Лекция 9. Задача избрания лидера. Выборы лидера на дереве_ в кольцах. Алгоритм Ле-Ланна_ ... Эффект угасания, страница 2

Êàêîå-òî âðåìÿ ïðåäïîëàãàëîñü, ÷òîΩ(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) åäèíèöâðåìåíè.Àëãîðèòì Ëå-ËàííàÒåîðåìà 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 ðàçëè÷íûõ ìàðêåðîâ, è êàæäûéèç íèõ ñîâåðøàåò 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) åäèíèö âðåìåíè.Àëãîðèòì ×åíÿ ÐîáåðòñàÒåîðåìà 8.3.Àëãîðèòì ×åíÿ Ðîáåðòñà ðåøàåò çàäà÷ó î âûáîðàõ íàêîëüöàõ ñ èñïîëüçîâàíèåì Θ(N 2 ) îáìåíîâ ñîîáùåíèÿìè âíàèõóäøåì ñëó÷àå è çà O(N) åäèíèö âðåìåíè.Äîêàçàòåëüñòâî.Îáîçíà÷èì p0 èíèöèàòîðà ñ íàèìåíüøèì èìåíåì.Âñÿêèé äðóãîé ïðîöåññ ìîæåò áûòü ëèáî íå-èíèöèàòîðîì, ëèáîèíèöèàòîðîì ñ îòëè÷èòåëüíûì ïðèçíàêîì, ïðåâûøàþùèì p0 ,è ïîýòîìó âñå ïðîöåññû ïåðåäàäóò äàëåå ìàðêåð htok, p0 iâûïóùåííûé p0 .

Çíà÷èò, p0 ïîëó÷èò ñâîé ìàðêåð îáðàòíî èáóäåò èçáðàí ëèäåðîì.Àëãîðèòì ×åíÿ ÐîáåðòñàÄîêàçàòåëüñòâî.Íå-èíèöèàòîðû íå áóäóò èçáðàíû, íî âñå îíè ïåðåéäóò âñîñòîÿíèå lost ñàìîå ïîçäíåå ê ìîìåíòó ïåðåäà÷è ìàðêåðà,êîòîðûé âûïóñòèë p0 .Èíèöèàòîð p , äëÿ êîòîðîãî p > p0 , íå ñòàíåò ëèäåðîì, ò.ê. p0íå ïåðåäàñò äàëåå ìàðêåð htok, pi, è ïîýòîìó p íèêîãäà íåïîëó÷èò ñâîé ñîáñòâåííûé ìàðêåð.Òàêîé èíèöèàòîð p ïåðåéäåò â ñîñòîÿíèå lost ñàìîå ïîçäíåå âòîò ìîìåíò, êîãäà áóäåò ïåðåäàâàòü äàëåå htok, p0 i.Ýòî è ñëóæèò îáîñíîâàíèåì òîãî, ÷òî íàø àëãîðèòì ðåøàåòçàäà÷ó î âûáîðàõ.Àëãîðèòì ×åíÿ ÐîáåðòñàÄîêàçàòåëüñòâî. àëãîðèòìå çàäåéñòâîâàíî íå áîëåå N ðàçëè÷íûõ ìàðêåðîâ, èêàæäûé ìàðêåð ïåðåäàåòñÿ íå áîëåå N ðàç; ýòèì èîáîñíîâûâàåòñÿ îöåíêà O(N 2 ) ñëîæíîñòè ïî ÷èñëó îáìåíîâñîîáùåíèÿìè.Àëãîðèòì ×åíÿ ÐîáåðòñàÄîêàçàòåëüñòâî. àëãîðèòìå çàäåéñòâîâàíî íå áîëåå N ðàçëè÷íûõ ìàðêåðîâ, èêàæäûé ìàðêåð ïåðåäàåòñÿ íå áîëåå N ðàç; ýòèì èîáîñíîâûâàåòñÿ îöåíêà O(N 2 ) ñëîæíîñòè ïî ÷èñëó îáìåíîâñîîáùåíèÿìè.×òîáû óáåäèòüñÿ â òîì, ÷òî ìîæåò èíîãäà ìîæåò ïîíàäîáèòüñÿïåðåäàòü Ω(N 2 ) ñîîáùåíèé, ðàññìîòðèì íà÷àëüíóþêîíôèãóðàöèþ, â êîòîðîé îòëè÷èòåëüíûå ïðèçíàêèðàñïîëîæåíû â êîëüöå ïî âîçðàñòàíèþ, è êàæäûé ïðîöåññÿâëÿåòñÿ èíèöèàòîðîì.Àëãîðèòì ×åíÿ ÐîáåðòñàÄîêàçàòåëüñòâî.N −10ttHHt1AAAAtiHHÑîîáùåíèÿ ïåðåäàþòñÿïî ÷àñîâîé ñòðåëêåÀëãîðèòì ×åíÿ ÐîáåðòñàÄîêàçàòåëüñòâî. àëãîðèòìå çàäåéñòâîâàíî íå áîëåå N ðàçëè÷íûõ ìàðêåðîâ, èêàæäûé ìàðêåð ïåðåäàåòñÿ íå áîëåå N ðàç; ýòèì èîáîñíîâûâàåòñÿ îöåíêà O(N 2 ) ñëîæíîñòè ïî ÷èñëó îáìåíîâñîîáùåíèÿìè.×òîáû óáåäèòüñÿ â òîì, ÷òî ìîæåò èíîãäà ìîæåò ïîíàäîáèòüñÿïåðåäàòü Ω(N 2 ) ñîîáùåíèé, ðàññìîòðèì íà÷àëüíóþêîíôèãóðàöèþ, â êîòîðîé îòëè÷èòåëüíûå ïðèçíàêèðàñïîëîæåíû â êîëüöå ïî âîçðàñòàíèþ, è êàæäûé ïðîöåññÿâëÿåòñÿ èíèöèàòîðîì.Ìàðêåð êàæäîãî ïðîöåññà èçûìàåòñÿ èç êîëüöà ïðîöåññîì 0 , èïîýòîìó ìàðêåð ïðîöåññà i ñîâåðøàåò N − i ïåðåõîäîâ; ýòîïðèâîäèò ê òîìó, ÷òî ÷èñëî ïåðåäà÷ ñîîáùåíèé áóäåò ðàâíîN−1P(N − i) = 12 N(N + 1) .i=0Àëãîðèòì ×åíÿ ÐîáåðòñàÒåîðåìà 8.4.Àëãîðèòìó ×åíÿÐîáåðòñà â ñðåäíåì òðåáóåòñÿ âñåãî ëèøü≈ 0.69N log N îáìåíîâ ñîîáùåíèÿìè, êîãäà âñå ïðîöåññûÿâëÿþòñÿ èíèöèàòîðàìè.Àëãîðèòì ×åíÿ ÐîáåðòñàÒåîðåìà 8.4.Àëãîðèòìó ×åíÿÐîáåðòñà â ñðåäíåì òðåáóåòñÿ âñåãî ëèøü≈ 0.69N log N îáìåíîâ ñîîáùåíèÿìè, êîãäà âñå ïðîöåññûÿâëÿþòñÿ èíèöèàòîðàìè.Çàäà÷è.1.

Çàâèñèò ëè êîððåêòíîñòü àëãîðèòìà ×åíÿÐîáåðòñà îòî÷åðåäíîñòè ïåðåäà÷è ñîîáùåíèé â êàíàëàõ?2. Ðàññìîòðèì àëãîðèòì ×åíÿÐîáåðòñà, ïîëàãàÿ, ÷òîêàæäûé ïðîöåññ ÿâëÿåòñÿ èíèöèàòîðîì. Ïðè êàêîìðàñïîëîæåíèè îòëè÷èòåëüíûõ ïðèçíàêîâ â êîëüöåñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè áóäåòìèíèìàëüíîé, è ñêîëüêî îáìåíîâ ñîîáùåíèÿìèïîòðåáóåòñÿ â ýòîì ñëó÷àå?Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå äàííîì àëãîðèòìå òðåáóåòñÿ, ÷òîáû â êàíàëàõïîääåðæèâàëàñü î÷åðåäíîñòü ñîîáùåíèé.Âíà÷àëå àëãîðèòì âû÷èñëÿåò íàèìåíüøèé îòëè÷èòåëüíûéïðèçíàê è äîâîäèò åãî äî ñâåäåíèÿ âñåõ ïðîöåññîâ; çàòåìïðîöåññ ñ óêàçàííûì îòëè÷èòåëüíûì ïðèçíàêîì ñòàíîâèòñÿëèäåðîì, à âñå îñòàëüíûå ïðîöåññû ïðèçíàþò ñâîå ïîðàæåíèåíà âûáîðàõ.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå äàííîì àëãîðèòìå òðåáóåòñÿ, ÷òîáû â êàíàëàõïîääåðæèâàëàñü î÷åðåäíîñòü ñîîáùåíèé.Âíà÷àëå àëãîðèòì âû÷èñëÿåò íàèìåíüøèé îòëè÷èòåëüíûéïðèçíàê è äîâîäèò åãî äî ñâåäåíèÿ âñåõ ïðîöåññîâ; çàòåìïðîöåññ ñ óêàçàííûì îòëè÷èòåëüíûì ïðèçíàêîì ñòàíîâèòñÿëèäåðîì, à âñå îñòàëüíûå ïðîöåññû ïðèçíàþò ñâîå ïîðàæåíèåíà âûáîðàõ.Ñóòü ýòîãî àëãîðèòìà áóäåò ïðîùå ïîíÿòü, åñëè âçãëÿíóòü íàíåãî òàê, êàê áóäòî àëãîðèòì âûïîëíÿþò íå ñàìè ïðîöåññû, àèõ îòëè÷èòåëüíûå ïðèçíàêè .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÏåðâîíà÷àëüíî êàæäûé îòëè÷èòåëüíûé ïðèçíàê ÿâëÿåòñÿàêòèâíûì , íî â êàæäîì òóðå íåêîòîðûå îòëè÷èòåëüíûåïðèçíàêè ñòàíîâÿòñÿ ïàññèâíûìè .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÏåðâîíà÷àëüíî êàæäûé îòëè÷èòåëüíûé ïðèçíàê ÿâëÿåòñÿàêòèâíûì , íî â êàæäîì òóðå íåêîòîðûå îòëè÷èòåëüíûåïðèçíàêè ñòàíîâÿòñÿ ïàññèâíûìè .Âû÷èñëåíèå ðàçáèòî íà òóðû.

 êàæäîì òóðå âñÿêèé àêòèâíûéîòëè÷èòåëüíûé ïðèçíàê ñðàâíèâàåòñÿ ñ äâóìÿ ñîñåäíèìèàêòèâíûìè îòëè÷èòåëüíûìè ïðèçíàêàìè, ðàñïîëîæåííûìè ïîõîäó è ïðîòèâ õîäà ÷àñîâîé ñòðåëêè. Åñëè ýòîò ïðèçíàê áóäåòìèíèìàëüíûì èç òðåõ, òî îí ïåðåõîäèò â ñëåäóþùèé òóð, àèíà÷å îí ñòàíîâèòñÿ ïàññèâíûì .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÏåðâîíà÷àëüíî êàæäûé îòëè÷èòåëüíûé ïðèçíàê ÿâëÿåòñÿàêòèâíûì , íî â êàæäîì òóðå íåêîòîðûå îòëè÷èòåëüíûåïðèçíàêè ñòàíîâÿòñÿ ïàññèâíûìè .Âû÷èñëåíèå ðàçáèòî íà òóðû.  êàæäîì òóðå âñÿêèé àêòèâíûéîòëè÷èòåëüíûé ïðèçíàê ñðàâíèâàåòñÿ ñ äâóìÿ ñîñåäíèìèàêòèâíûìè îòëè÷èòåëüíûìè ïðèçíàêàìè, ðàñïîëîæåííûìè ïîõîäó è ïðîòèâ õîäà ÷àñîâîé ñòðåëêè. Åñëè ýòîò ïðèçíàê áóäåòìèíèìàëüíûì èç òðåõ, òî îí ïåðåõîäèò â ñëåäóþùèé òóð, àèíà÷å îí ñòàíîâèòñÿ ïàññèâíûì .Òàê êàê âñå îòëè÷èòåëüíûå ïðèçíàêè ïîïàðíî ðàçëè÷íû,îòëè÷èòåëüíûå ïðèçíàêè, ðàñïîëîæåííûå ïî îáå ñòîðîíû îòëîêàëüíîãî ìèíèìóìà, ñòàíóò ïàññèâíûìè, è ïîýòîìó, ïîêðàéíåé ìåðå, ïîëîâèíà îòëè÷èòåëüíûõ ïðèçíàêîâ íå ïåðåéäåòâ ñëåäóþùèé òóð.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÏåðâîíà÷àëüíî êàæäûé îòëè÷èòåëüíûé ïðèçíàê ÿâëÿåòñÿàêòèâíûì , íî â êàæäîì òóðå íåêîòîðûå îòëè÷èòåëüíûåïðèçíàêè ñòàíîâÿòñÿ ïàññèâíûìè .Âû÷èñëåíèå ðàçáèòî íà òóðû.

 êàæäîì òóðå âñÿêèé àêòèâíûéîòëè÷èòåëüíûé ïðèçíàê ñðàâíèâàåòñÿ ñ äâóìÿ ñîñåäíèìèàêòèâíûìè îòëè÷èòåëüíûìè ïðèçíàêàìè, ðàñïîëîæåííûìè ïîõîäó è ïðîòèâ õîäà ÷àñîâîé ñòðåëêè. Åñëè ýòîò ïðèçíàê áóäåòìèíèìàëüíûì èç òðåõ, òî îí ïåðåõîäèò â ñëåäóþùèé òóð, àèíà÷å îí ñòàíîâèòñÿ ïàññèâíûì .Òàê êàê âñå îòëè÷èòåëüíûå ïðèçíàêè ïîïàðíî ðàçëè÷íû,îòëè÷èòåëüíûå ïðèçíàêè, ðàñïîëîæåííûå ïî îáå ñòîðîíû îòëîêàëüíîãî ìèíèìóìà, ñòàíóò ïàññèâíûìè, è ïîýòîìó, ïîêðàéíåé ìåðå, ïîëîâèíà îòëè÷èòåëüíûõ ïðèçíàêîâ íå ïåðåéäåòâ ñëåäóþùèé òóð.Ñëåäîâàòåëüíî, ñïóñòÿ ñàìîå áîëüøåå log N òóðîâ, îñòàíåòñÿòîëüêî îäèí àêòèâíûé îòëè÷èòåëüíûé ïðèçíàê, êîòîðûé èáóäåò ïðèçíàí ïîáåäèòåëåì.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåer ue e eqHHuHeAeAAupu Àêòèâíûé ïðîöåññe Ïàññèâíûé ïðîöåññ îðèåíòèðîâàííûõ êîëüöàõ ñîîáùåíèÿ ìîæíî ïåðåäàâàòüòîëüêî ïî ÷àñîâîé ñòðåëêå, è ýòî çàòðóäíÿåò ïîëó÷åíèå ïåðâîãîñîñåäíåãî ïî õîäó ÷àñîâîé ñòðåëêè îòëè÷èòåëüíîãî ïðèçíàêà.Îòëè÷èòåëüíûé ïðèçíàê q íåîáõîäèìî ñðàâíèòü ñ r è p ; íîåñëè ïðèçíàê r ìîæåò áûòü ëåãêî ïåðåäàí q , òî ïðèçíàê pâûíóæäåí áûë áû äâèãàòüñÿ â íàïðàâëåíèè, ïðîòèâîïîëîæíîìîðèåíòàöèè êàíàëîâ, ÷òîáû äîñòè÷ü q .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåer ue e e qHHuHeAeAAupu Àêòèâíûé ïðîöåññe Ïàññèâíûé ïðîöåññÄëÿ òîãî, ÷òîáû ñäåëàòü âîçìîæíûì ïðîâåäåíèå ñðàâíåíèÿ ñîáîèìè ïðèçíàêàìè r è p , îòëè÷èòåëüíûé ïðèçíàê qïåðåäàåòñÿ (ïî íàïðàâëåíèþ êàíàëîâ â êîëüöå) òîìó ïðîöåññó,êîòîðûé â ýòîò ìîìåíò ÿâëÿåòñÿ õðàíèòåëåì p , à rïåðåïðàâëÿåòñÿ íå òîëüêî ïðîöåññó, õðàíÿùåìó q , íî òàêæå èäàëåå ïðîöåññó, õðàíÿùåìó p .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåer ue e e qHHuHeAeAAupu Àêòèâíûé ïðîöåññe Ïàññèâíûé ïðîöåññÅñëè q îñòàåòñÿ åäèíñòâåííûì àêòèâíûì îòëè÷èòåëüíûìïðèçíàêîì â íà÷àëå íåêîòîðîãî òóðà, òî ïåðâûé æå ïðèçíàê,êîòîðûé áóäåò ïåðåäàí q â ýòîì òóðå, áóäåò ðàâåí q (ò.