分布式算法5ppt课件

1 AlgorithmsinGeneralAsynchronousNetworks 沈卓炜zwshen 九龙湖校区计算机楼347房间Tel 52090919133909229522011年3月 2 Leaderelectioningeneralasynchronousnetworks Undirectedgraphs CangetasynchronousversionofsynchronousFloodMaxalgorithm Simulateroundswithcounters Needtoknowdiameterfortermination FloodMaxalgorithm Everyround SendmaxUIDseentoallneighbors Stopafterdiamrounds ElectselfiffownUIDismaxseen 3 Leaderelectioningeneralasynchronousnetworks We llseebetterasynchronousalgorithmslater Don tneedtoknowdiameter Lowermessagecomplexity Dependontechniquessuchas Breadth firstsearchConvergecastusingaspanningtreeSynchronizerstosimulatesynchronousalgorithmsConsistentglobalsnapshotstodetecttermination 4 Spanningtreeandsearching Spanningtreesareusedforcommunication e g broadcast convergecastStartwiththesimpletaskofsettingupsome arbitrary spanningtreewitha given rooti0 Assume Undirected connectedgraph i e bidirectionalcommunication Rooti0Sizeanddiameterunknown UIDs withcomparisons Canidentifyin andout edgestosameneighbor 5 Spanningtreeandsearching Require Eachprocessshouldoutputitsparentintree withaparentoutputaction Startingpoint SynchBFSalgorithm i0floodssearchmessage parentofanodeisthefirstnodefromwhichitreceivesasearchmessage Tryrunningthesamealgorithminasynchronousnetwork Stillyieldsspanningtree butnotnecessarilybreadth firsttree 6 AsynchSpanningtree Processi 7 Asynchronousspanningtree 8 Asynchronousspanningtree S 9 Asynchronousspanningtree S 10 Asynchronousspanningtree S 11 Asynchronousspanningtree S S 12 Asynchronousspanningtree S 13 Asynchronousspanningtree S S S 14 Asynchronousspanningtree 15 AsynchSpanningtree ComplexityMessages O E Time diam l d lAnomaly Pathsmaybelongerthandiameter Messagesmaytravelfasteralonglongerpaths inasynchronousnetworks 16 ApplicationofAsynchSpanningtree SimilartosynchronousBFSMessagebroadcast Piggybackonsearchmessage Childpointers Addresponsestosearchmessages easybecauseofbidirectionalcommunication Useprecomputedtreeforbcast convergecastNowthetiminganomalyarisesO h l d timecomplexity O E messagecomplexity h heightoftree mayben 17 ApplicationsofBFS 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 18 Moreapplications Asynchronousbroadcast convergecast Canalsoconstructspanningtreewhileusingittobroadcastmessageandalsotocollectresponses E g totelltherootwhenthebcastisdone ortocollectaggregateddata Complexity O E messagecomplexity O n l d timecomplexity timinganomaly Electleaderwhennodeshavenoinfoaboutthenetwork noknowledgeofn diam etc noroot nospanningtree 19 Breadth firstspanningtree Assume sameasabove Undirected connectedgraph i e bidirectionalcommunication Rooti0 Sizeanddiameterunknown UIDs withcomparisons Require Eachprocessshouldoutputitsparentinabreadth firstspanningtree 20 Breadth firstspanningtree Inasynchronousnetworks modifiedSynchBFSdoesnotguaranteethatthespanningtreeconstructedisbreadth first Longpathsmaybetraversedfasterthanshortones Canmodifyeachprocesstokeeptrackofdistance changeparentwhenithearsofshorterpath Relaxationalgorithm likeBellman Ford Mustinformneighborsofchanges Eventually treestabilizestoabreadth firstspanningtree 21 AsynchBFS 22 AsynchBFS 0 23 AsynchBFS 0 0 24 AsynchBFS 0 0 0 25 AsynchBFS 1 0 0 26 AsynchBFS 1 0 1 1 27 AsynchBFS 1 0 1 3 2 1 1 28 AsynchBFS 1 0 4 1 3 2 1 1 29 AsynchBFS 1 0 4 1 3 2 1 1 4 4 30 AsynchBFS 1 0 2 1 3 2 1 4 4 31 AsynchBFS 1 0 2 5 1 3 2 1 4 2 32 AsynchBFS 6 1 0 2 3 1 3 2 1 1 33 AsynchBFS 6 1 0 2 2 1 3 2 1 1 34 AsynchBFS 2 1 0 2 2 1 3 2 1 0 35 AsynchBFS 1 1 0 2 2 1 3 2 1 36 AsynchBFS 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 37 AsynchBFS Termination Nooneknowswhenthisisdone socan tproduceparentoutputs Canaugmentwithacksforsearchmessages convergecastbacktoi0 i0learnswhenthetreehasstabilized tellseveryoneelse Abittricky Treegrowsandshrinks Someprocessesmayparticipatemanytimes astheylearnimprovements Bookkeepingneeded Complexity 38 LayeredBFS Asynchronyleadstomanycorrections whichleadtolotsofcommunication Idea Slowdowncommunication growthetreeinsynchronizedphases Inphasek incorporateallnodesatdistancekfromi0 i0synchronizesbetweenincorporatingnodesatdistancekandk 1 Phase1 i0sendssearchmessagestoneighbors Neighborssetdist 1 sendackstoi0 39 LayeredBFS Phasek 1 Assumephases1 karecompleted eachnodeatdistance kknowsitsparent andeachnodeatdistance k 1alsoknowsitschildren i0broadcastsnewphasemessagealongtreeedges todistancekprocesses Eachofthesesendssearchmessagetoallnbrsexceptitsparent Whenanynon i0processreceivesfirstsearchmessage setsparent senderandsendsapositiveack sendsnacksforsubsequentsearchmsgs Whendistancekprocessreceivesacks nacksforallitssearchmessages designatesnodesthatsentpostiveacksasitschildren Thendistancekprocessesconvergecastbacktoi0alongdepthktreetosaythatthey redone includeabitsayingwhethernewnodeswerefound 40 LayeredBFS Terminates Wheni0learns insomephase thatnonewnodeswerefound ObviouslyproducesBFStree Complexity Messages O E ndiam Time Usesimplifiedanalysis NeglectinglocalcomputationtimelAssumingthateverymessageinachannelisdeliveredintimed ignoringcongestiondelays O diam2d Eachedgeexploredatmostonceineachdirectionbysearch ack Eachtreeedgetraversedatmostonceineachphasebynewphase convergecast 41 LayeredBFSvsAsynchBFS Messagecomplexity AsynchBFS O diam E assumingdiamisknown O n E ifnotLayeredBFS O E ndiam Timecomplexity AsynchBFS O diamd LayeredBFS O diam2d Canalsodefine hybrid algorithmAddmlayersineachphase Withineachphase layersconstructedasynchronously Intermediateperformance 42 ShortestPaths Assumptions SameasforBFS plusedgeweights weight i j nonnegativereal sameinbothdirections Require Outputshortestdistanceandparentinshortest pathstree UseBellman FordasynchronouslyUsedtoestablishroutesinARPANET1969 1980 CanaugmentwithconvergecastasforBFS fortermination Butworst casecomplexityisverybad 43 AsynchBellmanFord 44 AsynchBellmanFord Termination Useconvergecast asforAsynchBFS Complexity O n simplepathsfromi0toanyothernode whichisO nn SothenumberofmessagessentonanychannelisO nn Somessagecomplexity O nn E timecomplexity O nnn l d 45 AsynchBellmanFord Complexity Q Arethemessageandtimecomplexityreallyexponentialinn A Yes Insomeexecutionofnetworkbelow iksends2kmessagestoik 1 somessagecomplexityis 2n 2 andtimecomplexityis 2n 2d 46 Exponentialtime messagecomplexity Possibledistanceestimatesforikare2k 1 2k 2 0 Moreover ikcantakeonalltheseestimatesinsequence First messagestraverseupperlinks 2k 1 Thenlastlowermessagearrivesatik 2k 2 Thenlowermessageik 2 ik 1arrives reducesik 1 sestimateby2 messageik 1 ikarrivesonupperlinks 2k 3 Etc Countdowninbinary Ifthishappensquickly getpileupof2ksearchmessagesinCk k 1 47 ShortestPaths Moral Unrestrainedasynchronycancauseproblems Returntothisproblemafterwehavebettersynchronizationmethods Now anothergoodillustrationoftheproblemsintroducedbyasynchrony 48 Minimumspanningtree Assumptions G V E connected undirected Weightededges weightsknowntoendpointprocesses weightsdistinct UIDsProcessesdon tknown diam Canidentifyin andout edgestosameneighbor Input wakeupactions occurringatanytimeatoneormorenodes Processwakesupwhenitfirstreceiveseitherawakeupinputoraprotocolmessage 49 Minimumspanningtree Assumptions Requires ProduceMST whereeachprocessknowswhichofitsincidentedgesbelongtothetree Guaranteedtobeunique becauseofuniqueweights Gallager Humblet Spiraalgorithm 50 Recallsynchronousalgorithm Proceedsinphases levels Aftereachphase wehaveaspanningforest inwhicheachcomponenttreehasaleader Ineachphase eachcomponentfindsminweightoutgoingedge MWOE thencomponentsmergeusingallMWOEstogetcomponentsfornextphase 51 Synchronousalgorithm Complexityisgood Messages O nlogn E Time rounds O nlogn Lowmessagecomplexitydependsonthewaynodestesttheirincidentedges inorderofweight notretestingsameedgeonceit srejected Q Howtorunthisalgorithmasynchronously 52 RunningtheAlgasynchronously Problemsarise Inaccurateinformationaboutoutgoingedges Insynchronousalgorithm whenanodetestsitsedges itknowsthatitsneighborsarealreadyuptothesamelevel andhaveup to dateinformationabouttheircomponent Inasynchronousversion neighborscouldlagbehind theymightbeinsamecomponentbutnotyetknowthis Less balanced combinationofcomponents Insynchronousalgorithm levelkcomponentshave 2knodes andlevelk 1componentsareconstructedfromatleasttwolevelkcomponents Inasynchronousversion componentsatdifferentlevelscouldbecombined Canleadtomoremessagesoverall 53 RunningtheAlgasynchronously Problemsarise Inaccurateinformationaboutoutgoingedges Less balanced combinationofcomponents Concurrentoverlappingsearches convergecasts Whennodesareoutofsynch concurrentsearchesforMWOEscouldinterferewitheachother we llseethis Timebound Theseproblemsresultfromnodesbeingout of synch atdifferentlevels Wecouldtrytosynchronizelevels butthismustbedonecarefully soasnottohurtthetimecomplexitytoomuch 54 GHSalgorithm Samebasicideasasbefore Formcomponents combinealongMWOEs Withinanycomponent processescooperatetofindcomponentMWOE Broadcastfromleader convergecast etc 55 GHSalgorithm Introducesynchronizationtopreventnodesfromgettingtoofaraheadoftheirneighbors Associatea level witheachcomponent asbefore Numberofnodesinalevelkcomponent 2k Now eachlevelk 1componentwillbe initially formedfromexactlytwolevelkcomponents Levelnumbersareusedforsynchronization andindeterminingwhoisinthesamecomponent Complexity Messages O E nlogn Time O nlogn d l 56 GHSalgorithm Combinepairsofcomponentsintwoways mergingandabsorbing Merging CandC havesamelevelk andhaveacommonMWOE ResultisanewmergedcomponentC withlevelk 1 57 GHSalgorithm Absorbing level C level C andC sMWOEleadstoC ResultistoabsorbCintoC Notcreatinganewcomponent justaddingCtoexistingC C catchesup withthemoreadvancedC Absorbingischeap local Mergingandabsorbingensurethatthenumberofnodesinanylevelkcomponent 2k MergingandabsorbingarebothallowableoperationsinfindingMST becausetheyareallowedbythegeneraltheoryforMSTs 58 Liveness Q Whyaremergingandabsorbingsufficienttoensurethattheconstructioniseventuallycompleted Lemma Afteranyallowablefinitesequenceofmergesandabsorbs eithertheforestconsistsofonetree sowe redone orsomemergeorabsorbisenabled 59 Liveness Proof Considerthecurrent componentdigraph Nodes componentsDirectededgescorrespondtoMWOEsThentheremustbesomepairC C whoseMWOEspointtoeachother Why TheseMWOEsmustbethesameedge Why Cancombine usingeithermergeorabsorb Ifsamelevel merge elseabsorb So mergingandabsorbingareenough Now howtoimplementthemwithadistributedalgorithm 60 Componentnamesandleaders Foreverycomponentwithlevel 1 definethecoreedgeofthecomponent stree Definedintermsofthemergeandabsorboperationsusedtoconstructthecomponent Aftermerge UsethecommonMWOE Afterabsorb Keeptheoldcoreedgeofthehigher levelcomponent Theedgealongwhichthemostrecentmergeoccurred Componentname core level Leader Endpointofcoreedgewithhigherid 61 Determiningifanedgeisoutgoing Supposeiwantstoknowiftheedge i j isoutgoingfromi scurrentcomponent Atthatpoint i scomponentnameinfoisup to date Componentisin searchmode ihasreceivedinitiatemessagefromtheleader whichcarriedcomponentname Soisendsjatestmessage Threecases 62 Determiningifanedgeisoutgoing Threecases Ifj scurrent core level isthesameasi s thenjknowsthatjisinthesamecomponentasi Ifj s core level isdifferentfromi sandj slevelis i s thenjknowsthatjisinadifferentcomponentfromi Componenthasonlyonecoreperlevel Nooneinthesamecomponentcurrentlyhasahigherlevelthanidoes sincethecomponentisstillsearchingforitsMWOE Ifj slevelis i s thenjdoesn tknowifitisinthesameoradifferentcomponent Soitdoesn tyetrespond waitstocatchuptoi slevel 63 Liveness again Q Cantheextradelaysimposedhereaffecttheprogressargument No Wecanredotheprogressargument thistimeconsideringonlythosecomponentswiththelowestcurrentlevelk AllprocessesinthesecomponentsmustsucceedindeterminingtheirMWOEs sothesecomponentssucceedindeterminingthecomponentMWOE Ifanyoftheselevelkcomponents MWOEsleadstoahigherlevel canabsorb Ifnotthenallleadtootherlevelkcomponents soasbefore wemusthavetwocomponentsthatpointtoeachother socanmerge 64 InterferenceamongconcurrentMWOEsearches SupposeCgetsabsorbedintoC viaanedgefromitoj whileC isworkingondeterminingitsMWOE Twocases jhasnotyetreporteditslocalmwoewhentheabsorboccurs Thenit snottoolatetoincludeCinthesearchfortheMWOEofC SojforwardstheinitiatemessageintoC jhasalreadyreporteditslocalmwoe Thenit stoolatetoincludeCinthesearch Butitdoesn tmatter theMWOEforthecombinedcomponentcan tbeoutgoingfromanodeinCanyhow 65 Afewdetails Specificmessages initiate BroadcastfromleadertofindMWOE piggybackscomponentname report ConvergecastMWOEresponsesbacktoleader test Askswhetheranedgeisoutgoingfromthecomponent accept reject Answers changeroot SentfromleadertoendpointofMWOE connect SentacrosstheMWOE toconnectcompon