Opening Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees
Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees
- Length
- 1 h 12 min
- Level
- Graduate
- Recorded
- MIT2021
Chapter 1 of 10: Before the lecture
Lynch builds asynchronous Bellman-Ford and gives a graph with detours that forces exponentially many corrections.
Asynchronous distributed algorithms drop synchronized rounds, so processes and FIFO channels, modeled as automata, take steps in a nondeterministic order. Lynch first reviews synchronous leader election, maximal independent set, breadth-first spanning trees and synchronous Bellman-Ford, including child pointers and convergecast termination. An asynchronous maximum-finding algorithm illustrates message propagation and liveness, and naive search propagation is shown to fail at building a breadth-first tree. Lynch repairs it by tracking hop distance and relaxing parent pointers, then extends the relaxation to weighted edges as asynchronous Bellman-Ford. A network with detours makes exponentially many corrections pile up in queues, and an outline of graduate topics in fault tolerance closes the session.
Asynchronous distributed algorithms drop synchronized rounds, so processes and FIFO channels, modeled as automata, take steps in a nondeterministic order. Lynch first reviews synchronous leader election, maximal independent set, breadth-first spanning trees and synchronous Bellman-Ford, including child pointers and convergecast termination. An asynchronous maximum-finding algorithm illustrates message propagation and liveness, and naive search propagation is shown to fail at building a breadth-first tree. Lynch repairs it by tracking hop distance and relaxing parent pointers, then extends the relaxation to weighted edges as asynchronous Bellman-Ford. A network with detours makes exponentially many corrections pile up in queues, and an outline of graduate topics in fault tolerance closes the session.
Distributed Algorithms

This lecture
Lecture 23 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