Distributed minimum spanning tree: Difference between revisions

Revision as of 14:32, 9 August 2019

Revision as of 00:38, 17 April 2022

Line 29:

The GHS algorithm of [[Robert G. Gallager|Gallager]], Humblet and Spira is one of the best-known algorithms in distributed computing theory. This algorithm can construct the MST in asynchronous [[Message passing|Message-passing]] model.

=== Preconditions<ref name="GHS" /> ===

* The algorithm should run on a connected undirected graph.

* The graph should have distinct finite weights assigned to each edge. (This assumption can be removed by breaking ties between edge weights in a consistent way.)

Line 36:

* Messages can be transmitted independently in both directions on an edge and arrive after an unpredictable but finite delay, without error.

* Each edge delivers messages in [[FIFO (computing and electronics)|FIFO]] order.

<ref name="GHS" />

=== Properties of MST ===