Opening Synchronous Distributed Algorithms: Symmetry-Breaking and Shortest-Paths Spanning Trees
Synchronous Distributed Algorithms: Symmetry-Breaking and Shortest-Paths Spanning Trees
- Length
- 1 h 18 min
- Level
- Graduate
- Recorded
- MIT2016
Chapter 1 of 9: Before the lecture
Proves identical deterministic processes cannot elect a leader, then shows Luby's algorithm halves live edges per phase.
Synchronous distributed algorithms run on networks of processors that compute in lockstep rounds and exchange messages with their neighbours. Lynch, in session 22 of MIT 6.046J, opens with leader election and proves by induction that identical deterministic processes cannot break symmetry without unique identifiers or randomness. Luby's randomized maximal independent set algorithm follows: nodes draw random values from to , and local maxima join the set. The expected number of live edges falls by at least half each phase. The second half builds breadth-first spanning trees layer by layer, adds child pointers and convergecast for termination, then adapts Bellman-Ford relaxation to weighted shortest-paths trees. Graph theory, basic probability and sequential Bellman-Ford are assumed.
Synchronous distributed algorithms run on networks of processors that compute in lockstep rounds and exchange messages with their neighbours. Lynch, in session 22 of MIT 6.046J, opens with leader election and proves by induction that identical deterministic processes cannot break symmetry without unique identifiers or randomness. Luby's randomized maximal independent set algorithm follows: nodes draw random values from to , and local maxima join the set. The expected number of live edges falls by at least half each phase. The second half builds breadth-first spanning trees layer by layer, adds child pointers and convergecast for termination, then adapts Bellman-Ford relaxation to weighted shortest-paths trees. Graph theory, basic probability and sequential Bellman-Ford are assumed.
Distributed Algorithms
Distributed Computing: Fundamentals, Simulations, and Advanced Topics
Morgan Claypool series of monographs on Distributed Computing Theory

This lecture
Lecture 22 of 27 of Design and Analysis of Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in
Science paper on Sensory Organ Precursor cells