分布式算法領(lǐng)導(dǎo)者選舉

分布協(xié)同計(jì)算基礎(chǔ)第二章:分布式算法(2)

---領(lǐng)導(dǎo)者選舉張錫哲副教授計(jì)算機(jī)應(yīng)用技術(shù)研究所東北大學(xué)信息科學(xué)與工程學(xué)院選舉問(wèn)題Ifweareusingoneprocessasacoordinatorforasharedresource……h(huán)owdoweselectthatoneprocess?Often,thereisnoownerormasterthatisautomaticallyconsideredascoordinator選舉問(wèn)題Manydistributedsystemsareclientserverbased,withoneserver/coordinator(leader),andmultipleclientsWhathappensiftheleaderfails?ElectanewoneCannotassumeonlyoneprocessdetectsthecrashTheelectionshouldgetalloftheprocessestoagreethatonenodeisaleader選舉誰(shuí)？Basicidea:Ifeachprocesshasauniqueidentity,andtheidentitiesareorderedElectthenon-crashednodewithminimum/maximumidentity選舉算法旳應(yīng)用whenacentralizedalgorithmistobe

executedinadistributedsystemforinstance,afterasystemcrashwhenitis

unknownwhichnodesareworking什么是選舉

“tostartfromaconfigurationwhereall

processesareinthesamestateandarriveat

aconfigurationwhereexactlyoneprocessis

theleader”

Goal:toobtainlowmessagecomplexity選舉算法旳定義Formally,analgorithmisanelectionalgorithmiff:EachprocesshasthesamelocalalgorithmThealgorithmisdecentralizedItcanbeinitiatedbyanynumberofprocessesinthesystemItreachesaterminalconfiguration,andineachreachableterminalconfigurationoneprocessisinstateleaderandtherestareinthestatelost假設(shè)FullyasynchronoussystemNoglobalclock,transmissiontimesarbitraryEveryprocesshasauniqueidentityIdentitiesaretotallyorderedBecausewehavefinitenumberofprocesses:MaxidentityandMinidentityavailable(extremevalues)RemarkProcessorsareinoneofthreestates:undecided,leader,lostInitiallyeveryprocessisintheundecidedstateWhenleavingtheundecidedstate,aprocessorgoesintoaterminatedstate(leaderorlost)環(huán)網(wǎng)上旳選舉單向環(huán)雙向環(huán)LeLann77,O(N2)Chang-Roberts79Ω(N2),Θ(NlogN)Hirshbergetal.80Ω(NlogN)Petersen/Dolevetal.82Ω(NlogN)11環(huán)網(wǎng)上旳選舉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時(shí)間復(fù)雜度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同步環(huán)中旳選舉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