2.2分布式算法 2 领导者选举ppt课件

分布协同计算基础,第二章:分布式算法(2)-领导者选举张锡哲副教授计算机应用技术研究所东北大学信息科学与工程学院,选举问题,Ifweareusingoneprocessasacoordinatorforasharedresourcehowdoweselectthatoneprocess?Often,thereisnoownerormasterthatisautomaticallyconsideredascoordinator,选举问题,Manydistributedsystemsareclientserverbased,withoneserver/coordinator(leader),andmultipleclientsWhathappensiftheleaderfails?ElectanewoneCannotassumeonlyoneprocessdetectsthecrashTheelectionshouldgetalloftheprocessestoagreethatonenodeisaleader,选举谁？,Basicidea:Ifeachprocesshasauniqueidentity,andtheidentitiesareorderedElectthenon-crashednodewithminimum/maximumidentity,选举算法的应用,whenacentralizedalgorithmistobeexecutedinadistributedsystemforinstance,afterasystemcrashwhenitisunknownwhichnodesareworking,什么是选举,“tostartfromaconfigurationwhereallprocessesareinthesamestateandarriveataconfigurationwhereexactlyoneprocessistheleader”Goal:toobtainlowmessagecomplexity,选举算法的定义,Formally,analgorithmisanelectionalgorithmiff:EachprocesshasthesamelocalalgorithmThealgorithmisdecentralizedItcanbeinitiatedbyanynumberofprocessesinthesystemItreachesaterminalconfiguration,andineachreachableterminalconfigurationoneprocessisinstateleaderandtherestareinthestatelost,假设,FullyasynchronoussystemNoglobalclock,transmissiontimesarbitraryEveryprocesshasauniqueidentityIdentitiesaretotallyorderedBecausewehavefinitenumberofprocesses:MaxidentityandMinidentityavailable(extremevalues),Remark,Processorsareinoneofthreestates:undecided,leader,lostInitiallyeveryprocessisintheundecidedstateWhenleavingtheundecidedstate,aprocessorgoesintoaterminatedstate(leaderorlost),环网上的选举,单向环双向环LeLann77,O(N2)Chang-Roberts79(N2),(NlogN)Hirshbergetal.80(NlogN)Petersen/Dolevetal.82(NlogN),11,环网上的选举,ThefirsteverelectionalgorithmwasdoneforringsbyLeLannSimpleidea:LeteveryinitiatorsendatokenwiththeiridentityaroundthewholeringNodesarenotallowedtoinitiateaftertheyreceiveatoken(example),12,Example,Nodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example),3,5,1,9,8,2,6,7,initiator,13,Example,Nodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example),3,5,1,9,8,2,6,7,initiator,14,Example,Nodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example),3,5,1,9,8,2,6,7,initiator,notallowedtoinitiate,15,Example,Nodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example),3,5,1,9,8,2,6,7,initiator,notallowedtoinitiate,notallowedtoinitiate,16,Example,Nodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example),3,5,1,9,8,2,6,7,initiator,notallowedtoinitiate,notallowedtoinitiate,notallowedtoinitiate,17,Example,Nodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example),3,5,1,9,8,2,6,7,initiator,notallowedtoinitiate,notallowedtoinitiate,initiator,notallowedtoinitiate,18,Example,Nodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example),3,5,1,9,8,2,6,7,initiator,notallowedtoinitiate,notallowedtoinitiate,initiator,notallowedtoinitiate,notallowedtoinitiate,19,Example,Nodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example),3,5,1,9,8,2,6,7,initiator,notallowedtoinitiate,notallowedtoinitiate,initiator,notallowedtoinitiate,notallowedtoinitiate,notallowedtoinitiate,20,LeLannsringelection,Wheneveranodereceivesbackitsid,ithasseeneveryotherinitiatorsidAssumingFIFOchannelsLeteverynodekeepalistofeveryidentifierseen(listp)Ifnon-initiator,state=lostimmediatelyIfinitiator,whenownidreceived:state=leaderifminlistp=pstate=lostotherwise,LeLannsAlgorithm,Initiallyonlyknowmyself,Sendmyid,andwait,Termination:didwewinorlose,22,MessageComplexity,Worstcaseiseverynodeisinitiator(N)EveryinitiatorsendsNmessagesGivesatotalofN2messages,23,时间复杂度,AssumelastinitiatorfstartsattimeN-1fterminatesafteritstokenhascirculatedthering,NstepsTimecomplexity2N-1,3,5,1,9,8,2,6,7,initiator,lastinitiator,24,Chang-Roberts算法,ChangandRobertscameupwithasmallimprovementIdea:Whenanodereceivesatokenwithlargeridthanitself,whyshoulditkeepforwardingit?Itisawaste,weknowthatthatidwillneverwin!Letsdroptokenswithlargeridsthanourselves!,25,Howtomakeitwork,Butifwedropatokenwithids,nodeswillbewaitingforeveronitstokentocomebackHowdowesolvethat?,26,Howtomakeitwork,Ifnodestokenisdropped,itwillanywayreceiveanothertokenwithloweridInthatcase,sshouldsetstate=lost,ChangandRobertsAlgo,Initiatorsendsitstoken,Whilenotleader,keepreceivingtokens,Ifmytokencomes,thenIwon,28,ChangRoberts-Example,Nodes1,3,6areinitiators,6,9,1,3,Non-initiator,Lost,Won,6,Initiator,1,3,29,0,1,7,5,3,2,6,4,ChangRobertsAnalysis,WorstcasecomplexitysameasLeLannsTimeComplexity:2N-1MessageComplexity:O(N2)ConsideredasortedringwithNinitiators,8times,7times,6times,5times,4times,3times,2times,1times,30,Furtherimprovements?,HSRingElection,HirschbergSinclairAlgorithm(ringmodification)O(N2)isalotofmessages.HereisamodificationthatisO(NlogN).Assumptions:theringsizecanbeunknown.Thecommunicationsmustbebidirectional.Allnodesstartmoreorlessatthesametime.Eachnodeoperatesinphasesandsendsouttokens.Thetokenscarryhop-countsanddirectionflagsinadditiontotheIDofthesender.,3,ID=3,2hopsclockwise,ID=3,2hopscounterclckws,HSRingElection,Phasesarenumbered0,1,2,3,Ineachphase,k,nodejsendsouttokensujcontainingitsIDinbothdirections.Thetokenstravel2khopsthenreturntotheiroriginj.Ifbothtokensmakeitback,processjcontinueswiththenextphase(incrementsk).Ifbothtokensdonotmakeitback,processjsimplywaitstobetoldwhotheresultsoftheelection.,3,3,x,x,Trajectoryofsuccessivetokensoriginatingatprocessi,HSRingElection,6-34,HSRingElection,Ifaprocessmreceivesatokenujgoingintheoutbounddirection,itcomparesthetokensIDwithitsown.IfithasalargerID,itsimplydiscardsthetoken.IfithasasmallerID,itrelaysthetokenasrequested.IfitisequaltothetokenID,ithasreceiveditsowntokenintheoutbounddirection,sothetokenhasgonecleararoundtheringandtheprocessdeclaresitselfleader.Allprocessesalwaysrelayinboundtokens.,4,ID=3,2hopsclockwise,非形式化描述,Eachprocessioperatesinphases0,1,2,.Ineachphasel,processisendsouttokenscontainingitsUIDuiinbothdirections.Theseareintendedtotraveldistance2l,thenreturntotheirorigini.Ifbothtokensmakeitbacksafely,processicontinueswiththefollowingphase.However,thetokensmightnotmakeitbacksafely.Whileauitokenisproceedingintheoutbounddirection,eachotherprocessjonuispathcomparesuiwithitsownUIDuj.Ifuiuj,thenjrelaysui.Ifui=uj,thenitmeansthatprocessjhasreceiveditsownUIDbeforethetokenhasturnedaround,soprocessjelectsitselfastheleader.Allprocessalwaysrelayalltokensintheinbounddirection.,HSRingElection,一个例子,Fordemonstrationpurposes,wewillignoretheasynchronousnatureofthesystemandassumethatallnodesoperateatthesamespeedandatthesametime.InitialnetworkconfigurationwithUIDvaluesinblue.,Thealgorithmstartsinphase0,andeachnodewillsendanoutboundmessagetoitsneighbors.Themessageisintendedtotraveladistanceof20hops.,ThenodesthatreceivedaninboundmessagewithitsOWNUIDfrombothneighborsarequalifiedtoproceedtothenextphase.Theyareindicatedingray.,Nowweadvancetophase1,andeachactivenodewillsendanoutboundmessagetoitsneighbors.Themessagethistimeisintendedtotraveladistanceof21hops.Thestraightarrowsrepresentsoutboundandthecurvedarrowsrepresentsinbound.,Phase2.Onlynode4isactiveinphase2.Itistheonlynodethatcaninitiateamessage.Themessageisintendedtotravel22hops.Outgoingmessagessentbynode4intheclockwisedirectionareinpink.Outgoingmessagesinthecounter-clockwisedirectionareingreen.Straightlinesareoutgoingmessages,curvedlinesareincoming.,Phase3.Onlynode4isactiveinphase2.Itistheonlynodethatcaninitiateamessage.Itsmessagesareintendedtotravel23hops.,43,AnalysisofHSRingElection,MessageComplexity:Eachmsgbelongstoaparticularphaseandisinitiatedbyaparticularproc.Probedistanceinphaseiis2iNumberofmsgsinitiatedbyaproc.inphaseiisatmost4*2i(probesandrepliesinbothdirections),44,AnalysisofHSRingElection,Howmanyprocs.initiateprobesinphasei?Fori=0,everyproc.doesFori0,everyproc.thatisawinnerinphasei-1doeswinnermeanshaslargestidinits2i-1neighborhood,45,AnalysisofHSRingElection,Maximumnumberofphasei-1winnersoccurswhentheyarepackedasdenselyaspossible:totalnumberofphasei-1winnersisatmostn/(2i-1+1),46,AnalysisofHSRingElection,Howmanyphasesarethere?Ateachphasethenumberof(phase)winnersiscutinhalf(atleast)Soafteratmostlog2nphases,onlyonewinnerisleft.,47,AnalysisofHSRingElection,Totalnumberofmessagesissum,overallphases,ofnumberofwinnersatthatphasetimesnumberofmessagesoriginatedbythatwinner:,phase0msgs,msgsforphases1tologn,terminationmsgs,Franklin算法,AllactiveidentitiescomparethemselveswiththeclosestactiveneighbortotheleftandtotherightTheidentityremainsactiveifitisthelocalmin.,Peterson/Dolev-Klawe-Rodeh,PetersonLeader-ElectionAlgorithm,ArbitraryelectionofleaderusingcomparisonofUIDsusingunidirectionalcommunicationAlgorithmrunsinphasesinwhicheachprocessisassignedtoactiveorpassivemode(allprocessesstartasactive)ThenumberofactiveprocessesisreducedbyafactoroftwoduringeachphaseSummary:AtthebeginningofeachphaseeachactiveprocessisendsitsUIDtwostepsclockwise.ThenprocessicomparesitsownUIDtothetwoUIDsitreceived.Ifui-1ui-2andui-11.TherecanbeatmostlogNphasestoreachoneactiveprocess.Duringaphaseeveryprocesssends(andreceive)twomessages,andonthelastphasetheloneactiveprocesssendsonemessagewhichisrelayedaroundtothemaximumforatotalof2NlogN+N.,54,55,同步环中的选举,Hereisasimplealgorithm.Grouproundsintophases,eachphasecontainingnroundsInphasei,theprocessorwithidi,ifthereisone,sendsamessagearoundtheringandiselected.,56,ExampleofSimpleSynchronousAlgorithm,n=4,thesmallestidis7.Inphases0through6(correspondingtorounds1through28),nomessageiseversent.Atbeginningofphase7(round29),processorwithid7sendsmessagewhichisforwardedaroundthering.,Reliesonsynchronyandknowingn,57,AnalysisofSimpleAlgorithm,Correctness:Easytosee.Messagecomplexity:O(n),whichisoptimalTimecomplexity:O(n*m),wheremisthesmallestidinthering.notboundedbyanyfunctionofn!,58,AnotherSynchronousAlgorithm,Worksinaslightlyweakermodelthantheprevioussynchronousalgorithm:processorsmightnotallstartatsameround;aprocessoreitherwakesupspontaneouslyorwhenitfirstgetsamessageuniform(doesnotrelyonknowingn),59,AnotherSynchronousAlgorithm,Aprocessorthatwakesupspontaneouslyisactive;sendsitsidinafastmessage(oneedgeperround)Aprocessorthatwakesupwhenreceivingamsgisrelay;neverinthecompetitionAfastmessagecarryingidmbecomesslowifitreachesanactiveprocessor;startstravelingatoneedgeper2mroundsAprocessoronlyforwardsamsgwhoseidissmallerthananyidishaspreviouslysentIfaproc.getsitsownidback,electsself,60,AnalysisofSynchronousAlgorithm,Correctness:convinceyourselfthattheactiveprocessorwithsmallestidiselected.Messagecomplexity:Winnersmsgisthefastest.Whileittraversesthering,othermsgsareslower,sotheyareovertakenandstoppedbeforetoomanymessagesaresent.,61,MessageComplexity,Dividemsgsintothreekinds:fastmsgsslowmsgssentwhiletheleadersmsgisfastslowmsgssentwhiletheleadersmsgisslowNext,countthenumberofeachtypeofmsg.,62,Showthatnoprocessorforwardsmorethanonefastmsg:S