分布式算法课件3

LeaderElectioninRings1沈卓炜[e-mail]九龙湖校区计算机楼347房间Tel:52090919133909229522011年3月2RingNetworks•Inanorientedring,processorshaveaconsistentnotionofleftandright•Forexample,ifmessagesarealwaysforwardedonchannel1,theywillcycleclockwisearoundthering3WhyStudyRings?•simplestartingpoint,easytoanalyze•abstractionofatokenring•lowerboundsandimpossibilityresultsforringtopologyalsoapplytoarbitrarytopologies4LeaderElectionDefinition•Eachprocessorhasasetofelected(won)andnot-elected(lost)states.•Onceanelectedstateisentered,processorisalwaysinanelectedstate(andsimilarlyfornot-elected):i.e.,irreversibledecision•Ineveryadmissibleexecution:–everyprocessoreventuallyenterseitheranelectedoranot-electedstate–exactlyoneprocessor(theleader)entersanelectedstate5UsesofLeaderElection•Aleadercanbeusedtocoordinateactivitiesofthesystem:–findaspanningtreeusingtheleaderastheroot–reconstructalosttokeninatoken-ringnetwork•Wewillstudyleaderelectioninrings.6AnonymousRings•Howtomodelsituationwhenprocessorsdonothaveuniqueidentifiers?•Firstattempt:requireeachprocessortohavethesamestatemachine•Subtlepoint:doesalgorithmrelyonknowingtheringsize(numberofprocessors)?7Uniform(Anonymous)Algorithms•Auniformalgorithmdoesnotusetheringsize(samealgorithmforeachsizering)–Formally,everyprocessorineverysizeringismodeledwiththesamestatemachine•Anon-uniformalgorithmusestheringsize(differentalgorithmforeachsizering)–Formally,foreachvalueofn,everyprocessorinaringofsizenismodeledwiththesamestatemachineAn.•Notethelackofuniqueids.8LeaderElectioninAnonymousRings•Theorem:Thereisnoleaderelectionalgorithmforanonymousrings,evenif–algorithmknowstheringsize(non-uniform)–synchronousmodel•ProofSketch:–Everyprocessorbeginsinsamestatewithsameoutgoingmsgs(sinceanonymous)–Everyprocessorreceivessamemsgs,doessamestatetransition,andsendssamemsgsinround1–Dittoforrounds2,3,…–Eventuallysomeprocessorissupposedtoenteranelectedstate.Butthentheyallwould.9LeaderElectioninAnonymousRings•Proofsketchshowsthateithersafety(neverelectmorethanoneleader)orliveness(eventuallyelectatleastoneleader)isviolated.•Sincethetheoremwasprovedfornon-uniformandsynchronousrings,thesameresultholdsforweaker(lesswell-behaved)models:–uniform–asynchronous10RingswithIdentifiers•Assumeeachprocessorhasauniqueid.•Don'tconfuseindicesandids:–indicesare0ton-1;usedonlyforanalysis,notavailabletotheprocessors–idsarearbitrarynonnegativeintegers;areavailabletotheprocessorsthroughlocalvariableid.11•Startwiththesmallestidandlistidsinclockwiseorder.•Example:3,37,19,4,25SpecifyingaRingp3p4p0p1p2id=3id=25id=4id=19id=3712Uniform(Non-anonymous)Algorithms•Uniformalgorithm:thereisonestatemachineforeveryid,nomatterwhatsizering•Non-uniformalgorithm:thereisonestatemachineforeveryidandeverydifferentringsize•Thesedefinitionsaretailoredforleaderelectioninaring.13OverviewofLEinRingswithIds•Thereexistalgorithmswhennodeshaveuniqueids.•Wewillevaluatethemaccordingtotheirmessagecomplexity.•asynchronousring:–(nlogn)messages•synchronousring:–(n)messagesundercertainconditions–otherwise(nlogn)messages•Allboundsareasymptoticallytight.14O(n2)MessagesLEAlgorithm•sendvalueofownidtotheleft•whenreceiveanidj(fromtheright):–ifjidthen•forwardjtotheleft(thisprocessorhaslost)–ifj=idthen•electself(thisprocessorhaswon)–ifjidthen•donothing15AnalysisofO(n2)Algorithm•Correctness:Electsprocessorwithlargestid.–msgcontaininglargestidpassesthrougheveryprocessor•Time:O(n)•Messagecomplexity:Dependshowtheidsarearranged.–largestidtravelsallaroundthering(nmsgs)–2ndlargestidtravelsuntilreachinglargest–3rdlargestidtravelsuntilreachinglargestorsecondlargest–etc.16AnalysisofO(n2)Algorithm•Worstwaytoarrangetheidsisindecreasingorder:–2ndlargestcausesn-1messages–3rdlargestcausesn-2messages–etc.•Totalnumberofmessagesisn+(n-1)+(n-2)+…+1=(n2).17CanWeUseFewerMessages?•TheO(n2)algorithmissimpleandworksinbothsynchronousandasynchronousmodel.•Butcanwesolvetheproblemwithfewermessages?•Idea:–Trytohavemsgscontainingsmalleridstravelsmallerdistanceinthering18O(nlogn)LeaderElectionAlgorithm•Eachproc.triestoprobesuccessivelylargerneighborhoodsinbothdirections–sizeofneighborhooddoublesineachphase•Ifprobereachesanodewithalargerid,theprobestops•Ifprobereachesendofitsneighborhood,thenareplyissentbacktoinitiator•Ifinitiatorgetsbackrepliesfrombothdirections,thengotonextphase•Ifproc.receivesaprobewithitsownid,itelectsitself19O(nlogn)LeaderElectionAlgorithm20AnalysisofO(nlogn)LeaderElectionAlgorithm•Correctness:SimilartoO(n2)algorithm.•MessageComplexity:–Eachmsgbelongstoaparticularphaseandisinitiatedbyaparticularproc.–Probedistanceinphaseiis2i–Numberofmsgsinitiatedbyaproc.inphaseiisatmost4*2i(probesandrepliesinbothdirections)21AnalysisofO(nlogn)LeaderElectionAlgorithm•Howmanyprocs.initiateprobesinphasei?•Fori=0,everyproc.does•Fori0,everyproc.thatisawinnerinphasei-1does–winnermeanshaslargestidinits2i-1neighborhood22AnalysisofO(nlogn)LeaderElectionAlgorithm•Maximumnumberofphasei-1winnersoccurswhentheyarepackedasdenselyaspossible:•totalnumberofphasei-1winnersisatmostn/(2i-1+1)23AnalysisofO(nlogn)Leade