Distributed minimum spanning tree: Difference between revisions

Revision as of 02:12, 15 May 2018

Revision as of 13:07, 7 July 2019

Line 19:

The [[Message passing|message-passing]] model is one of the most commonly used models in [[distributed computing]]. In this model, each process is modeled as a node of a graph. The communication channel between two processes is an edge of the graph.

Two commonly used algorithms for the classical minimum spanning tree problem are [[Prim's algorithm|Prim’sPrim's algorithm]] and [[Kruskal's algorithm|Kruskal’sKruskal's algorithm]]. However, it is difficult to apply these two algorithms in the distributed message-passing model. The main challenges are:

* Both [[Prim's algorithm|Prim’sPrim's algorithm]] and [[Kruskal's algorithm|Kruskal’sKruskal's algorithm]] require processing one node or vertex at a time, making it difficult to make them run in parallel. (For example, Kruskal's algorithm processes edges in turn, deciding whether to include the edge in the MST based on whether it would form a cycle with all previously chosen edges.)

* Both [[Prim's algorithm|Prim’sPrim's algorithm]] and [[Kruskal's algorithm|Kruskal’sKruskal's algorithm]] require processes to know the state of the whole graph, which is very difficult to discover in the message-passing model.

Due to these difficulties, new techniques were needed for distributed MST algorithms in the message-passing model. Some bear similarities to [[Borůvka's algorithm]] for the classical MST problem.

Line 69:

==== How to find minimum weight incident outgoing edge? ====

As discussed above, every node needs to find its minimum weight outgoing incident edge after the receipt of a broadcast message from the core. If node n receives a broadcast, it will pick its minimum weight basic edge and send a message to the node n’ on the other side with its fragment’sfragment's ID and level. Then, node n’ will decide whether the edge is an outgoing edge and send back a message to notify node n of the result. The decision is made according to the following:<br/>

'''Case 1''': Fragment_ID(n) = Fragment_ID(n’).<br/>

Then, node n and n’ belongs to same fragment (so the edge is not outgoing).<br/>