并行程序設(shè)計(jì) 中文課件 11 并行計(jì)算系統(tǒng)同步

ParallelProgrammingInstructor:ZhangWeizhe(張偉哲)ComputerNetworkandInformationSecurityTechniqueResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnologyTimeandGlobalState31.Introduction介紹2.Clocks,eventsandprocessstates時(shí)鐘，事件和進(jìn)程狀態(tài)3.Synchronizingphysicalclocks同步物理時(shí)鐘4.Logicaltimeandlogicalclocks邏輯時(shí)間和邏輯時(shí)鐘5.SummaryOutline4Needtomeasureaccurately需要準(zhǔn)確測(cè)量E.g.auditingine-commerce電子商務(wù)審計(jì)Algorithmsdependingon算法取決于E.g.consistency,make，DistributedDebugging分布式調(diào)試TimeisanimportantissueinDS5Example:makeWheneachmachinehasitsownclock,aneventthatoccurredafteranothereventmayneverthelessbeassignedanearliertime.當(dāng)每臺(tái)機(jī)器都有自己的時(shí)鐘時(shí)，在另一個(gè)事件之后發(fā)生的事件可能會(huì)被分配較早的時(shí)間。6Physicist’sview物理學(xué)家的觀點(diǎn)Newton’snotation:absolutephysicaltime牛頓的符號(hào)：絕對(duì)的物理時(shí)間Einstein’sRelativityTheory愛(ài)因斯坦的相對(duì)論P(yáng)eople’sapproachesdealingwithtime人們處理時(shí)間的方法Approximatelysynchronize大概同步Logicalclocks邏輯時(shí)鐘Thereisnouniversephysicalclock71.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline8Adevicethatcountoscillationsoccurringinacrystalatadefinitefrequency以一定頻率計(jì)算晶體振蕩的裝置Hardwaretime:Hi(t)Thecountsofoscillationsinceanoriginalpoint原始點(diǎn)以來(lái)的振蕩計(jì)數(shù)Softwaretime:Ci(t)=

Hi(t)+

Timestampofanevent事件的時(shí)間戳Clockincomputer9Clockdrift時(shí)鐘漂移Crystaloscillateatdifferentrate晶體以不同的速率振蕩Clockdriftcannotbeavoided時(shí)鐘漂移是無(wú)法避免的Clockskew時(shí)鐘偏移Theinstantaneousdifferencebetweenthereadingsofanytwoclocks任何兩個(gè)時(shí)鐘的讀數(shù)之間的瞬時(shí)差異Clockskewandclockdrift10RotationofearthonitsaxisandabouttheSun自轉(zhuǎn)和公轉(zhuǎn)Days,Years,etcSecondis1/86400astronomical天文timeMeansolarsecond平均太陽(yáng)秒TheperiodoftheEarth’srotationaboutitsaxisisgraduallygettinglonger地球圍繞其軸旋轉(zhuǎn)的時(shí)期逐漸變長(zhǎng)Tidalfriction,atmosphericeffects,etc潮汐摩擦，大氣影響等AstronomicalTime(1)11AstronomicalTime(2)Computationofthemeansolarday.12Standardsecond標(biāo)準(zhǔn)秒Atomicoscillator原子振蕩器Driftrate:onepartin10-13Since1967:9,192,631,770periodsoftransitionbetweenthetwohyperfinelevelsofthegroundstateofCs133Shiftbetweenastronomicaltimeandatomictime天文時(shí)間與原子時(shí)間之間的轉(zhuǎn)換Leapsecond閏秒Atomictimewhichisinsertedaleapsecondoccasionallytokeepinstepwithastronomicaltime原子時(shí)間偶爾插入閏秒，與天文時(shí)間保持一致InternationalAtomicTime13LeapsecondTAIsecondsareofconstantlength,unlikesolarseconds.Leapsecondsareintroducedwhennecessarytokeepinphasewiththesun.

TAI秒的長(zhǎng)度不變，不像太陽(yáng)秒。必要時(shí)引入閏秒與太陽(yáng)保持同步。14Greenwichmeantime格林威治標(biāo)準(zhǔn)時(shí)間Universalcoordinatedtime(UTC)BroadcastUTCtotheWorldE.g.,byGPSorWWVCoordinatedUniversalTime(UTC)151.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline16Externalsynchronization外部同步ForasynchronizationboundD>0,andforasourceSofUTCtime,|S(t)-Ci(t)|<D,fori=1,2,…NandforallrealtimestinIClocksCiareaccurate

towithintheboundD時(shí)鐘Ci精確到D范圍內(nèi)Ci

:pi’sclockI:anintervalofrealtime真實(shí)時(shí)間間隔External&Internalsynchronization(1)17Internalsynchronization內(nèi)部同步ForasynchronizationboundD>0,|Ci(t)-Cj(t)|<D

fori,j=1,2,…N,andforallrealtimestinIClocksCi

agree

withintheboundDIf

accurate

towithinD,then

agree

within2D如果精確到D，允許范圍是2DExternal&Internalsynchronization(2)18Clockfailures時(shí)鐘故障Crashfailure:stopticking崩潰故障：停止滴答Arbitrary任意failure,e.g.Y2KbugGeneralsynchronizationissues19Protocol協(xié)議Sender:sendM(t)Receiver:settimetot+TtransBoundsareknowinsynchronoussystem范圍在同步系統(tǒng)中是已知的min<Ttrans<max(constant)So,setTtrans=(min+max)/2Receiver’sclock=t+(min+max)/2Synchronizationinasynchronoussystem20Clockskewbetweensenderandreceiver(max–min)/2Synchronizationinasynchronoussystem(2)tt+maxt+Ttranst+min21Externalsynchronization外部同步Applyingcircumstance適用情況C/SRound-triptimeisshortcomparedwiththerequiredaccuracyC/S與所需精度相比，往返時(shí)間短Protocolmr,mt(t),TroundEstimatedtime:tinmt+Tround/2Cristian’smethodofsynchronizingclocksmrmtpTimeserver,S22Accuracyanalysis精度分析Iftheminimumdelayofamessagetransmission消息傳輸?shù)淖钚⊙舆tismin,thenaccuracy:(Tround/2–min)Cristian’smethodofsynchronizingclocks(2)tt+Tround-mint+Tround/2t+mint+Tround23Internalsynchronization內(nèi)部同步Themaster

pollstheslaves’clocks主輪詢從時(shí)鐘Themaster

estimatestheslaves’clocksbyround-triptime主人通過(guò)往返時(shí)間估計(jì)從時(shí)鐘SimilartoChristian’salgorithm類似于基督教的算法Themaster

averagestheslaves’clockvalues主人對(duì)從站的時(shí)鐘值進(jìn)行平均Cancelouttheindividualclock’stendenciestorunfastorslow取消個(gè)別時(shí)鐘的趨勢(shì)，以快速或慢速運(yùn)行TheBerkeleyalgorithms24Themastersendsbacktotheslavestheamountthattheslaves’clocksshouldadjustby主機(jī)向從站發(fā)回從站的時(shí)鐘應(yīng)該調(diào)整的量Positiveornegativevalue正值或負(fù)值A(chǔ)voidfurtheruncertaintyduetothemessagetransmissiontime避免由于消息傳輸時(shí)間進(jìn)一步的不確定性Slaveajustitsclock從時(shí)鐘調(diào)整TheBerkeleyalgorithms(2)25TheBerkeleyAlgorithm(3)(a)Thetimedaemon時(shí)間守護(hù)進(jìn)程asksalltheothermachinesfortheirclockvalues.

26TheBerkeleyAlgorithm(4)(b)Themachinesanswer.27TheBerkeleyAlgorithm(5)(c)Thetimedaemontellseveryonehowtoadjusttheirclock.28ExternalsynchronizationEnableclientsacrosstheInternettobesynchronizedaccuratelytoUTCReliabilityCansurvivelengthylossesofconnectivityRedundantserver&redundantpathbetweenserversScalabilityEnableclientstoresynchronizesufficiently

frequentlytooffsettheratesofdriftfoundinmostcomputersSecurityProtectagainstinterferencewiththetimeserviceDesignaimsofNetworkTimeProtocol29外部同步使互聯(lián)網(wǎng)上的客戶端能夠準(zhǔn)確地同步到UTC可靠性可以長(zhǎng)時(shí)間連接的損失冗余服務(wù)器和服務(wù)器之間的冗余路徑可擴(kuò)展性使客戶端能夠頻繁地重新同步，以抵消大多數(shù)計(jì)算機(jī)中發(fā)現(xiàn)的漂移速率安全防止干擾時(shí)間服務(wù)網(wǎng)絡(luò)時(shí)間協(xié)議的設(shè)計(jì)目標(biāo)30ReconfigurewhenserversbecomeunreachableNetworkTimeProtocolArchitecture123233Note:Arrowsdenotesynchronizationcontrol,numbersdenotestrata.31MulticastmodeIntendforuseonahighspeedLANAssumingasmalldelayLowaccuracybutefficientProcedure-callmodeSimilartoChristian’sHigheraccuracythanmulticastSymmetricmodeThehighestaccuracySynchronizationmeasures32組播模式適合在高速LAN上使用假設(shè)延遲很小精度低但效率高程序呼叫模式類似于基督徒精度高于多播對(duì)稱模式最高的準(zhǔn)確性同步措施331.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline34

HB1:Ifprocesspi:eie`,thenee`HB2:Foranymessagem,send(m)receive(m)HB3:IFe,e`ande``areeventssuchthatee`ande`e``,thenee``CausalorderingHappen-beforerelation35Examplea||eShortcomings缺點(diǎn)Notsuitabletoprocessescollaborationthatdoesnotinvolvemessagestransmission不適合處理不涉及消息傳輸?shù)膮f(xié)作Capturepotentialcausalordering捕獲潛在的因果秩序Happen-beforerelation36Example37LC1Liisincrementedbeforeeacheventisissuedatprocesspi:Li:=Li+1LC2:(a)Whenaprocesspisendsamessagem,itpiggybacksonmthevaluet=Li(b)Onreceiving(m,t),aprocessPjcomputesLj:=max(Lj,t)andthenappliesLC1beforetimestampingtheeventreceive(m)Lamporttimestampsalgorithm38ee`L(e)<L(e`)L(e)<L(e`)ee`ore||e`Lamporttimestampsalgorithm(2)39Example:Lamport’sClocks(1)(a)Threeprocesses,eachwithitsownclock.

Theclocksrunatdifferentrates.

40Example:Lamport’sClocks(2)(b)Lamport’salgorithmcorrectstheclocks.41EachprocesspikeepsavectorclockViVC1:Initially,Vi[j]=0,fori,j=1,2…,NVC2:Justbeforepitimestampsanevent,itsetsVi[i]:=Vi[i]+1VC3:piincludesthevaluet=ViineverymessageitsendsVC4:Whenpireceivesatimestamptinamessage,itsetsVi[j]:=max(Vi[j],t[j]),forj=1,2…,NVectorClocks-algorithm42VectorClocks-example43Comparevectortimestamps

V=V’iffV[j]=V’[j]forj=1,2…,NV<=V’iffV[j]<=V’[j]forj=1,2…,N

V<V’iffV[j]<V’[j]forj=1,2…,NOtherwiseV<>V’V(e)<V(e`)ee`,V(e)<>V(e`)e||e`VectorClocks-significance441.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline45Clockskew,clockdrift時(shí)鐘偏移，時(shí)鐘漂移Synchronizephysicalclocks物理時(shí)鐘同步Christian’salgorithm基督教的算法Berkeleyalgorithm伯克利算法NetworkTimeProtocol網(wǎng)絡(luò)時(shí)間協(xié)議Logicaltime邏輯時(shí)間Happen-beforerelation發(fā)生之前關(guān)系Lamporttimestampalgorithm拉姆波特時(shí)間戳算法Vectorclock矢量時(shí)鐘Summary46Globalstates全球狀態(tài)Consistentcut,consistentstate一致切割，一致?tīng)顟B(tài)Snapshotalgorithm快照算法Constructreachabilityrelationshipbysnapshot通過(guò)快照構(gòu)建可達(dá)性關(guān)系Summary…continuedCoordinationandAgreement協(xié)調(diào)與協(xié)議481.Distributedmutualexclusion分布式互斥2.Elections選舉3.SummaryOutline49MutualExclusionToguaranteeconsistencyamongdistributedprocessesthatareaccessingsharedmemory,itisnecessarytoprovidemutualexclusion

whenaccessingacriticalsection.為了保證正在訪問(wèn)共享內(nèi)存的分布式進(jìn)程之間的一致性，必須在訪問(wèn)臨界區(qū)時(shí)提供互斥。Assume

nprocesses.50AssumptionAsynchronous,noprocessfail,reliablechannel異步，沒(méi)有進(jìn)程失敗，可靠的通道Applicationlevelprotocolenter()resourceAccesses()exit()Algorithmsformutualexclusion51EssentialrequirementsformutualexlcusionSafetyAtmostoneprocessmayexecuteinthecriticalsectionatatimeLivenessRequeststoenterandexitthecriticalsection(CS)eventuallysucceedFreefromdeadlockandstarvationOrderingIfonerequesttoentertheCShappened-beforeanother,thenentrytotheCSisgrantedinthatorderAlgorithmsformutualexclusion52互斥的基本要求安全一次最多可以在關(guān)鍵部分執(zhí)行一個(gè)進(jìn)程活躍進(jìn)入和退出關(guān)鍵部分（CS）的請(qǐng)求最終成功沒(méi)有死鎖和饑餓順序如果進(jìn)入CS的一個(gè)請(qǐng)求發(fā)生在另一個(gè)之前，則按照該順序授予對(duì)CS的輸入互斥算法53EvaluatetheperformanceofthealgorithmsBandwidthconsumedThenumberofmessagessentineachentryandexitoperationClientDelayIncurredbyaprocessateachentryandexitoperationsAlgorithmsformutualexclusion…continued54評(píng)估算法的性能帶寬消耗在每個(gè)進(jìn)入和退出操作中發(fā)送的消息數(shù)客戶延遲在進(jìn)入和退出操作過(guò)程中發(fā)生Algorithmsformutualexclusion…continued55ACentralizedAlgorithm

forMutualExclusionAssumeacoordinatorhasbeenelected. 1.Aprocesssendsamessagetothecoordinatorrequesting permissiontoenteracriticalsection.Ifnootherprocess isinthecriticalsection,permissionisgranted. 2.Ifanotherprocessthenaskspermissiontoenterthesame criticalregion,thecoordinatordoesnotreply(Or,it sends“permissiondenied”)andqueuestherequest. 3.Whenaprocessexitsthecriticalsection,itsendsa messagetothecoordinator. 4.Thecoordinatortakesfirstentryoffthequeueandsends thatprocessamessagegrantingpermissiontoenterthe criticalsection.56互斥的集中算法假設(shè)一個(gè)協(xié)調(diào)者已經(jīng)當(dāng)選了。1.進(jìn)程向協(xié)調(diào)者發(fā)送消息，請(qǐng)求進(jìn)入關(guān)鍵部分的許可。如果關(guān)鍵部分中沒(méi)有其他進(jìn)程，則授予權(quán)限。2.如果另一個(gè)進(jìn)程要求進(jìn)入相同關(guān)鍵區(qū)域的權(quán)限，則協(xié)調(diào)器不會(huì)回復(fù)（或者它發(fā)送“被拒絕的權(quán)限”）并對(duì)請(qǐng)求進(jìn)行排隊(duì)。3.當(dāng)一個(gè)進(jìn)程退出臨界區(qū)時(shí)，它向協(xié)調(diào)器發(fā)送一個(gè)消息。4.協(xié)調(diào)者從隊(duì)列中選擇第一個(gè)，并向該進(jìn)程發(fā)送一個(gè)消息，授予進(jìn)入關(guān)鍵部分的權(quán)限。57ACentralizedAlgorithm(1)(a)Process1asksthecoordinatorforpermissiontoaccessaharedresource.Permissionisgranted.

58ACentralizedAlgorithm(2)(b)Process2thenaskspermissiontoaccessthesameresource.Thecoordinatordoesnotreply.59ACentralizedAlgorithm(3)(c)Whenprocess1releasestheresource,ittellsthecoordinator,whichthenrepliesto2.60PerformanceBandwidthconsumption=3Enter():Arequestmessage,agrantmessageExit():areleasemessageClientDelay(nowaitingprocesses)=2Requestmessage+grantmessageProblems:Coordinatorcrash協(xié)調(diào)者崩潰Performancebottleneck性能瓶頸ACentralizedAlgorithm(4)61ADistributedAlgorithm(1)Threedifferentcases:Ifthereceiverisnotaccessingtheresourceanddoesnotwanttoaccessit,itsendsbackanOKmessagetothesender.Ifthereceiveralreadyhasaccesstotheresource,itsimplydoesnotreply.Instead,itqueuestherequest.Ifthereceiverwantstoaccesstheresourceaswellbuthasnotyetdoneso,itcomparesthetimestampoftheincomingmessagewiththeonecontainedinthemessagethatithassenteveryone.Thelowestonewins.62分布式算法(1)三種不同的情況：如果接收方?jīng)]有訪問(wèn)資源，并且不想訪問(wèn)該資源，則它向發(fā)送方發(fā)回一條OK消息。如果接收者已經(jīng)可以訪問(wèn)資源，它根本就不會(huì)回復(fù)。相反，它會(huì)排隊(duì)請(qǐng)求。如果接收方想要訪問(wèn)資源，但還沒(méi)有這樣做，它將傳入消息的時(shí)間戳與發(fā)送給每個(gè)人的消息中包含的時(shí)間戳進(jìn)行比較。最低的一個(gè)勝利。63ADistributedAlgorithm(2)(a)Twoprocesseswanttoaccessasharedresourceatthesamemoment.64ADistributedAlgorithm(3)(b)Process0hasthelowesttimestamp,soitwins.65ADistributedAlgorithm(4)(c)

Whenprocess0isdone,itsendsanOKalso,so2cannowgoahead.66IdeaAprocessentersCSifallotherprocessespromiseMulticast+replyPerformanceBandwidth=2(n-1)Enter():N-1multicastmessage,N-1replyClientdelay:round-triptime=2(n-1)Problems:Crashofanyprocess任何進(jìn)程崩潰ADistributedAlgorithm(4)67ATokenRingAlgorithm(1)(a)Anunorderedgroupofprocessesonanetwork.

(b)Alogicalringconstructedinsoftware.68PerformanceBandwidthconsumed=1~infiniteContinuouslyconsumenetworkbandwidthClientDelay=0~n-1Min:0message,whenithasjustreceivedthetokenMax:Nmessages,whenithasjustpassedonthetokenATokenRingAlgorithm(2)69AComparisonoftheThreeAlgorithmsAlgorithmMessagesperentry/exitDelaybeforeentry(inmessagetimes)ProblemsCentralized32CoordinatorcrashDistributed2(n–1)2(n–1)ProcesscrashTokenring1to

0ton–1Losttoken,processcrashCentralizedisthemostefficient.Tokenringefficientwhenmanywanttousecriticalregion.70IdeaAprocessenterCSwhenpartofotherprocessespromisePerformanceBandwidthutilization帶寬利用率Noreleasemessages:Havereleasemessages:Betterthan2(N-1)ifN>4Clientdelay:aroundtriptime客戶延遲：往返時(shí)間Sameasmulticastalgorithm與多播算法相同TheimprovedalgorithmAtotalorderofeachrequest每個(gè)請(qǐng)求的總順序Thewait-foroperationexecutesinaccordancewiththetotalorder等待操作根據(jù)總順序執(zhí)行Maekawa’svotingalgorithm711.Distributedmutualexclusion2.Elections3.SummaryOutline72ElectionAlgorithmsManydistributedalgorithmssuchasmutualexclusionanddeadlockdetectionrequirea

coordinatorprocess.Whenthecoordinatorprocessfails,thedistributedgroupofprocessesmustexecuteanelectionalgorithmtodetermineanewcoordinatorprocess.Thesealgorithmswillassumethateachactiveprocesshasauniquepriorityid.

73選擇算法Manydistributedalgorithmssuchasmutualexclusionanddeadlockdetectionrequirea

coordinatorprocess.許多分布式算法，如互斥和死鎖檢測(cè)需要協(xié)調(diào)程序。Whenthecoordinatorprocessfails,thedistributedgroupofprocessesmustexecuteanelectionalgorithmtodetermineanewcoordinatorprocess.當(dāng)協(xié)調(diào)程序進(jìn)程失敗時(shí)，分布式進(jìn)程組必須執(zhí)行選擇算法來(lái)確定新的協(xié)調(diào)程序進(jìn)程。Thesealgorithmswillassumethateachactiveprocesshasauniquepriorityid.這些算法將假設(shè)每個(gè)活動(dòng)進(jìn)程具有唯一的優(yōu)先級(jí)id。74ElectionChooseauniqueprocesstoplayaparticularroleDefinetheelection:choosethelargestidentifierE.g.forelectingtheprocesswithlowestload,thenid=1/loadEvaluatetheperformanceofelectionalgorithmTotalbandwidthutilizationTurnaroundtimeThenumberofserializedmessagetransmissiontimesbetweentheinitiationandterminationofasinglerunSomeconceptsaboutElectionalgorithm75選舉選擇一個(gè)獨(dú)特的過(guò)程來(lái)發(fā)揮特定的作用確定被選者：選擇最大的標(biāo)識(shí)符例如，用于選擇最低負(fù)載的過(guò)程，則id=1/負(fù)載評(píng)估選舉算法的性能總帶寬利用率周轉(zhuǎn)時(shí)間在單次運(yùn)行的啟動(dòng)和終止之間的序列化消息傳輸時(shí)間的數(shù)量選擇算法一些概念76AssumptionSynchronoussystemUsetimeouttodetectaprocessfailureReliablefailuredetectorProcesscancommunicatewithprocesseswhichhavehigheridentifiershigherprocesses&lowerprocessesThebullyalgorithm77假設(shè)同步系統(tǒng)使用超時(shí)來(lái)檢測(cè)進(jìn)程故障可靠的故障檢測(cè)器進(jìn)程可以與具有更高標(biāo)識(shí)符的進(jìn)程通信更高的流程和更低的流程Thebullyalgorithm78ThebullyalgorithmTheBullyAlgorithm1.PsendsanELECTIONmessagetoallprocesseswithhighernumbers.2.Ifnooneresponds,Pwinstheelectionandbecomescoordinator.3.Ifoneofthehigher-upsanswers,ittakesover.P’sjobisdone.79Thebullyalgorithm欺負(fù)算法1.P發(fā)送一個(gè)ELECTION消息給所有具有較高數(shù)字的進(jìn)程。2.如果沒(méi)有人回應(yīng)，P贏得選舉，成為協(xié)調(diào)員。3.如果其中一個(gè)高層回答，它將接管。P的工作完成了。80TheBullyAlgorithm(1)(a)Process4holdsanelection.(b)Processes5and6respond,telling4tostop.(c)Now5and6eachholdanelection.81TheBullyAlgorithm(2)(d)Process6tells5tostop.(e)Process6winsandtellseveryone.82Evaluatetheperformance評(píng)估性能bandwidthbest

=N-2Thesecondhighestprocessinitiatetheelection第二高的進(jìn)程開(kāi)始選舉SendN-2coordinatormessagetolowerprocessesTurnaroundtime=1messagebandwidthworst

:O(N2)Thelowestprocessinitiatetheelection

Thebullyalgorithm…continued83ARingAlgorithmAssumetheprocessesarelogicallyorderedinaring{impliesasuccessorpointerandanactiveprocesslist}

thatisunidirectional.Whenanyprocess,P,noticesthatthecoordinatorisnolongerrespondingitinitiatesanelection:1.PsendsmessagecontainingP’sprocessidtothenextavailablesuccessor.84ARingAlgorithm假設(shè)這些進(jìn)程在一個(gè)環(huán)中被邏輯地排序（這意味著一個(gè)獨(dú)立的后繼指針和一個(gè)活動(dòng)的進(jìn)程列表）。當(dāng)任何進(jìn)程P發(fā)現(xiàn)協(xié)調(diào)員不再響應(yīng)時(shí)，會(huì)啟動(dòng)一個(gè)選舉：P將包含P進(jìn)程標(biāo)識(shí)的消息發(fā)送到下一個(gè)可用的后繼。85ARingAlgorithm2.

Ateachactiveprocess,thereceivingprocessaddsitsprocessnumbertothelistofprocessesinthemessageandforwardsittoitssuccessor.3.Eventually,themessagegetsbacktothesender.4.Theinitialsendersendsoutasecondmessagelettingeveryoneknowwhothecoordinatoris{theprocesswiththehighestnumber}andindicatingthecurrentmembersoftheactivelistofprocesses.

86ARingA