asyncGHS

Minimum-Weight Spanning Tree in Asynchronous Distibuted Networks

• Followed the paper by Gallagher, Humblet, and Spira.
• An enhanced version of the paper, prepared by Guy Flysher and Amir Rubenstein, was also used for better understanding. It can be found here

Input to the master

• Number of processes
• A Unique ID (UID) for each process
• Weights of the edges as an adjacency matrix

The master on receiving this input spawns the worker processes. Each worker process knows only about its neighbors. (All links are bidirectional)

Output

• Core nodes' UIDs
• Each node's neighbors in the MST

Run

• Install Node.js
• npm install
• sudo node main.js connectivity.txt