6.852: Distributed Algorithms Fall, 2009Today’s planLast timeLast timeLower bounds for leader electionLower bounds for leader electionComparison-based algorithmsLower bound proof: OverviewLower bound proof: DefinitionsLower bound proof: Key LemmaLower bound proof: Key lemmaKey lemmaKey lemmaLower bound proofLower bound proofLower bound proofHighly symmetric ringsC-symmetric ringsGeneral Synchronous NetworksGeneral synchronous networksGeneral synchronous network assumptionsLeader election in general synchronous networksLeader election in general synchronous networksLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkKey invariantReducing the message complexity Leader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkLeader election in general networkSimulation relationSimulation relation for the optimized algorithmWhy all these proofs?Other problems besides leader election…Breadth-first searchBreadth-first searchBreadth-first searchBreadth-first search algorithmBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first searchBreadth-first search algorithmBFS, bells and whistlesApplications of BFSApplications of BFSNext time6.852: Distributed AlgorithmsFall, 2009Class 2Today’s plan• Leader election in a synchronous ring: – Lower bound for comparison-based algorithms.• Basic computation in general synchronous networks:– Leader election– Breadth-first search– Broadcast and convergecast• Reading: Sections 3.6, 4.1-4-2• Next time: – Shortest paths– Minimum spanning tree– Maximal independent set– Reading: Sections 4.3-4.5Last time• Model for synchronous networks• Leader election problem, in simple ring networks• Two algorithms:– [LeLann], [Chang, Roberts]• Pass UID tokens one way, elect max• Proofs, using invariants• Time complexity: n (or 2n for halting, unknown size)• Communication (message) complexity: O(n2)– [Hirshberg, Sinclair]• Send UID tokens to successively-doubled distances, in both directions.z Message complexity: O(n log n)z Time complexity: O(n) (dominated by last phase)Last time• Q: Can the message complexity be lowered still more?• Non-comparison-based algorithms– Wait quietly until it’s your “turn”, determined by UID.– Message complexity: O(n)– Time complexity: O(uminn), or O(n 2umin) if n is unknownLower bounds for leader electionz Q: Can we get lower time complexity?z Easy n/2 lower bound (informal):z Suppose an algorithm always elects a leader in time < n/2.z Consider two separate rings of size n (n odd), R1and R2.z Algorithm elects processes i1and i2, each in time < n/2.z Now cut R1and R2at points furthest from the leaders, paste them together to form a new ring R of size 2n.z Then in R, both i1and i2 get elected, because the time it takes for them to get elected is insufficient for information about the pasting to propagate from the pasting points to i1and i2.R1i1R2i2Ri1i2Lower bounds for leader electionz Q: Can we get lower message complexity?z More difficult Ω(n log n) lower bound.z Assumptions− Comparison-based algorithm− Unique start state (except for UID), deterministic.Comparison-based algorithmsz All decisions determined only by relative order of UIDs:− Identical start states, except for UID.− Manipulate UIDs only by copying, sending, receiving, and comparing them (<, =, >).− Can use results of comparisons to decide what to do:z State transitionz What (if anything) to send to neighborsz Whether to elect self leaderLower bound proof: Overviewz For any n, there is a ring Rnof size n such that in Rn, any leader election algorithm has:− Ω(n) “active” rounds (in which messages are sent).− Ω(n/i) msgs sent in active round i (for i > √n).− Thus, Ω(n log n) msgs total.z Choose ring Rnwith a great deal of symmetry in ordering pattern of UIDs.z For n = power of 2: Bit-reversal rings.z For general n: c-symmetric rings.z Key lemma: Processes whose neighborhoods “look the same” act the same, until information from outside their neighborhoods reaches them.− Need many active rounds to break symmetry.z A round is active if some (non-null) message is sent in the round.z k-neighborhood of a process: The 2k+1 processes within distance k.z (u1, u2,..., uk) & (v1, v2,..., vk) are order-equivalentprovided that ui≤ ujiff vi≤ vjfor all i,j.z Implies same (<, =, >) relationships for all corresponding pairs.z Example: (1 3 6 5 2 7 9) vs. (2 7 9 8 4 10 11)z Two process states s and t correspond with respect to (u1, u2,..., uk) & (v1, v2,..., vk) if they are identical except that occurrences of uiin s are replaced by viin t for all i.− Analogous definition for corresponding messages.Lower bound proof: DefinitionsLower bound proof: Key Lemma•Lemma:Suppose A is a comparison-based algorithm on a synchronous ring network. Suppose i and j are processes whose sequences of UIDs in their k-neighborhoods are order-equivalent. Then at any point after ≤ k active rounds, the states of i and j correspond with respect to their k-neighborhoods' UID sequences.• That is, processes with order-equivalent k-neighborhoods are indistinguishable until after “enough” active rounds.• Enough: Information has had a chance to reach the processes from outside the k-neighborhoods.• Example: 5 and 8 have order-equivalent 3-neighborhoods, so must remain in corresponding states through 3 active rounds.1256397118104Lower bound proof: Key lemmaz Lemma: Suppose A is a comparison-based algorithm on a synchronous ring