6.852: Distributed Algorithms Fall, 2009Today’s planMinimum spanning tree, revisitedStrategy for designing asynchronous distributed algorithmsSynchronous model, reformulated in terms of automata Behavior of GlobSynchRequirements on each UiSynchronizersThe Synchronizer ProblemLocal Synchronizer, LocSynchProof sketch for Lemma 1Trivial distributed algorithm to implement LocSynchSimpleSynch, cont’dReducing the communicationSafe SynchronizersCorrectness of SafeSynchSafeSynch ImplementationsComparisonsSynchronizer Synchronizer Decomposition of   Implements SafeSynch Implementing ClusterSynch and ForestSynchPutting the pieces togetherComplexity of Comparison of CostsExampleApplication 1: Breadth-first searchApplication 2: Broadcast and ackApplication 3: Shortest pathsFurther workLower Bound on Time for SynchronizationLower bound on timek-Session ProblemExample: Boolean matrix computationSynchronous solutionAsynchronous lower boundLower boundLower bound, cont’dLower bound, cont’dConstructing the reorderingNext time…6.852: Distributed AlgorithmsFall, 2009Class 10Today’s plan• Simulating synchronous algorithms in asynchronous networks• Synchronizers• Lower bound for global synchronization• Reading: Chapter 16• Next: – Logical time– Reading: Chapter 18, [Lamport time, clocks…], [Mattern]Minimum spanning tree, revisited• In GHS, complications arise because different parts of the network can be at very different levels at the same time.• Alternative, more synchronized approach: – Keep levels of nearby nodes close, by restricting the asynchrony.– Each process uses a level variable to keep track of the level of its current component (according to its local knowledge).– Process at level k delays all “interesting” processing until it hears that all its neighbors have reached level ≥ k.• Looks (to each process) like global synchronization, but easier to achieve.• Each node inform its neighbors whenever it changes level.• Resulting algorithm is simpler than GHS.• Complexity:– Time: O(n log n), like GHS.– Messages: O( |E| log n), somewhat worse than GHS.Strategy for designing asynchronous distributed algorithms• Assume undirected graph G = (V,E).• Design a synchronous algorithm for G, transform it into an asynchronous algorithm using local synchronization. • Synchronize at every round (not every “level” as above).• Method works only for non-fault-tolerant algorithms.– In fact, no general transformation can work for fault-tolerant algorithms.– E.g., ordinary stopping agreement is solvable in synchronous networks, but unsolvable in asynchronous networks [FLP].• Present a general strategy, some special implementations.– Describe in terms of sub-algorithms, modeled as abstract services.– [Raynal book], [Awerbuch papers]• Then a lower bound on the time for global synchronization.– Larger than upper bounds for local synchronization.Synchronous model, reformulated in terms of automata • Interactions between user process i and synchronizer:– user-send(T,r)i• T = set of (message, destination) pairs, destinations are neighbors of i.• T = empty set ∅, if no messages sent by i at round r.• r = round number– user-rcv(T,r)i• T = set of (message, source) pairs, source a neighbor of i.• r = round numberGlobSynchU1U2Un• Global synchronizer automaton• User process automata:– Processes of an algorithm that uses the synchronizer.– May have other inputs/outputs, for interacting with other programs.Behavior of GlobSynch• Not exactly the synchronous model:– GlobSynch can receive round 2 messages from i before it finishes delivering all the round 1 messages.– But it doesn’t do anything with these until it’s finished round 1 deliveries.– So, essentially the same.• GlobSynch synchronizes globally between each pair of rounds.GlobSynchU1U2Un• Manages global synchronization of rounds:– Users send packages of all their round 1 messages, using user-send(T,r) actions.– GlobSynch waits for all round 1 messages, sorts them, then delivers to users, using user-rcv(T,r) actions.– Users send round 2 messages, etc.Requirements on each Ui– State consists of:•Atray of messages for each (destination, round).• Some Boolean flags to keep track of which sends and rcvs have happened.– Transitions obvious.– Liveness expressed by tasks, one for each (destination, round).GlobSynchU1U2Un• Well-formed:–Uisends the right kinds of messages, in the right order, at the right times.• Liveness:– After receiving the messages for any round r, Uieventually submits messages for round r+1. • See code for GlobSynch in [book, p. 534].SynchronizersThe Synchronizer Problem• Design an automaton A that “implements” GlobSynch in the sense that it “looks the same” to each Ui:– Has the right interface.– Exhibits the right behavior:• ∀ fair execution α of the Uis and A,• ∃ fair execution α′ of the Uis and GlobSynch, such that• ∀ i, α is indistinguishable by Uifrom α′, α ~Uiα′.• A “behaves like” GlobSynch, as far as any individual Uican tell.• Allows global reordering of events at different Ui.GlobSynchU1U2UnAU1U2UnLocal Synchronizer, LocSynch• Enforces local synchronization rather than global, still looks the same locally.• Only one difference from GlobSynch: – Precondition for usr-rcv(T,r)i.– Now, to deliver round r messages to user i, check only that i’s neighbors have sent round r messages.– Don’t wait for all nodes to get this far.• Lemma 1: For every fair execution α of the Uis and LocSynch, there is a fair execution α′ of the Uis and GlobSynch, such that for each Ui, α ~Uiα′.• Proof: – Can’t use a simulation relation, since global order of external events need not be the same, and simulation relations preserve external order.– So consider partial order of events and dependencies:LocSynchU1U2UnProof sketch for Lemma 1• Consider partial order of events and dependencies:– Each Uievent depends on previous Uievents.– user-rcv(*,r)ievent depends on user-send(*,r)jfor every neighbor j of i.– Take transitive closure.•Claim:If you start with a (fair) execution of LocSynch system and reorder the events while preserving these dependencies, the result is still a (fair) execution of the LocSynch system.• So, obtain α′ by reordering the events of α so that:– These dependencies are preserved, and–