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

p0íå ïåðåäàñò äàëåå ìàðêåð htok, pi, è ïîýòîìó p íèêîãäà íåïîëó÷èò ñâîé ñîáñòâåííûé ìàðêåð.Òàêîé èíèöèàòîð p ïåðåéäåò â ñîñòîÿíèå lost ñàìîå ïîçäíåå âòîò ìîìåíò, êîãäà áóäåò ïåðåäàâàòü äàëåå htok, p0 i.Ýòî è ñëóæèò îáîñíîâàíèåì òîãî, ÷òî íàø àëãîðèòì ðåøàåòçàäà÷ó î âûáîðàõ.Àëãîðèòì ×åíÿ ÐîáåðòñàÄîêàçàòåëüñòâî. àëãîðèòìå çàäåéñòâîâàíî íå áîëåå 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 îáìåíîâ ñîîáùåíèÿìè, êîãäà âñå ïðîöåññûÿâëÿþòñÿ èíèöèàòîðàìè.Çàäà÷è.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 (ò.

e. â ýòîìñëó÷àå p = q ). Êàê òîëüêî ñëîæèòñÿ òàêàÿ ñèòóàöèÿ, äàííûéîòëè÷èòåëüíûé ïðèçíàê ñòàíîâèòñÿ ïîáåäèòåëåì íà âûáîðàõ.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåp7p3- p2@@@R@p56?p4I@@@@p1p6p8Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 137p7p342- p2@@@5R@p56? 6p4I@@@@p11p6p88Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 173p72- p2 7@@@5R@34641? 6p3p5p4I@@@@p118p625p886Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 1734p72- p2 7@3@@5R@34167418? 6p3p5p4I@@@@p1186p6252p8865Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå734ÒÓÐ 1p7341418p3passive2- p2 7@3passive@@5R@p5627passivep4I@@@ passive@p1186passivep8865? 6p652Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 23p7p3passive- p2@passive@@R@p5612p4I@@@ passive@p1passivepassivep8?p6Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 231p7p3passive- p2@passive@@R@p561223p4I@@@ passive@p1passivepassivep8?p6Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 2371 2pp3passive- p2@passive@@R@p56123231p4I@@@ passive@p1passivepassivep8?p6Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 2371 2pp3passive6123- p2@passive@@R@passivep5231p4passiveI@@@ passive@p1passivepassivep8?p6Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 3p71p3passive6- p2@passive@@R@passivep4passiveI@@@ passive@p1passivepassivep8p5?p6Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒÓÐ 3p71 1p3passive6- p2@passive@@R@passivep4passiveI@@@ passive@p1passivepassivep8p5?p6Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåleader=1ÒÓÐ 3p71 1p3passive6- p2@passive@@R@passivep4passiveI@@@ passive@p1passivepassivep8p5?p6Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåcip : P init p ;(* Òåêóùèé ïðèçíàê ïðîöåññà p *)acnp : P init udef ;(* Ïðèçíàê àêòèâíîãî ñîñåäà*)winp : P init udef ;(* Ïðèçíàê ïîáåäèòåëÿ *)statep : (active , passive , leader , lost ) init active ;begin if p is initiator then statep := active else statep := passive ;while winp = udef dobegin if statep = active thenbegin send hone, cip i; receive hone, qi ; acnp := q ;if acnp = cip then (* acnp ìèíèìàëüíûé *)begin send hsmall, acnp i ; winp := acnp ;receive hsmall, qivarendelse(* acnp òåêóùèé ïðèçíàê ñîñåäà *)send htwo, acnp i; receive htwo, qi ;if acnp < cip and acnp < qthen cip := acnp else statep := passivebeginendÀëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå(* statep = passive *)begin receive hone, qi ; send hone, qi ;receive m ; send m ;(* m ýòî ëèáî htwo, qi, ëèáî hsmall, qi*)if m ýòî ñîîáùåíèå hsmall, qi then winp := qelseend;p = winpendifendthenstatep := leaderelsestatep := lostÀëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÏðîöåññ p ÿâëÿåòñÿ àêòèâíûì â íåêîòîðîì òóðå, åñëè â íà÷àëåòóðà îí õðàíèò àêòèâíûé îòëè÷èòåëüíûé ïðèçíàê cip .

Âïðîòèâíîì ñëó÷àå p ÿâëÿåòñÿ ïàññèâíûì è ïðîñòîðåòðàíñëèðóåò âñå ñîîáùåíèÿ, êîòîðûå îí ïîëó÷àåò.Âñÿêèé àêòèâíûé ïðîöåññ îòïðàâëÿåò ñâîé òåêóùèé îòëè÷èòåëüíûé ïðèçíàê ñëåäóþùåìó ïî ïîðÿäêó àêòèâíîìó ïðîöåññó èïîëó÷àåò òåêóùèé îòëè÷èòåëüíûé ïðèçíàê îò ïðåäøåñòâóþùåãîàêòèâíîãî ïðîöåññà, èñïîëüçóÿ ñîîáùåíèÿ òèïà honei.Ïîëó÷åííûé ïðèçíàê ñîõðàíÿåòñÿ â ïàìÿòè (â êà÷åñòâåçíà÷åíèÿ ïåðåìåííîé acnp ).Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåcip : P init p ;(* Òåêóùèé ïðèçíàê ïðîöåññà p *)acnp : P init udef ;(* Ïðèçíàê àêòèâíîãî ñîñåäà *)winp : P init udef ;(* Ïðèçíàê ïîáåäèòåëÿ *)statep : (active , passive , leader , lost ) init active ;begin if p is initiator then statep := active else statep := passive ;while winp = udef dobegin if statep = active thenbegin send hone, cip i; receive hone, qi ; acnp := q ;if acnp = cip then (* acnp ìèíèìàëüíûé *)begin send hsmall, acnp i ; winp := acnp ;receive hsmall, qivarendelse(* acnp òåêóùèé ïðèçíàê ñîñåäà *)send htwo, acnp i; receive htwo, qi ;if acnp < cip and acnp < qthen cip := acnp else statep := passivebeginendÀëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÏîëó÷åííûé ïðèçíàê ñîõðàíÿåòñÿ â ïàìÿòè (â êà÷åñòâåçíà÷åíèÿ ïåðåìåííîé acnp ), è åñëè äàííûé ïðèçíàê ïåðåæèâåòýòîò òóð, òî îí ñòàíåò òåêóùèì îòëè÷èòåëüíûì ïðèçíàêîìïðîöåññà p â ñëåäóþùåì òóðå.×òîáû îöåíèòü, ïåðåæèâåò ëè îòëè÷èòåëüíûé ïðèçíàê acnpäàííûé òóð, åãî íóæíî ñðàâíèòü êàê ñ cip , òàê è ñ àêòèâíûìïðèçíàêîì, ïîëó÷åííûì â ñîîáùåíèè òèïà htwoi .Ïðîöåññ p îòïðàâëÿåò ñîîáùåíèå htwo, acpp i, ÷òîáûïðåäîñòàâèòü òàêóþ âîçìîæíîñòü ñëåäóþùåìó ïî ïîðÿäêóàêòèâíîìó ïðîöåññó.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåcip : P init p ;(* Òåêóùèé ïðèçíàê ïðîöåññà p *)acnp : P init udef ;(* Ïðèçíàê àêòèâíîãî ñîñåäà *)winp : P init udef ;(* Ïðèçíàê ïîáåäèòåëÿ *)statep : (active , passive , leader , lost ) init active ;begin if p is initiator then statep := active else statep := passive ;while winp = udef dobegin if statep = active thenbegin send hone, cip i; receive hone, qi ; acnp := q ;if acnp = cip then (* acnp ìèíèìàëüíûé *)begin send hsmall, acnp i ; winp := acnp ;receive hsmall, qivarendelse(* acnp òåêóùèé ïðèçíàê ñîñåäà *)send htwo, acnp i; receive htwo, qi ;if acnp < cip and acnp < qthen cip := acnp else statep := passivebeginendÀëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÈñêëþ÷èòåëüíûì ÿâëÿåòñÿ òîò ñëó÷àé, êîãäà âûïîëíÿåòñÿðàâåíñòâî acnp = cip ; òîãäà äàííûé îòëè÷èòåëüíûé ïðèçíàêîñòàåòñÿ åäèíñòâåííûì àêòèâíûì ïðèçíàêîì, è ñîîáùåíèåhsmall, acnp i îïîâåùàåò îá ýòîì âñå ïðîöåññû.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåcip : P init p ;(* Òåêóùèé ïðèçíàê ïðîöåññà p *)acnp : P init udef ;(* Ïðèçíàê àêòèâíîãî ñîñåäà *)winp : P init udef ;(* Ïðèçíàê ïîáåäèòåëÿ *)statep : (active , passive , leader , lost ) init active ;begin if p is initiator then statep := active else statep := passive ;while winp = udef dobegin if statep = active thenbegin send hone, cip i; receive hone, qi ; acnp := q ;if acnp = cip then (* acnp ìèíèìàëüíûé *)begin send hsmall, acnp i ; winp := acnp ;receive hsmall, qivarendelse(* acnp òåêóùèé ïðèçíàê ñîñåäà *)send htwo, acnp i; receive htwo, qi ;if acnp < cip and acnp < qthen cip := acnp else statep := passivebeginendÀëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.5.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå ðåøàåò çàäà÷ó îâûáîðàõ äëÿ îäíîíàïðàâëåííûõ êîëåö ñ èñïîëüçîâàíèåìO(N log N) îáìåíîâ ñîîáùåíèÿìè.Äîêàçàòåëüñòâî.Áóäåì ãîâîðèòü, ÷òî ïðîöåññ ó÷àñòâóåò â i -îì òóðå, åñëèîñíîâíîé öèêë ýòîãî ïðîöåññà âûïîëíÿåòñÿ i -é ðàç.Òóðû íå ñèíõðîíèçèðîâàíû, è âîçìîæíà êîíôèãóðàöèÿ, âêîòîðîé îäèí èç ïðîöåññîâ îïåðåæàåò íà íåñêîëüêî òóðîâäðóãîé ïðîöåññ, ðàñïîëîæåííûé â èíîé ÷àñòè êîëüöà.Íî òàê êàê êàæäûé ïðîöåññ îòïðàâëÿåò è ïîëó÷àåò â êàæäîìòóðå ðîâíî äâà ñîîáùåíèÿ, è â êàíàëàõ ïîääåðæèâàåòñÿî÷åðåäíîñòü ïîñëàíèé, ïîëó÷àòåëü âñÿêîãî ñîîáùåíèÿ áóäåòó÷àñòâîâàòü â òîì æå òóðå, ÷òî è åãî îòïðàâèòåëü. ïåðâîì òóðå âñå èíèöèàòîðû àêòèâíû , è êàæäûé àêòèâíûéïðîöåññ õðàíèò ñâîé ¾òåêóùèé îòëè÷èòåëüíûé ïðèçíàê¿.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÓòâåðæäåíèå 1.Åñëè â íà÷àëå i -ãî òóðà èìååòñÿ k > 1 àêòèâíûõ ïðîöåññîâ, èâñå ¾òåêóùèå îòëè÷èòåëüíûå ïðèçíàêè¿ ci , õðàíèìûå ýòèìèïðîöåññàìè, ïîïàðíî ðàçëè÷íû, òî â ñëåäóþùèé òóð ïåðåéäåòíå ìåíåå îäíîãî è íå áîëåå k/2 ïðîöåññîâ.Ïî îêîí÷àíèè i -ãî òóðà òåêóùèå îòëè÷èòåëüíûå ïðèçíàêèàêòèâíûõ ïðîöåññîâ áóäóò âíîâü ïîïàðíî ðàçëè÷íû, è ñðåäèíèõ áóäåò íàõîäèòüñÿ ñàìûé ìëàäøèé ïðèçíàê.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî óòâåðæäåíèÿ 1.Ïîñëå îáìåíà ñîîáùåíèÿìè âèäà hone, qi êàæäûé àêòèâíûéïðîöåññ ïîëó÷èò òåêóùèé îòëè÷èòåëüíûé ïðèçíàê ñâîåãîáëèæàéøåãî àêòèâíîãî ñîñåäà, ðàñïîëîæåííîãî ïðîòèâ õîäà÷àñîâîé ñòðåëêè.