20. Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees

What this lecture covers

This lecture finishes the two-lecture unit on distributed algorithms by first wrapping up the synchronous shortest-paths (Bellman-Ford) algorithm from the previous lecture, then introducing the much harder asynchronous model, where processes and channels take steps in arbitrary order with no shared notion of rounds. It revisits the same two structural problems, breadth-first spanning trees and shortest-paths spanning trees, and shows how naive synchronous algorithms fail when run asynchronously, and what it costs to fix them.

This is the second half of a self-contained pair of lectures; it assumes you watched the first lecture on synchronous distributed algorithms (leader election, maximal independent set, and breadth-first spanning trees). After watching, you should be able to explain why time is measured differently in an asynchronous model, why a naive breadth-first algorithm produces incorrect trees asynchronously, how relaxation-based corrections fix this, and why combining weights with asynchrony can make Bellman-Ford's message and time complexity exponential in the number of nodes.

Key ideas

• Synchronous Bellman-Ford invariant: after r rounds, every process holds the best distance and parent achievable via a path of at most r hops, so full correctness takes up to n - 1 rounds rather than just the diameter.
• Child-pointer corrections: because a process's parent can change as better distances arrive, maintaining child pointers requires sending "non-parent" corrections and restarting the search for children whenever a distance improves.
• Convergecast under change: termination detection still uses convergecast (leaves report "done" up the tree), but a process may participate in several rounds of convergecast as the tree structure keeps changing before it stabilizes.
• Asynchronous model: processes and channels are automata that take steps in an arbitrary interleaved order, with no shared rounds; correctness must be argued from invariants and timing properties expressed in real time, not round counts.
• Naive asynchronous BFS fails: a process that adopts the very first search message it sees as its parent can end up on a long, non-shortest path, since messages on longer paths can arrive before messages on the true shortest path.
• Relaxation fixes asynchronous BFS: tracking hop-count and updating whenever a strictly better hop count arrives converges to a correct breadth-first tree, analogous to Bellman-Ford but for asynchrony rather than weights.
• Exponential blowup: combining weights and asynchrony in a distributed Bellman-Ford algorithm can force a node to receive an exponential number of successive corrections, illustrated by a worst-case graph with detour edges weighted as powers of two.

Walkthrough

Completing synchronous Bellman-Ford's analysis (10:05)

The lecture restates the key invariant for the synchronous distributed Bellman-Ford algorithm from last time: after r rounds, each process's distance and parent reflect the best path using at most r hops. Since the longest simple path can use up to n - 1 hops, full stabilization takes n - 1 rounds, and message complexity becomes edges times rounds, both worse than the simpler unweighted breadth-first search case.

Maintaining child pointers and handling corrections (14:13)

Getting child pointers, not just parent pointers, requires each process to respond to search messages with "parent" or "non-parent," and to actively correct a previous parent if a better distance later changes who its parent is. A process that improves its own distance has to reset its known children and start collecting responses again, making bookkeeping considerably trickier than in the unweighted case.

Termination via repeated convergecast (18:17)

Detecting when the whole shortest-paths tree is finished still relies on convergecast, but since the tree keeps changing as distances improve, a node can believe it is a leaf, report "done," then later discover a shorter path forces it to become a non-child elsewhere, restarting the convergecast for that branch. The lecture walks through a worked example of exactly this kind of false start before the tree stabilizes and "done" information finally reaches the root.

Modeling the asynchronous system (25:22)

The lecture introduces the asynchronous model formally: processes and channels are automata with inputs and outputs, matched together by shared action names (send/receive), and the whole system executes by taking one enabled step at a time in any order, with no rounds. A channel is modeled explicitly as a queue that accepts sends and delivers messages from its head. A simple "max" process example shows how information propagates via one-at-a-time steps rather than synchronous broadcasts.

Measuring time without rounds (35:32)

Since there are no rounds, the lecture explains that time complexity is instead bounded using assumed upper bounds on local computation time and message delivery time (d), producing real-time complexity bounds. It stresses that these timing bounds are only used for external analysis; the processes themselves have no access to time and cannot use it to reason about their own progress.

Why naive asynchronous BFS breaks, and the relaxation fix (40:36)

Running the simple synchronous BFS algorithm asynchronously, where a process fixes its parent as the first search message it ever receives, can produce an incorrect, non-breadth-first tree, because messages on a longer path may simply arrive first. The fix, mirroring Bellman-Ford, has each process track its current best hop-distance and update its parent whenever a strictly shorter hop count arrives, propagating corrections until the tree stabilizes into a true breadth-first tree, though this reintroduces the "how do I know I'm done" problem, again solved with convergecast.

Asynchronous shortest-paths and the exponential blowup (54:50)

Combining weights with asynchrony means a process must now correct for two kinds of errors at once: longer but lower-weight paths (as in synchronous Bellman-Ford), and fast-arriving information on long asynchronous paths. The relaxation rule handles both uniformly, but the lecture shows this can blow up: an upper bound of n! possible corrections per node gives worst-case message and time complexity exponential in n. A concrete worst-case network, a spine of zero-weight edges shadowed by detours weighted as descending powers of two, is constructed to show a node can actually receive 2^k successive corrections in a single execution, causing exponential message pileup in one channel.

Before you watch

• Watch the previous lecture, "19. Synchronous Distributed Algorithms," since this lecture reviews and directly extends its leader election, MIS, breadth-first tree, and synchronous Bellman-Ford material.
• Be comfortable with the sequential Bellman-Ford shortest-paths algorithm and the idea of relaxation steps.
• Review the convergecast termination-detection technique, since it reappears repeatedly here under changing tree structure.

Check your understanding

1. Why does the synchronous distributed Bellman-Ford algorithm need up to n - 1 rounds to stabilize, rather than just the graph's diameter?
2. Explain why a process running the naive asynchronous breadth-first algorithm can end up with an incorrect, non-shortest parent, and why simply fixing on the first search message received causes the failure.
3. Why can a single process participate in convergecast multiple times before the shortest-paths tree finally stabilizes?
4. In the exponential-blowup example, why does a detour structure with powers-of-two weights let one node receive an exponential number of successive distance corrections?
5. Why are the timing bounds (local computation time, message delivery time) used to analyze asynchronous algorithms not something the processes themselves can observe or use?