PineWikiFor more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.
1. Synchronous case
See LynchBook Section 4.4.
1.1. The quick sketch
- Can build MST by combining components.
- If all edges have distinct weights, adding lowest-weight edge out of each component in parallel never creates a cycle. We can force all edges to have distinct weights by breaking ties using edge ids.
- Rest is bookkeeping.
1.2. The bookkeeping
- Start with level 0 components, combine to level 1, 2, etc. components by joining along min-wt outgoing edges (MWOEs) in parallel.
- Initially, each node is the leader of its own level 0 component.
To get the leader of the level k+1 component, choose one endpoint of the unique edge that is an MWOE in both directions.
Existence of unique such edge follows from fact that MWOEs don't create cycle => graph of level k components is acyclic => each level k+1 component joins m level k components using m-1 edges => exactly one MWOE in each level k component appears twice by PigeonholePrinciple.
- Finding MWOEs, negotiating joins etc. is triggered by leaders doing broadcast/convergecast along trees.
1.3. Running time analysis
Level k components have at least 2k members => after O(log N) phases we have only one component.
- In each phase:
Leaders broadcasts their ids in O(diameter of component) = O(2k) steps and O(N) messages.
- Probing edges to find MWOE takes O(1) time and O(E) messages.
Convergecast to negotiate joins is O(diameter of component) = O(2k) steps and O(N) messages.
So total is O((N+|E|) log N) messages and O(20+21 + ... + 2lg N) = O(N) time.
To improve message complexity, we have to avoid extra edge probes. Trick is to (a) throw out edges once the endpoints are in the same component and (b) probe edges leaving each component one at a time in order of increasing weight. This gets message complexity down to O(N log N + E) since each edge is probed at most once. But (b) may require Omega(E) steps in the worst case, e.g. if we end up with two large components at the end most of whose edges are self-loops.
1.4. Applications
- Leader election, with a built-in tree to talk to people with! Message complexity is generally much smaller than for flooding, though time complexity may be worse.
- Multicast
2. Asynchronous case
Essentially the same algorithm works, but we have to deal with latecomers by absorbing low-level components into high-level components; see LynchBook Section 15.5.
