（精选）分布式算法.ppt

AlgorithmsinGeneralAsynchronousNetworks,沈卓炜zwshen九龙湖校区计算机楼347房间Tel:52090919133909229522011年3月,1,Leaderelectioningeneralasynchronousnetworks,Undirectedgraphs.CangetasynchronousversionofsynchronousFloodMaxalgorithm:Simulateroundswithcounters.Needtoknowdiameterfortermination.FloodMaxalgorithm:Everyround:SendmaxUIDseentoallneighbors.Stopafterdiamrounds.ElectselfiffownUIDismaxseen.,2,2020/5/22,Leaderelectioningeneralasynchronousnetworks,Wellseebetterasynchronousalgorithmslater:Dontneedtoknowdiameter.Lowermessagecomplexity.Dependontechniquessuchas:Breadth-firstsearchConvergecastusingaspanningtreeSynchronizerstosimulatesynchronousalgorithmsConsistentglobalsnapshotstodetecttermination,3,2020/5/22,Spanningtreeandsearching,Spanningtreesareusedforcommunication,e.g.,broadcast/convergecastStartwiththesimpletaskofsettingupsome(arbitrary)spanningtreewitha(given)rooti0.Assume:Undirected,connectedgraph(i.e.,bidirectionalcommunication).Rooti0Sizeanddiameterunknown.UIDs,withcomparisons.Canidentifyin-andout-edgestosameneighbor.,4,2020/5/22,Spanningtreeandsearching,Require:Eachprocessshouldoutputitsparentintree,withaparentoutputaction.Startingpoint:SynchBFSalgorithm:i0floodssearchmessage;parentofanodeisthefirstnodefromwhichitreceivesasearchmessage.Tryrunningthesamealgorithminasynchronousnetwork.Stillyieldsspanningtree,butnotnecessarilybreadth-firsttree.,5,2020/5/22,AsynchSpanningtree,Processi,6,2020/5/22,Asynchronousspanningtree,7,2020/5/22,Asynchronousspanningtree,S,8,2020/5/22,Asynchronousspanningtree,S,9,2020/5/22,Asynchronousspanningtree,S,10,2020/5/22,Asynchronousspanningtree,S,S,11,2020/5/22,Asynchronousspanningtree,S,12,2020/5/22,Asynchronousspanningtree,S,S,S,13,2020/5/22,Asynchronousspanningtree,14,2020/5/22,AsynchSpanningtree,ComplexityMessages:O(|E|)Time:diam(l+d)+lAnomaly:Pathsmaybelongerthandiameter!Messagesmaytravelfasteralonglongerpaths,inasynchronousnetworks.,15,2020/5/22,ApplicationofAsynchSpanningtree,SimilartosynchronousBFSMessagebroadcast:Piggybackonsearchmessage.Childpointers:Addresponsestosearchmessages,easybecauseofbidirectionalcommunication.Useprecomputedtreeforbcast/convergecastNowthetiminganomalyarisesO(h(l+d)timecomplexity.O(|E|)messagecomplexity.,h=heightoftree;mayben,16,2020/5/22,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.,17,2020/5/22,Moreapplications,Asynchronousbroadcast/convergecast:Canalsoconstructspanningtreewhileusingittobroadcastmessageandalsotocollectresponses.E.g.,totelltherootwhenthebcastisdone,ortocollectaggregateddata.Complexity:O(|E|)messagecomplexity.O(n(l+d)timecomplexity,timinganomaly.Electleaderwhennodeshavenoinfoaboutthenetwork(noknowledgeofn,diam,etc.;noroot,nospanningtree),18,2020/5/22,Breadth-firstspanningtree,Assume(sameasabove):Undirected,connectedgraph(i.e.,bidirectionalcommunication).Rooti0.Sizeanddiameterunknown.UIDs,withcomparisons.Require:Eachprocessshouldoutputitsparentinabreadth-firstspanningtree.,19,2020/5/22,Breadth-firstspanningtree,Inasynchronousnetworks,modifiedSynchBFSdoesnotguaranteethatthespanningtreeconstructedisbreadth-first.Longpathsmaybetraversedfasterthanshortones.Canmodifyeachprocesstokeeptrackofdistance,changeparentwhenithearsofshorterpath.Relaxationalgorithm(likeBellman-Ford).Mustinformneighborsofchanges.Eventually,treestabilizestoabreadth-firstspanningtree.,20,2020/5/22,AsynchBFS,21,2020/5/22,AsynchBFS,0,22,2020/5/22,AsynchBFS,0,0,23,2020/5/22,AsynchBFS,0,0,0,24,2020/5/22,AsynchBFS,1,0,0,25,2020/5/22,AsynchBFS,1,0,1,1,26,2020/5/22,AsynchBFS,1,0,1,3,2,1,1,27,2020/5/22,AsynchBFS,1,0,4,1,3,2,1,1,28,2020/5/22,AsynchBFS,1,0,4,1,3,2,1,1,4,4,29,2020/5/22,AsynchBFS,1,0,2,1,3,2,1,4,4,30,2020/5/22,AsynchBFS,1,0,2,5,1,3,2,1,4,2,31,2020/5/22,AsynchBFS,6,1,0,2,3,1,3,2,1,1,32,2020/5/22,AsynchBFS,6,1,0,2,2,1,3,2,1,1,33,2020/5/22,AsynchBFS,2,1,0,2,2,1,3,2,1,0,34,2020/5/22,AsynchBFS,1,1,0,2,2,1,3,2,1,35,2020/5/22,AsynchBFS,Complexity:Messages:O(n|E|)MaysendO(n)messagesoneachlink(oneforeachdistanceestimate).Time:O(diamn(l+d)(takingpileupsintoaccount).CanreducecomplexityifknowboundDondiameter:AllowonlydistanceestimatesD.Messages:O(D|E|);Time:O(diamD(l+d),36,2020/5/22,AsynchBFS,Termination:Nooneknowswhenthisisdone,socantproduceparentoutputs.Canaugmentwithacksforsearchmessages,convergecastbacktoi0.i0learnswhenthetreehasstabilized,tellseveryoneelse.Abittricky:Treegrowsandshrinks.Someprocessesmayparticipatemanytimes,astheylearnimprovements.Bookkeepingneeded.Complexity?,37,2020/5/22,LayeredBFS,Asynchronyleadstomanycorrections,whichleadtolotsofcommunication.Idea:Slowdowncommunication,growthetreeinsynchronizedphases.Inphasek,incorporateallnodesatdistancekfromi0.i0synchronizesbetweenincorporatingnodesatdistancekandk+1.Phase1:i0sendssearchmessagestoneighbors.Neighborssetdist:=1,sendackstoi0.,38,2020/5/22,LayeredBFS,Phasek+1:Assumephases1,karecompleted:eachnodeatdistancekknowsitsparent,andeachnodeatdistancek-1alsoknowsitschildren.i0broadcastsnewphasemessagealongtreeedges,todistancekprocesses.Eachofthesesendssearchmessagetoallnbrsexceptitsparent.Whenanynon-i0processreceivesfirstsearchmessage,setsparent:=senderandsendsapositiveack;sendsnacksforsubsequentsearchmsgs.Whendistancekprocessreceivesacks/nacksforallitssearchmessages,designatesnodesthatsentpostiveacksasitschildren.Thendistancekprocessesconvergecastbacktoi0alongdepthktreetosaythattheyredone;includeabitsayingwhethernewnodeswerefound.,39,2020/5/22,LayeredBFS,Terminates:Wheni0learns,insomephase,thatnonewnodeswerefound.ObviouslyproducesBFStree.Complexity:Messages:O(|E|+ndiam)Time:Usesimplifiedanalysis:NeglectinglocalcomputationtimelAssumingthateverymessageinachannelisdeliveredintimed(ignoringcongestiondelays).O(diam2d),Eachedgeexploredatmostonceineachdirectionbysearch/ack.,Eachtreeedgetraversedatmostonceineachphasebynewphase/convergecast.,40,2020/5/22,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.,41,2020/5/22,ShortestPaths,Assumptions:SameasforBFS,plusedgeweights.weight(i,j),nonnegativereal,sameinbothdirections.Require:Outputshortestdistanceandparentinshortest-pathstree.UseBellman-FordasynchronouslyUsedtoestablishroutesinARPANET1969-1980.CanaugmentwithconvergecastasforBFS,fortermination.Butworst-casecomplexityisverybad,42,2020/5/22,AsynchBellmanFord,43,2020/5/22,AsynchBellmanFord,Termination:Useconvergecast(asforAsynchBFS).Complexity:O(n!)simplepathsfromi0toanyothernode,whichisO(nn).SothenumberofmessagessentonanychannelisO(nn).Somessagecomplexity=O(nn|E|),timecomplexity=O(nnn(l+d).,44,2020/5/22,AsynchBellmanFord,Complexity:Q:Arethemessageandtimecomplexityreallyexponentialinn?A:Yes:Insomeexecutionofnetworkbelow,iksends2kmessagestoik+1,somessagecomplexityis(2n/2)andtimecomplexityis(2n/2d).,45,2020/5/22,Exponentialtime/messagecomplexity,Possibledistanceestimatesforikare2k1,2k2,0.Moreover,ikcantakeonalltheseestimatesinsequence:First,messagestraverseupperlinks,2k1.Thenlastlowermessagearrivesatik,2k2.Thenlowermessageik-2ik-1arrives,reducesik-1sestimateby2,messageik-1ikarrivesonupperlinks,2k3.Etc.Countdowninbinary.Ifthishappensquickly,getpileupof2ksearchmessagesinCk,k+1.,46,2020/5/22,ShortestPaths,Moral:Unrestrainedasynchronycancauseproblems.Returntothisproblemafterwehavebettersynchronizationmethods.Now,anothergoodillustrationoftheproblemsintroducedbyasynchrony:,47,2020/5/22,Minimumspanningtree,Assumptions:G=(V,E)connected,undirected.Weightededges,weightsknowntoendpointprocesses,weightsdistinct.UIDsProcessesdontknown,diam.Canidentifyin-andout-edgestosameneighbor.Input:wakeupactions,occurringatanytimeatoneormorenodes.Processwakesupwhenitfirstreceiveseitherawakeupinputoraprotocolmessage.,48,2020/5/22,Minimumspanningtree,Assumptions:Requires:ProduceMST,whereeachprocessknowswhichofitsincidentedgesbelongtothetree.Guaranteedtobeunique,becauseofuniqueweights.Gallager-Humblet-Spiraalgorithm,49,2020/5/22,Recallsynchronousalgorithm,Proceedsinphases(levels).Aftereachphase,wehaveaspanningforest,inwhicheachcomponenttreehasaleader.Ineachphase,eachcomponentfindsminweightoutgoingedge(MWOE),thencomponentsmergeusingallMWOEstogetcomponentsfornextphase.,50,2020/5/22,Synchronousalgorithm,Complexityisgood:Messages:O(nlogn+|E|)Time(rounds):O(nlogn)Lowmessagecomplexitydependsonthewaynodestesttheirincidentedges,inorderofweight,notretestingsameedgeonceitsrejected.Q:Howtorunthisalgorithmasynchronously?,51,2020/5/22,RunningtheAlgasynchronously,Problemsarise:Inaccurateinformationaboutoutgoingedges:Insynchronousalgorithm,whenanodetestsitsedges,itknowsthatitsneighborsarealreadyuptothesamelevel,andhaveup-to-dateinformationabouttheircomponent.Inasynchronousversion,neighborscouldlagbehind;theymightbeinsamecomponentbutnotyetknowthis.Less“balanced”combinationofcomponents:Insynchronousalgorithm,levelkcomponentshave2knodes,andlevelk+1componentsareconstructedfromatleasttwolevelkcomponents.Inasynchronousversion,componentsatdifferentlevelscouldbecombined.Canleadtomoremessagesoverall.,52,2020/5/22,RunningtheAlgasynchronously,Problemsarise:Inaccurateinformationaboutoutgoingedges:Less“balanced”combinationofcomponents:Concurrentoverlappingsearches/convergecasts:Whennodesareoutofsynch,concurrentsearchesforMWOEscouldinterferewitheachother(wellseethis).Timebound:Theseproblemsresultfromnodesbeingout-of-synch,atdifferentlevels.Wecouldtrytosynchronizelevels,butthismustbedonecarefully,soasnottohurtthetimecomplexitytoomuch.,53,2020/5/22,GHSalgorithm,Samebasicideasasbefore:Formcomponents,combinealongMWOEs.Withinanycomponent,processescooperatetofindcomponentMWOE.Broadcastfromleader,convergecast,etc.,54,2020/5/22,GHSalgorithm,Introducesynchronizationtopreventnodesfromgettingtoofaraheadoftheirneighbors.Associatea“level”witheachcomponent,asbefore.Numberofnodesinalevelkcomponent2k.Now,eachlevelk+1componentwillbe(initially)formedfromexactlytwolevelkcomponents.Levelnumbersareusedforsynchronization,andindeterminingwhoisinthesamecomponent.Complexity:Messages:O(|E|+nlogn)Time:O(nlogn(d+l),55,2020/5/22,GHSalgorithm,Combinepairsofcomponentsintwoways,mergingandabsorbing.Merging:CandChavesamelevelk,andhaveacommonMWOE.ResultisanewmergedcomponentC,withlevelk+1.,56,2020/5/22,GHSalgorithm,Absorbing:level(C)level(C),andCsMWOEleadstoC.ResultistoabsorbCintoC.Notcreatinganewcomponent,justaddingCtoexistingC.C“catchesup”withthemoreadvancedC.Absorbingischeap,local.Mergingandabsorbingensurethatthenumberofnodesinanylevelkcomponent2k.MergingandabsorbingarebothallowableoperationsinfindingMST,becausetheyareallowedbythegeneraltheoryforMSTs.,57,2020/5/22,Liveness,Q:Whyaremergingandabsorbingsufficienttoensurethattheconstructioniseventuallycompleted?Lemma:Afteranyallowablefinitesequenceofmergesandabsorbs,eithertheforestconsistsofonetree(soweredone),orsomemergeorabsorbisenabled.,58,2020/5/22,Liveness,Proof:Considerthecurrent“componentdigraph”:Nodes=componentsDirectededgescorrespondtoMWOEsThentheremustbesomepairC,CwhoseMWOEspointtoeachother.(Why?)TheseMWOEsmustbethesameedge.(Why?)Cancombine,usingeithermergeorabsorb:Ifsamelevel,merge,elseabsorb.So,mergingandabsorbingareenough.Now,howtoimplementthemwithadistributedalgorithm?,59,2020/5/22,Componentnamesandleaders,Foreverycomponentwithlevel1,definethecoreedgeofthecomponentstree.Definedintermsofthemergeandabsorboperationsusedtoconstructthecomponent:Aftermerge:UsethecommonMWOE.Afterabsorb:Keeptheoldcoreedgeofthehigher-levelcomponent.“Theedgealongwhichthemostrecentmergeoccurred.”Componentname:(core,level)Leader:Endpointofcoreedgewithhigherid.,60,2020/5/22,Determiningifanedgeisoutgoing,Supposeiwantstoknowiftheedge(i,j)isoutgoingfromiscurrentcomponent.Atthatpoint,iscomponentnameinfoisup-to-date:Componentisin“searchmode”.ihasreceivedinitiatemessagefromtheleader,whichcarriedcomponentname.Soisendsjatestmessage.Threecases:,61,2020/5/22,Determiningifanedgeisoutgoing,Threecases:Ifjscurrent(core,level)isthesameasis,thenjknowsthatjisinthesamecomponentasi.Ifjs(core,level)isdifferentfromisandjslevelisis,thenjknowsthatjisinadifferentcomponentfromi.Componenthasonlyonecoreperlevel.Nooneinthesamecomponentcurrentlyhasahigherlevelthanidoes,sincethecomponentisstillsearchingforitsMWOE.Ifjslevelisis,thenjdoesntknowifitisinthesameoradifferentcomponent.Soitdoesntyetrespond-waitstocatchuptoislevel.,62,2020/5/22,Liveness,again,Q:Cantheextradelaysimposedhereaffecttheprogressargument?No:Wecanredotheprogressargument,thistimeconsideringonlythosecomponentswiththelowestcurrentlevelk.AllprocessesinthesecomponentsmustsucceedindeterminingtheirMWOEs,sothesecomponentssucceedindeterminingthecomponentMWOE.IfanyoftheselevelkcomponentsMWOEsleadstoahigherlevel,canabsorb.Ifnotthenallleadtootherlevelkcomponents,soasbefore,wemusthavetwocomponentsthatpointtoeachother;socanmerge.,63,2020/5/22,InterferenceamongconcurrentMWOEsearches,SupposeCgetsabsorbedintoCviaanedgefromitoj,whileCisworkingondeterminingitsMWOE.Twocases:jhasnotyetreporteditslocalmwoewhentheabsorboccurs.ThenitsnottoolatetoincludeCinthesearchfortheMWOEofC.SojforwardstheinitiatemessageintoC.jhasalreadyreporteditslocalmwoe.ThenitstoolatetoincludeCinthesearch.Butitdoesntmatter:theMWOEforthecombinedcomponentcantbeoutgoingfromanodeinCanyhow!,64,2020/5/22,Afewdetails,Specificmessages:initiate:BroadcastfromleadertofindMWOE;piggybackscomponentname.report:ConvergecastMWOEresponsesbacktoleader.test:Askswhetheranedgeisoutgoingfromthecomponent.accept/reject:Answers.changeroot:SentfromleadertoendpointofMWOE.connect:SentacrosstheMWOE,toconnectcompo