分布式算法课件5

AlgorithmsinGeneralAsynchronousNetworks沈卓炜[e-mail]九龙湖校区计算机楼347房间Tel:52090919133909229522011年3月1Leaderelectioningeneralasynchronousnetworks•Undirectedgraphs.•CangetasynchronousversionofsynchronousFloodMaxalgorithm:–Simulateroundswithcounters.–Needtoknowdiameterfortermination.•FloodMaxalgorithm:•Everyround:SendmaxUIDseentoallneighbors.•Stopafterdiamrounds.•ElectselfiffownUIDismaxseen.2Leaderelectioningeneralasynchronousnetworks•We’llseebetterasynchronousalgorithmslater:–Don’tneedtoknowdiameter.–Lowermessagecomplexity.•Dependontechniquessuchas:–Breadth-firstsearch–Convergecastusingaspanningtree–Synchronizerstosimulatesynchronousalgorithms–Consistentglobalsnapshotstodetecttermination3Spanningtreeandsearching•Spanningtreesareusedforcommunication,e.g.,broadcast/convergecast•Startwiththesimpletaskofsettingupsome(arbitrary)spanningtreewitha(given)rooti0.•Assume:–Undirected,connectedgraph(i.e.,bidirectionalcommunication).–Rooti0–Sizeanddiameterunknown.–UIDs,withcomparisons.–Canidentifyin-andout-edgestosameneighbor.4Spanningtreeandsearching•Require:Eachprocessshouldoutputitsparentintree,withaparentoutputaction.•Startingpoint:SynchBFSalgorithm:–i0floodssearchmessage;–parentofanodeisthefirstnodefromwhichitreceivesasearchmessage.–Tryrunningthesamealgorithminasynchronousnetwork.–Stillyieldsspanningtree,butnotnecessarilybreadth-firsttree.5AsynchSpanningtree,Processi6Asynchronousspanningtree7AsynchronousspanningtreeS8AsynchronousspanningtreeS9AsynchronousspanningtreeS10AsynchronousspanningtreeSS11AsynchronousspanningtreeS12AsynchronousspanningtreeSSS13Asynchronousspanningtree14AsynchSpanningtree•Complexity–Messages:O(|E|)–Time:diam(l+d)+l•Anomaly:Pathsmaybelongerthandiameter!–Messagesmaytravelfasteralonglongerpaths,inasynchronousnetworks.15ApplicationofAsynchSpanningtree•SimilartosynchronousBFS•Messagebroadcast:Piggybackonsearchmessage.•Childpointers:Addresponsestosearchmessages,easybecauseofbidirectionalcommunication.•Useprecomputedtreeforbcast/convergecast–Nowthetiminganomalyarises–O(h(l+d))timecomplexity.–O(|E|)messagecomplexity.h=heightoftree;mayben16ApplicationsofBFS•Globalcomputation:–Sum,max,oranykindofdataaggregation:ConvergecastonBFStree.–Complexity:TimeO(diameter);MessagesO(n)•Leaderelection(withoutknowingdiameter):–EveryonestartsBFS,determinesmaxUID.–Complexity:TimeO(diam);MessagesO(n|E|)(actually,O(diam|E|)).•Computediameter:–AlldoBFS.–ConvergecasttofindheightofeachBFStree.–Convergecastagaintofindmaxofallheights.17Moreapplications•Asynchronousbroadcast/convergecast:–Canalsoconstructspanningtreewhileusingittobroadcastmessageandalsotocollectresponses.–E.g.,totelltherootwhenthebcastisdone,ortocollectaggregateddata.–Complexity:•O(|E|)messagecomplexity.•O(n(l+d))timecomplexity,timinganomaly.•Electleaderwhennodeshavenoinfoaboutthenetwork(noknowledgeofn,diam,etc.;noroot,nospanningtree)18Breadth-firstspanningtree•Assume(sameasabove):–Undirected,connectedgraph(i.e.,bidirectionalcommunication).–Rooti0.–Sizeanddiameterunknown.–UIDs,withcomparisons.•Require:Eachprocessshouldoutputitsparentinabreadth-firstspanningtree.19Breadth-firstspanningtree•Inasynchronousnetworks,modifiedSynchBFSdoesnotguaranteethatthespanningtreeconstructedisbreadth-first.–Longpathsmaybetraversedfasterthanshortones.•Canmodifyeachprocesstokeeptrackofdistance,changeparentwhenithearsofshorterpath.–Relaxationalgorithm(likeBellman-Ford).–Mustinformneighborsofchanges.–Eventually,treestabilizestoabreadth-firstspanningtree.20AsynchBFS21AsynchBFS022AsynchBFS0023AsynchBFS00024AsynchBFS10025AsynchBFS101126AsynchBFS101321127AsynchBFS1041321128AsynchBFS104132114429AsynchBFS10213214430AsynchBFS102513214231AsynchBFS610231321132AsynchBFS610221321133AsynchBFS210221321034AsynchBFS11022132135AsynchBFS•Complexity:–Messages:O(n|E|)•MaysendO(n)messagesoneachlink(oneforeachdistanceestimate).–Time:O(diamn(l+d))(takingpileupsintoaccount).–CanreducecomplexityifknowboundDondiameter:•Allowonlydistanceestimates≤D.•Messages:O(D|E|);Time:O(diamD(l+d))36AsynchBFS•Termination:–Nooneknowswhenthisisdone,socan’tproduceparentoutputs.–Canaugmentwithacksforsearchmessages,convergecastbacktoi0.–i0learnswhenthetreehasstabilized,tellseveryoneelse.–Abittricky:•Treegrowsandshrinks.•Someprocessesmayparticipatemanytimes,astheylearnimprovements.•Bookkeepingneeded.•Complexity?37LayeredBFS•Asynchronyleadstomanycorrections,whichleadtolotsofcommunication.•Idea:Slowdowncommunication,growthetreeinsynchronizedphases.–Inphasek,incorporateallnodesatdistancekfromi0.–i0synchronizesbetweenincorporatingnodesatdistancekandk+1.•Phase1:–i0sendssearchmessagestoneighbors.–Neighborssetdist:=1,sendackstoi0.38LayeredBFS•Phasek+1:–Assumephases1,…,karecompleted:eachnodeatdistance≤kknowsitsparent,andeachnodeatdistance≤k-1alsoknowsitschildren.–i0broadcastsnewphasemessagealongtreeedges,todistancekprocesses.–Eachofthesesendssearchmessagetoallnbrsexceptitsparent.–Whenanynon-i0processreceivesfirstsearchmessage,setsparent:=senderandsendsapositiveack;sendsnacksforsubsequentsearchmsgs.–Whendistancekprocessreceivesacks/na