分布式算法完整5ppt课件

.,1,AlgorithmsinGeneralAsynchronousNetworks,沈卓炜zwshen九龙湖校区计算机楼347房间Tel:52090919133909229522011年3月,.,2,Leaderelectioningeneralasynchronousnetworks,Undirectedgraphs.CangetasynchronousversionofsynchronousFloodMaxalgorithm:Simulateroundswithcounters.Needtoknowdiameterfortermination.FloodMaxalgorithm:Everyround:SendmaxUIDseentoallneighbors.Stopafterdiamrounds.ElectselfiffownUIDismaxseen.,.,3,Leaderelectioningeneralasynchronousnetworks,Wellseebetterasynchronousalgorithmslater:Dontneedtoknowdiameter.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:AllowonlydistanceestimatesD.Messages:O(D|E|);Time:O(diamD(l+d),.,37,AsynchBFS,Termination:Nooneknowswhenthisisdone,socantproduceparentoutputs.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:eachnodeatdistancekknowsitsparent,andeachnodeatdistancek-1alsoknowsitschildren.i0broadcastsnewphasemessagealongtreeedges,todistancekprocesses.Eachofthesesendssearchmessagetoallnbrsexceptitsparent.Whenanynon-i0processreceivesfirstsearchmessage,setsparent:=senderandsendsapositiveack;sendsnacksforsubsequentsearchmsgs.Whendistancekprocessreceivesacks/nacksforallitssearchmessages,designatesnodesthatsentpostiveacksasitschildren.Thendistancekprocessesconvergecastbacktoi0alongdepthktreetosaythattheyredone;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,Possibledistanceestimatesforikare2k1,2k2,0.Moreover,ikcantakeonalltheseestimatesinsequence:First,messagestraverseupperlinks,2k1.Thenlastlowermessagearrivesatik,2k2.Thenlowermessageik-2ik-1arrives,reducesik-1sestimateby2,messageik-1ikarrivesonupperlinks,2k3.Etc.Countdowninbinary.Ifthishappensquickly,getpileupof2ksearchmessagesinCk,k+1.,.,47,ShortestPaths,Moral:Unrestrainedasynchronycancauseproblems.Returntothisproblemafterwehavebettersynchronizationmethods.Now,anothergoodillustrationoftheproblemsintroducedbyasynchrony:,.,48,Minimumspanningtree,Assumptions:G=(V,E)connected,undirected.Weightededges,weightsknowntoendpointprocesses,weightsdistinct.UIDsProcessesdontknown,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,notretestingsameedgeonceitsrejected.Q:Howtorunthisalgorithmasynchronously?,.,52,RunningtheAlgasynchronously,Problemsarise:Inaccurateinformationaboutoutgoingedges:Insynchronousalgorithm,whenanodetestsitsedges,itknowsthatitsneighborsarealreadyuptothesamelevel,andhaveup-to-dateinformationabouttheircomponent.Inasynchronousversion,neighborscouldlagbehind;theymightbeinsamecomponentbutnotyetknowthis.Less“balanced”combinationofcomponents:Insynchronousalgorithm,levelkcomponentshave2knodes,andlevelk+1componentsareconstructedfromatleasttwolevelkcomponents.Inasynchronousversion,componentsatdifferentlevelscouldbecombined.Canleadtomoremessagesoverall.,.,53,RunningtheAlgasynchronously,Problemsarise:Inaccurateinformationaboutoutgoingedges:Less“balanced”combinationofcomponents:Concurrentoverlappingsearches/convergecasts:Whennodesareoutofsynch,concurrentsearchesforMWOEscouldinterferewitheachother(wellseethis).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.Numberofnodesinalevelkcomponent2k.Now,eachlevelk+1componentwillbe(initially)formedfromexactlytwolevelkcomponents.Levelnumbersareusedforsynchronization,andindeterminingwhoisinthesamecomponent.Complexity:Messages:O(|E|+nlogn)Time:O(nlogn(d+l),.,56,GHSalgorithm,Combinepairsofcomponentsintwoways,mergingandabsorbing.Merging:CandChavesamelevelk,andhaveacommonMWOE.ResultisanewmergedcomponentC,withlevelk+1.,.,57,GHSalgorithm,Absorbing:level(C)level(C),andCsMWOEleadstoC.ResultistoabsorbCintoC.Notcreatinganewcomponent,justaddingCtoexistingC.C“catchesup”withthemoreadvancedC.Absorbingischeap,local.Mergingandabsorbingensurethatthenumberofnodesinanylevelkcomponent2k.MergingandabsorbingarebothallowableoperationsinfindingMST,becausetheyareallowedbythegeneraltheoryforMSTs.,.,58,Liveness,Q:Whyaremergingandabsorbingsufficienttoensurethattheconstructioniseventuallycompleted?Lemma:Afteranyallowablefinitesequenceofmergesandabsorbs,eithertheforestconsistsofonetree(soweredone),orsomemergeorabsorbisenabled.,.,59,Liveness,Proof:Considerthecurrent“componentdigraph”:Nodes=componentsDirectededgescorrespondtoMWOEsThentheremustbesomepairC,CwhoseMWOEspointtoeachother.(Why?)TheseMWOEsmustbethesameedge.(Why?)Cancombine,usingeithermergeorabsorb:Ifsamelevel,merge,elseabsorb.So,mergingandabsorbingareenough.Now,howtoimplementthemwithadistributedalgorithm?,.,60,Componentnamesandleaders,Foreverycomponentwithlevel1,definethecoreedgeofthecomponentstree.Definedintermsofthemergeandabsorboperationsusedtoconstructthecomponent:Aftermerge:UsethecommonMWOE.Afterabsorb:Keeptheoldcoreedgeofthehigher-levelcomponent.“Theedgealongwhichthemostrecentmergeoccurred.”Componentname:(core,level)Leader:Endpointofcoreedgewithhigherid.,.,61,Determiningifanedgeisoutgoing,Supposeiwantstoknowiftheedge(i,j)isoutgoingfromiscurrentcomponent.Atthatpoint,iscomponentnameinfoisup-to-date:Componentisin“searchmode”.ihasreceivedinitiatemessagefromtheleader,whichcarriedcomponentname.Soisendsjatestmessage.Threecases:,.,62,Determiningifanedgeisoutgoing,Threecases:Ifjscurrent(core,level)isthesameasis,thenjknowsthatjisinthesamecomponentasi.Ifjs(core,level)isdifferentfromisandjslevelisis,thenjknowsthatjisinadifferentcomponentfromi.Componenthasonlyonecoreperlevel.Nooneinthesamecomponentcurrentlyhasahigherlevelthanidoes,sincethecomponentisstillsearchingforitsMWOE.Ifjslevelisis,thenjdoesntknowifitisinthesameoradifferentcomponent.Soitdoesntyetrespond-waitstocatchuptoislevel.,.,63,Liveness,again,Q:Cantheextradelaysimposedhereaffecttheprogressargument?No:Wecanredotheprogressargument,thistimeconsideringonlythosecomponentswiththelowestcurrentlevelk.AllprocessesinthesecomponentsmustsucceedindeterminingtheirMWOEs,sothesecomponentssucceedindeterminingthecomponentMWOE.IfanyoftheselevelkcomponentsMWOEsleadstoahigherlevel,canabsorb.Ifnotthenallleadtootherlevelkcomponents,soasbefore,wemusthavetwocomponentsthatpointtoeachother;socanmerge.,.,64,InterferenceamongconcurrentMWOEsearches,SupposeCgetsabsorbedintoCviaanedgefromitoj,whileCisworkingondeterminingitsMWOE.Twocases:jhasnotyetreporteditslocalmwoewhentheabsorboccurs.ThenitsnottoolatetoincludeCinthesearchfortheMWOEofC.SojforwardstheinitiatemessageintoC.jhasalreadyreporteditslocalmwoe.ThenitstoolatetoincludeCinthesearch.Butitdoesntmatter:theMWOEforthecombinedcomponentcantbeoutgoingfromanodeinCanyhow!,.,65,Afewdetails,Specificmessages:initiate:BroadcastfromleadertofindMWOE;piggybackscomponentname.report:ConvergecastMWOEresponsesbacktoleader.test:Askswhetheranedgeisoutgoingfromthecomponent.accept/reject:Answers.changeroot:SentfromleadertoendpointofMWOE.connect:SentacrosstheMWOE,toconnectcomponents.Wes