6.852 Lecture 9●Lower bound on leader election●Basic asynchronous network algorithms–constructing a spanning tree–breadth-first search–shortest paths–minimum spanning tree●Reading: Chapter 15 (continued)●Next lecture: Chapter 16.Last lecture●Finished defining formal model●Leader election algorithm for asynchronous networks●Described lower bound for leader electionLeader election in a ring●Lower bound in asynchronous network if n is unknown–Key: “assemble” ring from pieces which delay communication●silent state: no more messages will be sent without input●ring looks like “line” if communication delayed across ends●some lines may send Ω(n log n) msgs before becoming silent●connect ends of such a line to make a ring–delay communication across ends of lineLower bound on leader election●C(α) = number of messages sent in α●C(A) = sup{ C(α) | α is an input-free execution of A }●Lemma 1: If L1, L2, L3 are three line graphs of length l such that C(Li) ≥ k for all i then C(Li join Lj) ≥ 2k + l/2 for some i ≠ j–Suppose not. Consider three rings:L1L2L1L3L2L3Lower bound on leader election●Let αi be finite execution of Li with ≥ k msgs.●Run α1 then α2 then α1,2, with msgs across boundary–since fewer than l/2 add'l msgs, middles of L1 & L2 still silent●not enough msgs to reach themL1L2Lower bound on leader electionL2L1●Let αi be finite execution of Li with ≥ k msgs.●Run α1 then α2 then α1,2, with msgs across boundary–since fewer than l/2 add'l msgs, middles of L1 & L2 still no input●not enough msgs to reach them●Similarly for α2,1.–no interference between α1,2 and α2,1 L1L2Lower bound on leader electionL1L2●Connect both ends into ring–left neighbor is clockwise around ring●Run α1 then α2 then α1,2 then α2,1.–must be silent in final state–must elect leader (possibly in extension, but no more msgs)●Assume WLOG that elected leader is in “bottom half”–can't be midpoint of either L1 or L2Lower bound on leader electionL1L2L2L3●Same argument for ring(L2 join L3)–Can leader be in bottom half?Lower bound on leader electionL1L2L2L3L2L3L1●Same argument for ring(L2 join L3)–Can leader be in bottom half? No!–so must be in top halfLower bound on leader electionL1L2L2L3Lower bound on leader electionL1L2L2L3L1L3L1L3L2L3L1L3L2L1Lower bound on leader election●Lemma 2: There are an infinite number of processes that can send a message before receiving any.p1p2p1p2Lower bound on leader election●Lemma 1: If L1, L2, L3 are three line graphs of length l such that C(Li) ≥ k for all i, then C(Li join Lj) ≥ 2k + l/2 for some i ≠ j.●Lemma 2: There are an infinite number of processes that can send a message before receiving any.●Lemma 3: For any r ≥ 0, there are infinitely many disjoint line graphs L of length 2r such that C(L) ≥ r 2r-2.–base case (r = 0): Trivial.–base case (r = 1): Use Lemma 1.–inductive case (r ≥ 2):●Choose L1, L2, L3 of length 2r-1 with C(Li) ≥ (r-1) 2r-3.●By Lemma 2, for some i,j, C(Li join Lj) ≥ 2(r-1)2r-3 + 2r-1/2 = r 2r-2.Lower bound on leader election●Lemma 3: For any r ≥ 0, there are infinitely many disjoint line graphs L of length 2r such that C(L) ≥ r 2r-2.●Theorem: For any r ≥ 0, there is a ring R of size n = 2r such that C(R) = Ω(n log n).–Choose L of length 2r such that C(L) ≥ r 2r-2.–Connect ends, but delay communication across boundary.●line graph by itself must never elect leader●Corollary: For any n ≥ 0, there is a ring R of size n such that C(R) = Ω(n log n).Leader election in general network●Can get asynchronous version of synchronous alg–can simulate rounds with counters–need to know diameter for termination●Better algorithms later–no need to know diameter–lower message complexitySpanning trees and searching●Spanning trees used for broadcast/convergecast●Assume (for rest of these algorithms)–undirected graph (i.e., bidirectional communication)–root i0–size and diameter unknown–can identify in- and out-edges to same neighbor●Problem: each process outputs parent in tree●Start from SynchBFS algorithm–i0 “flood” search msg; parent is first that sends it to process–still yields spanning tree in asynchronous network,but not necessarily breadth-first treeAsynchSpanningTree●Signature–in receive(“search”)j,i, j ∈ nbrs–out send(“search”)i,j, j ∈ nbrs–out parent(j)i, j ∈ nbrs●State–parent: nbrs U { null }; init null–reported: Boolean; init false–for each j ∈ nbrs●send(j) ∈ { search, null };init search iff i = i0 ●send(“search”)i,jpre: send(j) = searcheff: send(j) := null●receive(“search”)j,i eff: if i ≠ i0 and parent = null then parent := j for k ∈ nbrs - { j } do send(k) := search●parent(j)i pre: parent = j reported = falseeff: reported := trueAsynchSpanningTreeAsynchSpanningTreesAsynchSpanningTreessAsynchSpanningTreesAsynchSpanningTreesAsynchSpanningTreessAsynchSpanningTreesAsynchSpanningTreesssAsynchSpanningTreeAsynchSpanningTree●Complexity–msg: O( |E| )–time: (diam) (l+d) + l●Anomaly: Paths may be longer than diameter!–messages may travel faster along longer pathsAsynchSpanningTree●Applications of spanning tree (as in synchronous alg)–message broadcast: piggyback on search msg–child pointers: easy because of bidirectional communication–use precomputed tree to do broadcast/convergecast●O(n) msg complexity; O( h(l+d) ) time complexity–see book for detailsh = height of tree; may be nBreadth-first search●In asynchronous networks, “SynchBFS” does not guarantee spanning tree constructed is breadth-first–long paths may be traversed faster than short ones●We can modify each process to keep track of distance, change parent when it hears of shorter path.–relaxation algorithm (like Bellman-Ford)–must inform neighbors of change–eventually tree stabilizes into breadth-first spanning treeAsynchBFS●Signature–in receive(m)j,i, m ∈ N, j ∈ nbrs–out send(m)i,j, m ∈ N, j ∈ nbrs●State–dist: N U { ∞ }; init 0 if i = i0, else ∞–parent: nbrs U { null }–for each j ∈ nbrs●send(j): FIFO queue of N;init { 0 } if i = i0, else ∅●send(m)i,jpre: m is head of send(j)eff: remove head of send(j)●receive(m)j,i eff: if m+1 < dist then dist := m+1 parent := j for k ∈ nbrs - { j } do add dist to send(k)●No parent actions.–no one knows when it's