9 Задача избрания лидера. Избрание лидера на кольцах - алгоритм Ченя-Робертса, оптимальный алгоритм Патерсона – Долева-Клейва-Роде

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 8.Çàäà÷à èçáðàíèÿ ëèäåðà.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿ.Âîëíîâûå àëãîðèòìû èçáðàíèÿ ëèäåðà.Âûáîðû ëèäåðà íà äåðåâå.Âûáîðû â êîëüöàõ.Àëãîðèòì Ëå-Ëàííà.Àëãîðèòì ×åíÿ Ðîáåðòñà.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå.Ýôôåêò óãàñàíèÿ.Çàäà÷à èçáðàíèÿ ëèäåðàÇàäà÷à èçáðàíèÿ ëèäåðà ñîñòîèò â òîì, ÷òîáû, èçêîíôèãóðàöèè, â êîòîðîé âñå ïðîöåññû ïðåáûâàþò â îäíîì èòîì æå ñîñòîÿíèè, äîñòè÷ü òàêîé êîíôèãóðàöèè, â êîòîðîéðîâíî îäèí ïðîöåññ áóäåò íàõîäèòüñÿ â ñîñòîÿíèè leader , à âñåîñòàëüíûå ïðîöåññû â ñîñòîÿíèè lost .Âûáîðû ëèäåðà ñðåäè ïðîöåññîâ ïðîâîäÿòñÿ, êîãäà íóæíîâûïîëíèòü êàêîé-íèáóäü öåíòðàëèçîâàííûé àëãîðèòì, è íåòçàðàíåå çàäàííîãî êàíäèäàòà, êîòîðûé ìîã áû âûñòóïèòüèíèöèàòîðîì ýòîãî àëãîðèòìà.Òàêîå ïðîèñõîäèò, êîãäà èíèöèàëèçàöèÿ âûïîëíÿåòñÿ â íà÷àëåðàáîòû èëè ïîñëå âûõîäà ñèñòåìû èç ñòðîÿ.Ïîñêîëüêó ìíîæåñòâî àêòèâíûõ ïðîöåññîâ ìîæåò áûòü çàðàíååíåèçâåñòíî, íåëüçÿ íàçíà÷èòü ðàç è íàâñåãäà îäèí èç ïðîöåññîâíà ðîëü ëèäåðà.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿÎïðåäåëåíèåíàçûâàåòñÿ àëãîðèòì,êîòîðûé îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè.Àëãîðèòìîì èçáðàíèÿ ëèäåðà1.

Êàæäûé ïðîöåññ íàäåëåí îäíèì è òåì æå ëîêàëüíûìàëãîðèòìîì.2. Àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì, ò.å. âû÷èñëåíèåìîæåò áûòü èíèöèèðîâàíî ïðîèçâîëüíûì íåïóñòûìïîäìíîæåñòâîì ïðîöåññîâ.3. Àëãîðèòì äîñòèãàåò çàêëþ÷èòåëüíîé êîíôèãóðàöèè âêàæäîì âû÷èñëåíèè, è â êàæäîé çàêëþ÷èòåëüíîéêîíôèãóðàöèè ñóùåñòâóåò ðîâíî îäèí ïðîöåññ, êîòîðûéíàõîäèòñÿ â ñîñòîÿíèè leader à âñå îñòàëüíûå ïðîöåññûïðè ýòîì ïðåáûâàþò â ñîñòîÿíèè lost.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿÏîñëåäíåå ñâîéñòâî èíîãäà áûâàåò îãðàíè÷åíî ëèøüòðåáîâàíèåì òîãî, ÷òîáû ðîâíî îäèí ïðîöåññ íàõîäèëñÿ âñîñòîÿíèè leader. Åñëè çàäàí àëãîðèòì, óäîâëåòâîðÿþùèéýòîìó îñëàáëåííîìó òðåáîâàíèþ, òî åãî ìîæíî ëåãêîäîïîëíèòü ïîòîêîì ñîîáùåíèé, èíèöèèðîâàííûì ëèäåðîì,áëàãîäàðÿ êîòîðîìó âñå ïðîöåññû áóäóò îïîâåùåíû îðåçóëüòàòàõ âûáîðîâ.Âî âñåõ àëãîðèòìàõ ïðîöåññ p íàäåëåí ïåðåìåííîé statep ,ìíîæåñòâî çíà÷åíèé êîòîðîé âêëþ÷àåò â ñåáÿ leader è lost.Èíîãäà ïðåäïîëàãàåòñÿ, ÷òî çíà÷åíèåì statep ÿâëÿåòñÿ sleep äîòîãî, êàê p âûïîëíèë õîòü îäèí øàã íàøåãî àëãîðèòìà, è candêàê òîëüêî p ïðèñîåäèíèëñÿ ê âû÷èñëåíèþ, íî åùå íå áûëîñâåäîìëåí î òîì, âûèãðàë èëè ïðîèãðàë îí ýòè âûáîðû.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿÇàäà÷à î âûáîðàõ èçó÷àåòñÿ â ðàìêàõ ñëåäóþùèõ äîïóùåíèé.1Ïðîöåññû íå èìåþòäîñòóïà ê îáùèì ÷àñàì, è ïåðåäà÷à ñîîáùåíèé ìîæåòäëèòüñÿ ñêîëü óãîäíî äîëãî èëè êîðîòêî.Ñèñòåìà âïîëíå àñèíõðîííà.Äîïóùåíèå î ñèíõðîííîé ïåðåäà÷å ñîîáùåíèé ïî÷òè íåâëèÿåò íà ðåçóëüòàòû, îòíîñÿùèåñÿ ê çàäà÷å î âûáîðàõ:âñå ðàññìîòðåííûå àëãîðèòìû ìîæíî ïðèìåíÿòü âñèñòåìàõ ñ ñèíõðîííîé ïåðåäà÷åé ñîîáùåíèé.Äîïóùåíèå î ãëîáàëüíîì îòñ÷åòå âðåìåíè (ïðîöåññû ìîãóòîòñëåæèâàòü ðåàëüíîå âðåìÿ, çàäåðæêà ïåðåäà÷èñîîáùåíèÿ îãðàíè÷åíà è ïð.) äåéñòâèòåëüíî îêàçûâàåòâàæíîå âëèÿíèå íà ðåøåíèå çàäà÷è î âûáîðàõ.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿ2Êàæäûé ïðîöåññ îïîçíàåòñÿ ïî óíèêàëüíîìó èìåíè,è ýòî èìÿ èçíà÷àëüíî èçâåñòíî ñàìîìó ïðîöåññó.Èìåíà ïðîöåññîâ (îòëè÷èòåëüíûå ïðèçíàêè ) îáðàçóþòëèíåéíî óïîðÿäî÷åííîå ìíîæåñòâà P .Ïðè ïðîåêòèðîâàíèè àëãîðèòìà èçáðàíèÿ ìîæíî ïîñòóëèðîâàòü, ÷òî íà âûáîðàõ ïîáåäèò ïðîöåññ ñ íàèìåíüøèì(íàèáîëüøèì) ïî ïîðÿäêó îòëè÷èòåëüíûì ïðèçíàêîì.Òàê âîçíèêàåò çàäà÷à îòûñêàíèÿ íàèìåíüøåãî îòëè÷èòåëüíîãî ïðèçíàêà ïîñðåäñòâîì äåöåíòðàëèçîâàííîãîàëãîðèòìà çàäà÷à îòûñêàíèÿ ýêñòðåìóìîâ .Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿ3Êàæäîå ñîîáùåíèå ìîæåò ñîäåðæàòüO(w )áèò. êàæäîì ñîîáùåíèè ìîæåò ñîäåðæàòüñÿ ëèøüêîíñòàíòíîå ÷èñëî îòëè÷èòåëüíûõ ïðèçíàêîâ ïðîöåññîâ.Ýòî äîïóùåíèå ñäåëàíî äëÿ òîãî, ÷òîáû ñïðàâåäëèâîñîïîñòàâëÿòü ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìèäëÿ ðàçëè÷íûõ àëãîðèòìîâ.Âîëíîâûå àëãîðèòìû èçáðàíèÿ ëèäåðàÎòëè÷èòåëüíûå ïðèçíàêè ïðîöåññîâ ìîæíî èñïîëüçîâàòü äëÿíàðóøåíèÿ ñèììåòðèè ìåæäó ïðîöåññàìè, è àëãîðèòìèçáðàíèÿ ìîæíî ñïðîåêòèðîâàòü òàê, ÷òîáû âûäåëÿòü ïðîöåñññ íàèìåíüøèì îòëè÷èòåëüíûì ïðèçíàêîì.

Íàèìåíüøèéîòëè÷èòåëüíûé ïðèçíàê ìîæåò áûòü âû÷èñëåí ïðîöåññàìè ïîõîäó îäíîé âîëíû (ïî÷åìó? ).Çíà÷èò, âûáîðû ìîæíî ïðîâåñòè, çàïóñòèâ âîëíó âû÷èñëåíèÿíàèìåíüøåãî îòëè÷èòåëüíîãî ïðèçíàêà, ïîñëå ÷åãî ïðîöåññ ñíàèìåíüøèì ïðèçíàêîì ñòàíîâèòñÿ ëèäåðîì. Òàê êàê àëãîðèòìèçáðàíèÿ äîëæåí áûòü äåöåíòðàëèçîâàííûì, ýòîò ïðèíöèïìîæíî ïðèìåíÿòü òîëüêî ê äåöåíòðàëèçîâàííûì âîëíîâûìàëãîðèòìàì.Âîëíîâûå àëãîðèòìû èçáðàíèÿ ëèäåðàÇàäà÷à.Äîêàçàòü, ÷òî àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå çàäà÷èîòûñêàíèÿ ýêñòðåìóìîâ ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì, åñëèñîáûòèå èçáðàíèÿ ïðîöåññà ëèäåðîì ðàññìàòðèâàòü êàêñîáûòèå ðåøåíèÿ.Âûáîðû ëèäåðà íà äåðåâåÅñëè òîïîëîãèÿ ñåòè èìååò âèä äåðåâà, èëè â ñåòè åñòüîñòîâíîå äåðåâî, òî äëÿ âûáîðîâ ìîæíî âîñïîëüçîâàâàòüñÿäðåâåñíûì âîëíîâûì àëãîðèòìîì. Íî çäåñü òðåáóåòñÿ, ÷òîáûèíèöèàòîðàìè áûëè âñå ëèñòîâûå âåðøèíû.×òîáû çàïóñòèòü àëãîðèòì, êîãäà ëèøü ÷àñòü ïðîöåññîâÿâëÿþòñÿ èíèöèàòîðàìè, ê íåìó äîáàâëåí ýòàï ïîáóäêè .Ïðîöåññû, çàòåâàþùèå âûáîðû, íàâîäíÿþò ñåòü ñîîáùåíèÿìèwakeup.

Ïîñëå ïîëó÷åíèÿ ñîîáùåíèå wakeup ïî âñåì êàíàëàì,ïðîöåññ çàïóñêàåò äðåâåñíûé âîëíîâîé àëãîðèòì, êîòîðûéñíàáæåí ïðèñòàâêîé äëÿ âû÷èñëåíèÿ íàèìåíüøåãîîòëè÷èòåëüíîãî ïðèçíàêà.Êîãäà ïðîöåññ ïðèíèìàåò ðåøåíèå, îí çíàåò èìÿ ëèäåðà; åñëèýòî èìÿ ñîâïàäàåò ñ îòëè÷èòåëüíûì ïðèçíàêîì ñàìîãîïðîöåññà, òî îí ñòàíîâèòñÿ ëèäåðîì, à â ïðîòèâíîì ñëó÷àå îíïîëó÷àåò ñòàòóñ lost.Âûáîðû ëèäåðà íà äåðåâåwsp: boolinit false ;wrp: integerinit 0 ;recp [q] : bool äëÿ êàæäîãî q ∈ Neighp init false ;vp:Pinit p ;statep : (sleep, leader , lost)init sleep ;(* Ïîáóäêà *)begin if p is initiator thenbegin wsp := true ;forall q ∈ Neighp do send hwakeupi to qend;while wrp < #Neighp dobegin receive hwakeupi ; wrp := wrp + 1 ;if not wsp thenbegin wsp := true ;forall q ∈ Neighp do send hwakeupi to qvarendend;Âûáîðû ëèäåðà íà äåðåâå(* Çäåñü íà÷èíàåò ðàáîòàòü äðåâåñíûé àëãîðèòì *)while #{q : ¬recp [q]} > 1 dobeginreceive htok, r i from q ; recp [q] := true ; vp := min(vp , r );send htok, vp i to q0 with ¬recp [q0 ] ;receive htok, r i from q0 ;vp := min(vp , r ); (* ïðèíÿòü ðåøåíèå ñ îòâåòîì vp *)if vp = p then statep := leader else statep := lost ;forall q ∈ Neighp , q 6= q0 do send htok, vp i to qendendÂûáîðû ëèäåðà íà äåðåâåÒåîðåìà 8.1.Ïðåäëîæåííûé àëãîðèòì ðåøàåò çàäà÷ó î âûáîðàõ íàäðåâåñíûõ ñåòÿõ ñ èñïîëüçîâàíèåì O(N) îáìåíîâñîîáùåíèÿìè, çàòðà÷èâàÿ ïðè ýòîì O(D) åäèíèö âðåìåíè.Äîêàçàòåëüñòâî.Êîãäà õîòü îäèí ïðîöåññ çàïóñêàåò äàííûé àëãîðèòì, âñåïðîöåññû îòïðàâÿò ñîîáùåíèå hwakeupi âñåì ñâîèì ñîñåäÿì, èêàæäûé ïðîöåññ çàïóñòèò âûïîëíåíèå äðåâåñíîãî àëãîðèòìàïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hwakeupi îò êàæäîãî ñîñåäà.

Âñåïðîöåññû çàâåðøàò âûïîëíåíèå äðåâåñíîãî àëãîðèòìà ñ îäíèìè òåì æå çíà÷åíèåì ïåðåìåííîé v , à èìåííî, íàèìåíüøèìîòëè÷èòåëüíûì ïðèçíàêîì ñðåäè âñåõ ïðîöåññîâ (ïî÷åìó? ). Èåäèíñòâåííûé ïðîöåññ ñ òàêèì ïðèçíàêîì çàâåðøèò ðàáîòó âñîñòîÿíèè leader, à âñå ïðî÷èå ïðîöåññû â ñîñòîÿíèè lost.Âûáîðû ëèäåðà íà äåðåâåÄîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó ïåðåäàþòñÿ äâà ñîîáùåíèÿ hwakeupi è äâàñîîáùåíèÿ htok, r i, è ïîýòîìó ñëîæíîñòü ïî ÷èñëó îáìåíîâñîîáùåíèÿìè ñòàíîâèòñÿ ðàâíîé 4N − 4 .Ïî èñòå÷åíèè D åäèíèö âðåìåíè ïîñëå òîãî, êàê ïåðâûéïðîöåññ çàïóñòèë íàø àëãîðèòì, êàæäûé ïðîöåññ óæå îòïðàâèòñîîáùåíèÿ hwakeupi è, ñëåäîâàòåëüíî, ñïóñòÿ D + 1 åäèíèöâðåìåíè êàæäûé ïðîöåññ óæå çàïóñòèò âîëíó.Ïåðâîå ðåøåíèå áóäåò ïðèíÿòî ñïóñòÿ D åäèíèö âðåìåíè ïîñëåíà÷àëà äâèæåíèÿ âîëíû, à ïîñëåäíåå ðåøåíèå áóäåò ïðèíÿòîñïóñòÿ D åäèíèö âðåìåíè ïîñëå ïåðâîãî, è ïîýòîìó îáùååçàòðà÷åííîå âðåìÿ ñòàíîâèòñÿ ðàâíûì 3D + 1 .

Âîëíîâûå àëãîðèòìû èçáðàíèÿ ëèäåðàÇàäà÷è.1. Ïîêàçàòü, ÷òî ñëîæíîñòü ïî âðåìåíè àëãîðèòìà èçáðàíèÿëèäåðà íà äåðåâå ñîñòàâëÿåò 2D .2. Êàêèì îáðàçîì ìîæíî ìîäèôèöèðîâàòü àëãîðèòìèçáðàíèÿ ëèäåðà íà äåðåâå, ÷òîáû ÷èñëî îáìåíîâñîîáùåíèÿìè ñóùåñòâåííî óìåíüøèëîñü?3. Êàê ïðîâåñòè âûáîðû ëèäåðà â ïðîèçâîëüíîé ñåòè ïðèïîìîùè ôàçîâîãî àëãîðèòìà? Êàêîâà áóäåò ñëîæíîñòüòàêîãî àëãîðèòìà èçáðàíèÿ ëèäåðà ïî ÷èñëó îáìåíîâñîîáùåíèÿìè?4. Êàê ïðîâåñòè âûáîðû ëèäåðà â ïðîèçâîëüíîé ñåòè ïðèïîìîùè àëãîðèòìà Ôèííà? Êàêîâà áóäåò ñëîæíîñòü òàêîãîàëãîðèòìà èçáðàíèÿ ëèäåðà ïî ÷èñëó îáìåíîâñîîáùåíèÿìè?Âûáîðû ëèäåðà â êîëüöàõÇàäà÷à î âûáîðàõ â êîëüöåâûõ ñåòÿõ áûëà âïåðâûå ïîñòàâëåíàËå-Ëàííîì â 1977; åìó óäàëîñü íàéòè åå ðåøåíèå ñîñëîæíîñòüþ O(N 2 ) ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè.Ýòî ðåøåíèå áûëî óëó÷øåíî ×åíåì è Ðîáåðòñîì â 1979; îíèïðåäëîæèëè àëãîðèòì, êîòîðûé èìååò ñëîæíîñòü O(N 2 ) âíàèõóäøåì ñëó÷àå, è ñëîæíîñòü O(N log N) â ñðåäíåì.Âîïðîñ î ñóùåñòâîâàíèè àëãîðèòìà ñî ñëîæíîñòüþ O(N log N)â íàèõóäøåì ñëó÷àå îñòàâàëñÿ îòêðûòûì äî 1980, êîãäà òàêîéàëãîðèòì áûë ïðåäëîæåí Õèðøáåðãîì è Ñèíêëåéðîìäâóíàïðàâëåííûõ êîëåö.

Êàêîå-òî âðåìÿ ïðåäïîëàãàëîñü, ÷òîΩ(N 2 ) îáìåíîâ ñîîáùåíèÿìè ñîñòàâëÿþò íèæíþþ îöåíêó äëÿîäíîíàïðàâëåííûõ êîëåö, íî Ïåòåðñîí, à òàêæå Äîëåâ, Êëåéâ èÐîäå â 1982 íåçàâèñèìî ïðåäëîæèëè ðåøåíèå ñëîæíîñòèO(N log N) äëÿ îäíîíàïðàâëåííîãî êîëüöà. Íèæíÿÿ îöåíêà≈ 0.34N log N ñëîæíîñòè ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè âíàèõóäøåì ñëó÷àå äëÿ äâóíàïðàâëåííûõ êîëåö áûëàîáîñíîâàíà Áîäëàåíäýðîì â 1988.Àëãîðèòì Ëå-ËàííàÊàæäûé èíèöèàòîð âû÷èñëÿåò ñïèñîê îòëè÷èòåëüíûõïðèçíàêîâ âñåõ èíèöèàòîðîâ, ïîñëå ÷åãî ëèäåðîì èçáèðàåòñÿèíèöèàòîð ñ íàèìåíüøèì ïðèçíàêîì.Êàæäûé èíèöèàòîð îòïðàâëÿåò ïî êîëüöó ìàðêåð ñî ñâîèìîòëè÷èòåëüíûì ïðèçíàêîì, è âñå ïðîöåññû ïåðåäàþò äàëååýòîò ìàðêåð.

Êàíàëû ïîääåðæèâàþò î÷åðåäíîñòü ñîîáùåíèé.Êîãäà èíèöèàòîð p ïîëó÷àåò ñâîé ñîáñòâåííûé ìàðêåð îáðàòíî,ìàðêåðû âñåõ èíèöèàòîðîâ óæå ïðîøëè ÷åðåç p , è p áóäåòèçáðàí ëèäåðîì â òîì è òîëüêî òîì ñëó÷àå, åñëè p íàèìåíüøèé ïðîöåññ ñðåäè âñåõ èíèöèàòîðîâ.Àëãîðèòì Ëå-ËàííàvarListpstatep ;: ìíîæåñòâî èìåí Pinit{p} ;p is initiator thenbegin statep := cand ; send htok, pi to Nextp ; receive htok, qi ;while q 6= p dobegin Listp := Listp ∪ {q} ;send htok, qi to Nextp ; receive htok, qiend;if p = min(Listp ) then statep := leaderelse statep := lostbegin ifendelse whiletruedoreceive htok, qi ; send htok, qi to Nextp ;if statep = sleep then statep := lostbeginendendÀëãîðèòì Ëå-ËàííàÒåîðåìà 8.2.Àëãîðèòì Ëå-Ëàííà ðåøàåò çàäà÷ó î âûáîðàõ íà êîëüöàõ ñèñïîëüçîâàíèåì O(N 2 ) îáìåíîâ ñîîáùåíèÿìè çà O(N) åäèíèöâðåìåíè.Äîêàçàòåëüñòâî.Òàê êàê ïîðÿäîê ñëåäîâàíèÿ ìàðêåðîâ ïî êîëüöó îñòàåòñÿíåèçìåííûì (ïî÷åìó? ), è èíèöèàòîð q îòïðàâëÿåò htok, qiðàíüøå , ÷åì q ïîëó÷àåò htok, pi, èíèöèàòîð p ïîëó÷àåòhtok, qi äî òîãî, êàê p ïîëó÷èò htok, pi îáðàòíî.Îòñþäà ñëåäóåò, ÷òî êàæäûé èíèöèàòîð p çàâåðøàåò ðàáîòó ñîñïèñêîì Listp èìåí âñåõ èíèöèàòîðîâ, è èíèöèàòîð ñíàèìåíüøèì îòëè÷èòåëüíûì ïðèçíàêîì ñòàíîâèòñÿ ëèäåðîì.Àëãîðèòì Ëå-ËàííàÄîêàçàòåëüñòâî.Âñåãî èñïîëüçóåòñÿ íå áîëåå N ðàçëè÷íûõ ìàðêåðîâ, è êàæäûéèç íèõ ñîâåðøàåò N øàãîâ, ÷òî ïðèâîäèò ê ñëîæíîñòè O(N 2 )ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè.Ñïóñòÿ ñàìîå ïîçäíåå N − 1 åäèíèö âðåìåíè ïîñëå òîãî, êàêïåðâûé èíèöèàòîð îòïðàâèë ñâîé ìàðêåð, êàæäûé èíèöèàòîðïðîäåëàåò òîæå ñàìîå.Ïðè ýòîì êàæäûé èíèöèàòîð ïîëó÷èò ñâîé ìàðêåð îáðàòíî âòå÷åíèå N åäèíèö âðåìåíè ïîñëå ñîçäàíèÿ ýòîãî ìàðêåðà.Çíà÷èò, íàø àëãîðèòì çàâåðøèò ðàáîòó íå ïîçäíåå, ÷åì ñïóñòÿ2N − 1 åäèíèö âðåìåíè.Àëãîðèòì ×åíÿ ÐîáåðòñàÀëãîðèòì ×åíÿ è Ðîáåðòñà óëó÷øàåò àëãîðèòì Ëå-Ëàííà çàñ÷åò òîãî, ÷òî èç êîëüöà èçûìàþòñÿ ìàðêåðû òåõ ïðîöåññîâ,îòíîñèòåëüíî êîòîðûõ óæå ñòàëî ÿñíî, ÷òî îíè ïðîèãðàþòâûáîðû.À èìåííî, èíèöèàòîð p èçûìàåò ìàðêåð htok, qi, åñëè q > p .Èíèöèàòîð p îáðåòàåò ñòàòóñ lost , êàê òîëüêî ïîëó÷àåò ìàðêåðñ îòëè÷èòåëüíûì ïðèçíàêîì q < p , è ñòàòóñ leader, êàê òîëüêîïîëó÷àåò ìàðêåð ñ îòëè÷èòåëüíûì ïðèçíàêîì p .Àëãîðèòì ×åíÿ Ðîáåðòñàvarstatep ;begin ifp is initiator thenstatep := cand ; send htok, pi to Nextp ;while statep 6= leader dobegin receive htok, qi ;if q = p then statep := leaderelse if q < p thenbegin if statep = cand then statep := lost;send htok, qi to Nextp endbeginendendtrue doreceive htok, qi ; send htok, qi to Nextp ;if statep = sleep then statep := lostelse whilebeginendendÀëãîðèòì ×åíÿ ÐîáåðòñàÒåîðåìà 8.3.Àëãîðèòì ×åíÿ Ðîáåðòñà ðåøàåò çàäà÷ó î âûáîðàõ íàêîëüöàõ ñ èñïîëüçîâàíèåì Θ(N 2 ) îáìåíîâ ñîîáùåíèÿìè âíàèõóäøåì ñëó÷àå è çà O(N) åäèíèö âðåìåíè.Äîêàçàòåëüñòâî.Îáîçíà÷èì p0 èíèöèàòîðà ñ íàèìåíüøèì èìåíåì.Âñÿêèé äðóãîé ïðîöåññ ìîæåò áûòü ëèáî íå-èíèöèàòîðîì, ëèáîèíèöèàòîðîì ñ îòëè÷èòåëüíûì ïðèçíàêîì, ïðåâûøàþùèì p0 ,è ïîýòîìó âñå ïðîöåññû ïåðåäàäóò äàëåå ìàðêåð htok, p0 iâûïóùåííûé p0 .Çíà÷èò, p0 ïîëó÷èò ñâîé ìàðêåð îáðàòíî è áóäåò èçáðàíëèäåðîì.Àëãîðèòì ×åíÿ ÐîáåðòñàÄîêàçàòåëüñòâî.Íå-èíèöèàòîðû íå áóäóò èçáðàíû, íî âñå îíè ïåðåéäóò âñîñòîÿíèå lost ñàìîå ïîçäíåå ê ìîìåíòó ïåðåäà÷è ìàðêåðà,êîòîðûé âûïóñòèë p0 .Èíèöèàòîð p , äëÿ êîòîðîãî p > p0 , íå ñòàíåò ëèäåðîì, ò.ê.