分布式算法课件5.ppt

《分布式算法课件5.ppt》由会员分享，可在线阅读，更多相关《分布式算法课件5.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分布式算法课件5Leader election in general asynchronous networksUndirected graphs.Can get asynchronous version of synchronous FloodMax algorithm:Simulate rounds with counters.Need to know diameter for termination.FloodMax algorithm:Every round:Send max UID seen to all neighbors.Stop after diam rounds.Elect

2、self iff own UID is max seen.2AsynchSpanning tree,Process i6Asynchronous spanning tree7Asynchronous spanning treeS8Asynchronous spanning treeS9Asynchronous spanning treeS10Asynchronous spanning treeSS11Asynchronous spanning treeS12Asynchronous spanning treeSSS13Asynchronous spanning tree14AsynchSpan

3、ning treeComplexityMessages:O(|E|)Time:diam(l+d)+lAnomaly:Paths may be longer than diameter!Messages may travel faster along longer paths,in asynchronous networks.15Application of AsynchSpanning treeSimilar to synchronous BFSMessage broadcast:Piggyback on search message.Child pointers:Add responses

4、to search messages,easy because of bidirectional communication.Use precomputed tree for bcast/convergecastNow the timing anomaly arisesO(h(l+d)time complexity.O(|E|)message complexity.h=height of tree;may be n16Applications of BFSGlobal computation:Sum,max,or any kind of data aggregation:Convergecas

5、t on BFS tree.Complexity:Time O(diameter);Messages O(n)Leader election(without knowing diameter):Everyone starts BFS,determines max UID.Complexity:Time O(diam);Messages O(n|E|)(actually,O(diam|E|).Compute diameter:All do BFS.Convergecast to find height of each BFS tree.Convergecast again to find max

6、 of all heights.17More applicationsAsynchronous broadcast/convergecast:Can also construct spanning tree while using it to broadcast message and also to collect responses.E.g.,to tell the root when the bcast is done,or to collect aggregated data.Complexity:O(|E|)message complexity.O(n(l+d)time comple

7、xity,timing anomaly.Elect leader when nodes have no info about the network(no knowledge of n,diam,etc.;no root,no spanning tree)18Breadth-first spanning treeAssume(same as above):Undirected,connected graph(i.e.,bidirectional communication).Root i0.Size and diameter unknown.UIDs,with comparisons.Requ

8、ire:Each process should output its parent in a breadth-first spanning tree.19Breadth-first spanning treeIn asynchronous networks,modified SynchBFSdoes not guarantee that the spanning tree constructed is breadth-first.Long paths may be traversed faster than short ones.Can modify each process to keep

9、track of distance,change parent when it hears of shorter path.Relaxation algorithm(like Bellman-Ford).Must inform neighbors of changes.Eventually,tree stabilizes to a breadth-first spanning tree.20AsynchBFS21AsynchBFS022AsynchBFS0023AsynchBFS00024AsynchBFS10025AsynchBFS101126AsynchBFS101321127Asynch

10、BFS1041321128AsynchBFS104132114429AsynchBFS10213214430AsynchBFS102513214231AsynchBFS610231321132AsynchBFS610221321133AsynchBFS210221321034AsynchBFS11022132135AsynchBFSComplexity:Messages:O(n|E|)May send O(n)messages on each link(one for each distance estimate).Time:O(diam n(l+d)(taking pileups into

11、account).Can reduce complexity if know bound D on diameter:Allow only distance estimates D.Messages:O(D|E|);Time:O(diamD(l+d)36AsynchBFSTermination:No one knows when this is done,so cant produce parent outputs.Can augment with acks for search messages,convergecast back to i0.i0 learns when the tree

12、has stabilized,tells everyone else.A bit tricky:Tree grows and shrinks.Some processes may participate many times,as they learn improvements.Bookkeeping needed.Complexity?37Layered BFSAsynchrony leads to many corrections,which lead to lots of communication.Idea:Slow down communication,grow the tree i

13、n synchronized phases.In phase k,incorporate all nodes at distance k from i0.i0 synchronizes between incorporating nodes at distance k and k+1.Phase 1:i0 sends search messages to neighbors.Neighbors set dist:=1,send acks to i0.38Layered BFSPhase k+1:Assume phases 1,k are completed:each node at dista

14、nce k knows its parent,and each node at distance k-1 also knows its children.i0 broadcasts newphase message along tree edges,to distance k processes.Each of these sends search message to all nbrs except its parent.When any non-i0 process receives first search message,sets parent:=sender and sends a

15、positive ack;sends nacks for subsequent search msgs.When distance k process receives acks/nacks for all its search messages,designates nodes that sent postive acks as its children.Then distance k processes convergecast back to i0 along depth k tree to say that theyre done;include a bit saying whethe

16、r new nodes were found.39Layered BFSTerminates:When i0 learns,in some phase,that no new nodes were found.Obviously produces BFS tree.Complexity:Messages:O(|E|+n diam)Time:Use simplified analysis:Neglecting local computation time l Assuming that every message in a channel is delivered in time d(ignor

17、ing congestion delays).O(diam2 d)Each edge explored at most once in each direction by search/ack.Each tree edge traversed at most once in each phase by newphase/convergecast.40Layered BFS vs AsynchBFSMessage complexity:AsynchBFS:O(diam|E|),assuming diam is known,O(n|E|)if notLayeredBFS:O(|E|+n diam)

18、Time complexity:AsynchBFS:O(diamd)LayeredBFS:O(diam2d)Can also define“hybrid”algorithm Add m layers in each phase.Within each phase,layers constructed asynchronously.Intermediate performance.41Shortest PathsAssumptions:Same as for BFS,plus edge weights.weight(i,j),nonnegative real,same in both direc

19、tions.Require:Output shortest distance and parent in shortest-paths tree.Use Bellman-Ford asynchronouslyUsed to establish routes in ARPANET 1969-1980.Can augment with convergecast as for BFS,for termination.But worst-case complexity is very bad42AsynchBellmanFord43AsynchBellmanFordTermination:Use co

20、nvergecast(as for AsynchBFS).Complexity:O(n!)simple paths from i0 to any other node,which is O(nn).So the number of messages sent on any channel is O(nn).So message complexity=O(nn|E|),time complexity=O(nnn(l+d).44AsynchBellmanFordComplexity:Q:Are the message and time complexity really exponential i

21、n n?A:Yes:In some execution of network below,iksends 2kmessages to ik+1,so message complexity is(2n/2)and time complexity is(2n/2d).45Exponential time/message complexityPossible distance estimates for ik are 2k1,2k2,0.Moreover,ik can take on all these estimates in sequence:First,messages traverse up

22、per links,2k1.Then last lower message arrives at ik,2k2.Then lower message ik-2 ik-1 arrives,reduces ik-1s estimate by 2,message ik-1 ik arrives on upper links,2k3.Etc.Count down in binary.If this happens quickly,get pileup of 2k search messages in Ck,k+1.46Shortest PathsMoral:Unrestrained asynchron

23、y can cause problems.Return to this problem after we have better synchronization methods.Now,another good illustration of the problems introduced by asynchrony:47Minimum spanning treeAssumptions:G=(V,E)connected,undirected.Weighted edges,weights known to endpoint processes,weights distinct.UIDsProce

24、sses dont know n,diam.Can identify in-and out-edges to same neighbor.Input:wakeup actions,occurring at any time at one or more nodes.Process wakes up when it first receives either a wakeupinput or a protocol message.48Minimum spanning treeAssumptions:Requires:Produce MST,where each process knows whi

25、ch of its incident edges belong to the tree.Guaranteed to be unique,because of unique weights.Gallager-Humblet-Spira algorithm 49Recall synchronous algorithmProceeds in phases(levels).After each phase,we have a spanning forest,in which each component tree has a leader.In each phase,each component fi

26、nds min weight outgoing edge(MWOE),then components merge using all MWOEs to get components for next phase.50Synchronous algorithmComplexity is good:Messages:O(nlog n+|E|)Time(rounds):O(nlog n)Low message complexity depends on the way nodes test their incident edges,in order of weight,not retesting s

27、ame edge once its rejected.Q:How to run this algorithm asynchronously?51Running the Alg asynchronouslyProblems arise:Inaccurate information about outgoing edges:In synchronous algorithm,when a node tests its edges,it knows that its neighbors are already up to the same level,and have up-to-date infor

28、mation about their component.In asynchronous version,neighbors could lag behind;they might be in same component but not yet know this.Less“balanced”combination of components:In synchronous algorithm,level k components have 2knodes,and level k+1 components are constructed from at least two level k co

29、mponents.In asynchronous version,components at different levels could becombined.Can lead to more messages overall.52Running the Alg asynchronouslyProblems arise:Inaccurate information about outgoing edges:Less“balanced”combination of components:Concurrent overlapping searches/convergecasts:When nod

30、es are out of synch,concurrent searches for MWOEs could interfere with each other(well see this).Time bound:These problems result from nodes being out-of-synch,at different levels.We could try to synchronize levels,but this must be done carefully,so as not to hurt the time complexity too much.53GHS

31、algorithmSame basic ideas as before:Form components,combine along MWOEs.Within any component,processes cooperate to find component MWOE.Broadcast from leader,convergecast,etc.54GHS algorithmIntroduce synchronization to prevent nodes from getting too far ahead of their neighbors.Associate a“level”wit

32、h each component,as before.Number of nodes in a level k component 2k.Now,each level k+1 component will be(initially)formed from exactly two level k components.Level numbers are used for synchronization,and in determining who is in the same component.Complexity:Messages:O(|E|+n log n)Time:O(nlog n(d+

33、l)55GHS algorithmCombine pairs of components in two ways,merging and absorbing.Merging:C and C have same level k,and have a common MWOE.Result is a new merged component C,with level k+1.56GHS algorithmAbsorbing:level(C)level(C),and Cs MWOE leads to C.Result is to absorb C into C.Not creating a new c

34、omponent,just adding C to existing C.C“catches up”with the more advanced C.Absorbing is cheap,local.Merging and absorbing ensure that the number of nodes in any level k component 2k.Merging and absorbing are both allowable operations in finding MST,because they are allowed by the general theory for

35、MSTs.57LivenessQ:Why are merging and absorbing sufficient to ensure that the construction is eventually completed?Lemma:After any allowable finite sequence of merges and absorbs,either the forest consists of one tree(so were done),or some merge or absorb is enabled.58LivenessProof:Consider the curre

36、nt“component digraph”:Nodes=componentsDirected edges correspond to MWOEsThen there must be some pair C,C whose MWOEs point to each other.(Why?)These MWOEs must be the same edge.(Why?)Can combine,using either merge or absorb:If same level,merge,else absorb.So,merging and absorbing are enough.Now,how

37、to implement them with a distributed algorithm?59Component names and leadersFor every component with level 1,define the core edge of the components tree.Defined in terms of the merge and absorb operations used to construct the component:After merge:Use the common MWOE.After absorb:Keep the old core

38、edge of the higher-level component.“The edge along which the most recent merge occurred.”Component name:(core,level)Leader:Endpoint of core edge with higher id.60Determining if an edge is outgoingSuppose i wants to know if the edge(i,j)is outgoing from is current component.At that point,is component

39、 name info is up-to-date:Component is in“search mode”.i has received initiate message from the leader,which carried component name.So i sends j a test message.Three cases:61Determining if an edge is outgoingThree cases:If js current(core,level)is the same as is,then j knows that j is in the same com

40、ponent as i.If js(core,level)is different from is and js level is is,then j knows that j is in a different component from i.Component has only one core per level.No one in the same component currently has a higher level than i does,since the component is still searching for its MWOE.If js level is i

41、s,then j doesnt know if it is in the same or a different component.So it doesnt yet respond-waits to catch up to is level.62Liveness,againQ:Can the extra delays imposed here affect the progress argument?No:We can redo the progress argument,this time considering only those components with the lowest

42、current level k.All processes in these components must succeed in determining their MWOEs,so these components succeed in determining the component MWOE.If any of these level k components MWOEs leads to a higher level,can absorb.If not then all lead to other level k components,so as before,we must ha

43、ve two components that point to each other;so can merge.63Interference among concurrent MWOE searchesSuppose C gets absorbed into C via an edge from i to j,while C is working on determining its MWOE.Two cases:j has not yet reported its local mwoe when the absorb occurs.Then its not too late to inclu

44、de C in the search for the MWOE of C.So j forwards the initiate message into C.j has already reported its local mwoe.Then its too late to include C in the search.But it doesnt matter:the MWOE for the combined component cant be outgoing from a node in C anyhow!64A few detailsSpecific messages:initiat

45、e:Broadcast from leader to find MWOE;piggybacks component name.report:Convergecast MWOE responses back to leader.test:Asks whether an edge is outgoing from the component.accept/reject:Answers.changeroot:Sent from leader to endpoint of MWOE.connect:Sent across the MWOE,to connect components.We say me

46、rge occurs when connect message has been sent both ways on the edge(2 nodes must have same level).We say absorb occurs when connect message has been sent on the edge from a lower-level to a higher-level node.65Test-Accept-Reject protocolBookkeeping:Each process i keeps a list of incident edges in or

47、der of weight,classified as:branch(in the MST),rejected(leads to same component),orunknown(not yet classified).66Test-Accept-Reject protocolProcess i tests only unknown edges,sequentially in order of weight:Sends test message,with(core,level);recipient j compares.If same(core,level),j sends reject(s

48、ame component),and i reclassifies edge as rejected.If(core,level)pairs are unequal and level(j)level(i)then j sends accept(different component).i does not reclassify the edge.If level(j)level(i)then j delays responding,until level(j)level(i).Retesting is possible,for accepted edges.Reclassify edge a

49、s branch as a result of changeroot message.67ComplexityAs for synchronous version.Messages:O(|E|+n log n)4|E|for test-reject msgs(one pair for each direction of every edge)n initiate messages per level(broadcast)n report messages per level(convergecast)2n test-accept messages per level(one pair per

50、node)n change-root/connect messages per level(core to MWOE path)log n levelsTotal:4|E|+5n log nTime:O(nlog n(l+d)68Minimum spanning treeApplication to leader election:Convergecast from leaves until messages meet at node or edge.Works with any spanning tree,not just MST.E.g.,in asynchronous ring,this