最新分布式算法课件5学习资料.ppt

《最新分布式算法课件5学习资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、LeaderelectioningeneralasynchronousnetworksUndirectedgraphs.CangetasynchronousversionofsynchronousFloodMaxalgorithm:Simulateroundswithcounters.Needtoknowdiameterfortermination.FloodMaxalgorithm:Everyround:SendmaxUIDseentoallneighbors.Stopafterdiamrounds.ElectselfiffownUIDismaxseen.2Leaderelecti

2、oningeneralasynchronousnetworksWe’llseebetterasynchronousalgorithmslater:Don’tneedtoknowdiameter.Lowermessagecomplexity.Dependontechniquessuchas:Breadth-firstsearchConvergecastusingaspanningtreeSynchronizerstosimulatesynchronousalgorithmsConsistentglobalsnapshotstodetecttermination3Spanningtree

3、andsearchingSpanningtreesareusedforcommunication,e.g.,broadcast/convergecastStartwiththesimpletaskofsettingupsome(arbitrary)spanningtreewitha(given)rooti0.Assume:Undirected,connectedgraph(i.e.,bidirectionalcommunication).Rooti0Sizeanddiameterunknown.UIDs,withcomparisons.Canidentifyin-andout-edg

4、estosameneighbor.4SpanningtreeandsearchingRequire:Eachprocessshouldoutputitsparentintree,withaparentoutputaction.Startingpoint:SynchBFSalgorithm:i0floodssearchmessage;parentofanodeisthefirstnodefromwhichitreceivesasearchmessage.Tryrunningthesamealgorithminasynchronousnetwork.Stillyieldsspanning

5、tree,butnotnecessarilybreadth-firsttree.5AsynchSpanningtree,Processi6Asynchronousspanningtree7AsynchronousspanningtreeS8AsynchronousspanningtreeS9AsynchronousspanningtreeS10AsynchronousspanningtreeSS11AsynchronousspanningtreeS12AsynchronousspanningtreeSSS13Asynchronousspanningtree14AsynchSpanni

6、ngtreeComplexityMessages:O(

7、E

8、)Time:diam(l+d)+lAnomaly:Pathsmaybelongerthandiameter!Messagesmaytravelfasteralonglongerpaths,inasynchronousnetworks.15ApplicationofAsynchSpanningtreeSimilartosynchronousBFSMessagebroadcast:Piggybackonsearchmessage.Childpointers:Addresponsestosearchmessages,easybec

9、auseofbidirectionalcommunication.Useprecomputedtreeforbcast/convergecastNowthetiminganomalyarisesO(h(l+d))timecomplexity.O(

10、E

11、)messagecomplexity.h=heightoftree;mayben16ApplicationsofBFSGlobalcomputation:Sum,max,oranykindofdataaggr