分布式算法领导者选举

分布协同计算基础第二章:分布式算法(2)

---领导者选举张锡哲副教授计算机应用技术研究所东北大学信息科学与工程学院选举问题Ifweareusingoneprocessasacoordinatorforasharedresource……howdoweselectthatoneprocess?Often,thereisnoownerormasterthatisautomaticallyconsideredascoordinator选举问题Manydistributedsystemsareclientserverbased,withoneserver/coordinator(leader),andmultipleclientsWhathappensiftheleaderfails?ElectanewoneCannotassumeonlyoneprocessdetectsthecrashTheelectionshouldgetalloftheprocessestoagreethatonenodeisaleader选举谁？Basicidea:Ifeachprocesshasauniqueidentity,andtheidentitiesareorderedElectthenon-crashednodewithminimum/maximumidentity选举算法旳应用whenacentralizedalgorithmistobe

executedinadistributedsystemforinstance,afterasystemcrashwhenitis

unknownwhichnodesareworking什么是选举

“tostartfromaconfigurationwhereall

processesareinthesamestateandarriveat

aconfigurationwhereexactlyoneprocessis

theleader”

Goal:toobtainlowmessagecomplexity选举算法旳定义Formally,analgorithmisanelectionalgorithmiff:EachprocesshasthesamelocalalgorithmThealgorithmisdecentralizedItcanbeinitiatedbyanynumberofprocessesinthesystemItreachesaterminalconfiguration,andineachreachableterminalconfigurationoneprocessisinstateleaderandtherestareinthestatelost假设FullyasynchronoussystemNoglobalclock,transmissiontimesarbitraryEveryprocesshasauniqueidentityIdentitiesaretotallyorderedBecausewehavefinitenumberofprocesses:MaxidentityandMinidentityavailable(extremevalues)RemarkProcessorsareinoneofthreestates:undecided,leader,lostInitiallyeveryprocessisintheundecidedstateWhenleavingtheundecidedstate,aprocessorgoesintoaterminatedstate(leaderorlost)环网上旳选举单向环双向环LeLann77,O(N2)Chang-Roberts79Ω(N2),Θ(NlogN)Hirshbergetal.80Ω(NlogN)Petersen/Dolevetal.82Ω(NlogN)11环网上旳选举ThefirsteverelectionalgorithmwasdoneforringsbyLeLannSimpleidea:LeteveryinitiatorsendatokenwiththeiridentityaroundthewholeringNodesarenotallowedtoinitiateaftertheyreceiveatoken(example…)12ExampleNodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example…)35198267initiator13ExampleNodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example…)35198267initiator14ExampleNodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example…)35198267initiatornotallowedtoinitiate15ExampleNodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example…)35198267initiatornotallowedtoinitiatenotallowedtoinitiate16ExampleNodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example…)35198267initiatornotallowedtoinitiatenotallowedtoinitiatenotallowedtoinitiate17ExampleNodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example…)35198267initiatornotallowedtoinitiatenotallowedtoinitiateinitiatornotallowedtoinitiate18ExampleNodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example…)35198267initiatornotallowedtoinitiatenotallowedtoinitiateinitiatornotallowedtoinitiatenotallowedtoinitiate19ExampleNodesarenotallowedtoinitiateamessageaftertheyreceiveatoken(example…)35198267initiatornotallowedtoinitiatenotallowedtoinitiateinitiatornotallowedtoinitiatenotallowedtoinitiatenotallowedtoinitiate20LeLann’sringelectionWheneveranodereceivesbackitsid,ithasseeneveryotherinitiatorsidAssumingFIFOchannelsLeteverynodekeepalistofeveryidentifierseen(listp)Ifnon-initiator,state=lostimmediatelyIfinitiator,whenownidreceived:state=leaderifmin{listp}=pstate=lost

otherwiseLeLann’sAlgorithmNon-initiatorsjustforwardandloseInitiallyonlyknowmyselfSendmyid,andwaitRepeatforwardingandcollectingidsuntilwereceiveouridTermination:didwewinorlose22MessageComplexityWorstcaseiseverynodeisinitiator(N)EveryinitiatorsendsNmessagesGivesatotalofN2messages23时间复杂度AssumelastinitiatorfstartsattimeN-1fterminatesafteritstokenhascirculatedthering,NstepsTimecomplexity2N-135198267initiatorlastinitiator24Chang-Roberts算法ChangandRobertscameupwithasmallimprovementIdea:Whenanodereceivesatokenwithlargeridthanitself,whyshoulditkeepforwardingit?Itisawaste,weknowthatthatidwillneverwin!Letsdroptokenswithlargeridsthanourselves!25HowtomakeitworkButifwedropatokenwithids,nodeswillbewaitingforeveronitstokentocomebackHowdowesolvethat?26HowtomakeitworkIfnodestokenisdropped,itwillanywayreceiveanothertokenwithloweridInthatcase,sshouldsetstate=lostChangandRobertsAlgoNon-initiatorsjustforwardandloseInitiatorsendsitstokenWhilenotleader,keepreceivingtokensIfmytokencomes,thenIwonOtherwise,onlyforwardifit’sloweridthanmeandlose28ChangRoberts-ExampleNodes1,3,6areinitiators6913Non-initiatorLostWon6Initiator132901753264ChangRobertsAnalysisWorstcasecomplexitysameasLeLann’sTimeComplexity:2N-1MessageComplexity:O(N2)ConsideredasortedringwithNinitiators8times7times6times5times4times3times2times1times30Furtherimprovements?Letthenon-initiatorsalsofilterloweridsDonotjustcomparewithyourid,comparewiththelowestidyouhaveseen!HSRingElectionHirschbergSinclairAlgorithm(ringmodification)O(N2)isalotofmessages.HereisamodificationthatisO(NlogN).Assumptions:theringsizecanbeunknown.Thecommunicationsmustbebidirectional.Allnodesstartmoreorlessatthesametime.Eachnodeoperatesinphasesandsendsouttokens.Thetokenscarryhop-countsanddirectionflagsinadditiontotheIDofthesender.3

ID=3,2hops

clockwise

ID=3,2hops

counterclckwsHSRingElectionPhasesarenumbered0,1,2,3,…Ineachphase,k,nodejsendsouttokensujcontainingitsIDinbothdirections.Thetokenstravel2khopsthenreturntotheiroriginj.Ifbothtokensmakeitback,processjcontinueswiththenextphase(incrementsk).Ifbothtokensdonotmakeitback,processjsimplywaitstobetoldwhotheresultsoftheelection.33xxiPhase0:20Phase1:21Phase2:22TrajectoryofsuccessivetokensoriginatingatprocessiHSRingElection6-34HSRingElectionIfaprocessmreceivesatokenujgoingintheoutbounddirection,itcomparesthetoken’sIDwithitsown.IfithasalargerID,itsimplydiscardsthetoken.IfithasasmallerID,itrelaysthetokenasrequested.IfitisequaltothetokenID,ithasreceiveditsowntokenintheoutbounddirection,sothetokenhasgonecleararoundtheringandtheprocessdeclaresitselfleader.Allprocessesalwaysrelayinboundtokens.4ID=3,2hopsclockwise非形式化描述Eachprocessioperatesinphases0,1,2,....Ineachphasel,processisendsout"tokens"containingitsUIDuiinbothdirections.Theseareintendedtotraveldistance2l,thenreturntotheirorigini.Ifbothtokensmakeitbacksafely,processicontinueswiththefollowingphase.However,thetokensmightnotmakeitbacksafely.Whileauitokenisproceedingintheoutbounddirection,eachotherprocessjonui'spathcomparesuiwithitsownUIDuj.Ifui<uj,thenjsimplydiscardsthetoken,whereasifui>uj,thenjrelaysui.Ifui=uj,thenitmeansthatprocessjhasreceiveditsownUIDbeforethetokenhasturnedaround,soprocessjelectsitselfastheleader.Allprocessalwaysrelayalltokensintheinbounddirection.HSRingElection一种例子Fordemonstrationpurposes,wewillignoretheasynchronousnatureofthesystemandassumethatallnodesoperateatthesamespeedandatthesametime.InitialnetworkconfigurationwithUIDvaluesinblue.015225314456544134Initialconfiguration.BluenumbersareUIDvaluesThealgorithmstartsinphase0,andeachnodewillsendanoutboundmessagetoitsneighbors.Themessageisintendedtotraveladistanceof20

hops.ThenodesthatreceivedaninboundmessagewithitsOWNUIDfrombothneighborsarequalifiedtoproceedtothenextphase.Theyareindicatedingray.015225314456544134Thenodeseligibletocontinuetophase2Nowweadvancetophase1,andeachactivenodewillsendanoutboundmessagetoitsneighbors.Themessagethistimeisintendedtotraveladistanceof21

hops.Thestraightarrowsrepresentsoutboundandthecurvedarrowsrepresentsinbound.

015225314456544134Phase1.Onlynode4receivesaninboundmessagefrombothneighbors34345656Phase2.Onlynode4isactiveinphase2.Itistheonlynodethatcaninitiateamessage.Themessageisintendedtotravel22

hops.Outgoingmessagessentbynode4intheclockwisedirectionareinpink.Outgoingmessagesinthecounter-clockwisedirectionareingreen.Straightlinesareoutgoingmessages,curvedlinesareincoming.015225314456544134Phase2.Node4onceagainreceivesbothinboundmessageswithownUID5656Phase3.Onlynode4isactiveinphase2.Itistheonlynodethatcaninitiateamessage.Itsmessagesareintendedtotravel23

hops.015225314456544134Phase3.Node4changesitsstatustoleader.43AnalysisofHSRingElectionMessageComplexity:Eachmsgbelongstoaparticularphaseandisinitiatedbyaparticularproc.Probedistanceinphaseiis2iNumberofmsgsinitiatedbyaproc.inphaseiisatmost4*2i(probesandrepliesinbothdirections)44AnalysisofHSRingElectionHowmanyprocs.initiateprobesinphasei?Fori=0,everyproc.doesFori>0,everyproc.thatisa"winner"inphasei-1does"winner"meanshaslargestidinits2i-1neighborhood45AnalysisofHSRingElectionMaximumnumberofphasei-1winnersoccurswhentheyarepackedasdenselyaspossible:totalnumberofphasei-1winnersisatmostn/(2i-1+1)46AnalysisofHSRingElectionHowmanyphasesarethere?Ateachphasethenumberof(phase)winnersiscutinhalf(atleast)Soafteratmostlog2

nphases,onlyonewinnerisleft.47AnalysisofHSRingElectionTotalnumberofmessagesissum,overallphases,ofnumberofwinnersatthatphasetimesnumberofmessagesoriginatedbythatwinner:phase0msgsmsgsforphases1tolognterminationmsgsFranklin算法Allactiveidentitiescomparethemselveswiththe

closestactiveneighbortotheleftandtotherightTheidentityremainsactiveifitisthelocalmin.Peterson/Dolev-Klawe-RodehPetersonLeader-ElectionAlgorithmArbitraryelectionofleaderusingcomparisonofUID’susingunidirectionalcommunicationAlgorithmrunsinphasesinwhicheachprocessisassignedtoactiveorpassivemode(allprocessesstartasactive)ThenumberofactiveprocessesisreducedbyafactoroftwoduringeachphaseSummary:AtthebeginningofeachphaseeachactiveprocessisendsitsUIDtwostepsclockwise.ThenprocessicomparesitsownUIDtothetwoUIDsitreceived.Ifui-1<ui-2andui-1<ui,processiremainsactiveadoptingtheUIDofitscounterclockwiseneighborOtherwiseprocessibecomesarelayPetersonLeaderElectionExamplei11UID=9i10UID=4i9UID=5i12UID=7i8UID=11i7UID=12i6UID=3i5UID=2i4UID=6i3UID=1i2UID=10i1UID=8nPhase1Phase2Phase3Phase4187,9---2108,7---3110,8109,12--461,10---526,1610,91012,101212,12632,6---7123,2---81112,3126,10--9511,12---1045,11---1194,5---1279,4912,61210,12-PetersonLeader-ElectionExamplePetersonLeader-ElectionAlgorithmAnyactiveprocesssurvivesaphaseonlyiftheactiveprocesstoitsleftdoesnotsurvivethatphase.Henceofmactiveprocessesduringaphase,atmostm/2willsurviveform>1.TherecanbeatmostlogNphasestoreachoneactiveprocess.Duringaphaseeveryprocesssends(andreceive)twomessages,andonthelastphasetheloneactiveprocesssendsonemessagewhichisrelayedaroundtothemaximumforatotalof2NlogN+N.5455同步环中旳选举Hereisasimplealgorithm.Grouproundsintophases,eachphasecontainingn

roundsInphasei,theprocessorwithidi,ifthereisone,sendsamessagearoundtheringandiselected.56ExampleofSimpleSynchronousAlgorithmn=4,thesmallestidis7.Inphases0through6(correspondingtorounds1through28),nomessageiseversent.Atbeginningofphase7(round29),processorwithid7sendsmessagewhichisforwardedaroundthering.Reliesonsynchronyandknowingn57AnalysisofSimpleAlgorithmCorrectness:Easytosee.Messagecomplexity:

O(n),whichisoptimalTimecomplexity:

O(n*m),wheremisthesmallestidinthering.notboundedbyanyfunctionofn!58AnotherSynchronousAlgorithmWorksinaslightlyweakermodelthantheprevioussynchronousalgorithm:processorsmightnotallstartatsameround;aprocessoreitherwakesupspontaneouslyorwhenitfirstgetsamessageuniform(doesnotrelyonknowingn)59AnotherSynchronousAlgorithmAprocessorthatwakesupspontaneouslyisactive;sendsitsidinafast

message(oneedgeperround)Aprocessorthatwakesupwhenreceivingamsgisrelay;neverinthecompetitionAfastmessagecarryingidmbecomesslow

ifitreachesanactiveprocessor;startstravelingatoneedgeper2mroundsAprocessoronlyforwardsamsgwhoseidissmallerthananyidishaspreviouslysentIfaproc.getsitsownidback,electsself60AnalysisofSynchronousAlgorithmCorrectness:convinceyourselfthattheactiveprocessorwithsmallestidiselected.Messagecomplexity:Winner'smsgisthefastest.Whileittraversesthering,othermsgsareslower,sotheyareovertakenandstoppedbeforetoomanymessagesaresent.61MessageComplexityDividemsgsintothreekinds:fastmsgsslowmsgssentwhiletheleader'smsgisfastslowmsgssentwhiletheleader'smsgisslowNext,countthenumberofeachtypeofmsg.62