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

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 ÿâëÿåòñÿ ïàññèâíûì è ïðîñòîðåòðàíñëèðóåò âñå ñîîáùåíèÿ, êîòîðûå îí ïîëó÷àåò.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÏðîöåññ 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) îáìåíîâ ñîîáùåíèÿìè.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.5.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå ðåøàåò çàäà÷ó îâûáîðàõ äëÿ îäíîíàïðàâëåííûõ êîëåö ñ èñïîëüçîâàíèåìO(N log N) îáìåíîâ ñîîáùåíèÿìè.Äîêàçàòåëüñòâî.Áóäåì ãîâîðèòü, ÷òî ïðîöåññ ó÷àñòâóåò â i -îì òóðå, åñëèîñíîâíîé öèêë ýòîãî ïðîöåññà âûïîëíÿåòñÿ i -é ðàç.

Òóðû íåñèíõðîíèçèðîâàíû ãëîáàëüíî; âîçìîæíà ñèòóàöèÿ, ïðè êîòîðîéîäèí èç ïðîöåññîâ îïåðåæàåò íà íåñêîëüêî òóðîâ äðóãîéïðîöåññ, ðàñïîëîæåííûé â èíîé ÷àñòè êîëüöà. Íî êîëü ñêîðîêàæäûé ïðîöåññ îòïðàâëÿåò è ïîëó÷àåò â êàæäîì òóðå ðîâíîäâà ñîîáùåíèÿ, è â êàíàëàõ ïîääåðæèâàåòñÿ î÷åðåäíîñòüïîñëàíèé, ïîëó÷àòåëü âñÿêîãî ñîîáùåíèÿ áóäåò ó÷àñòâîâàòü âòîì æå òóðå, â êîòîðîì íàõîäèëñÿ åãî îòïðàâèòåëü.  ïåðâîìòóðå âñå èíèöèàòîðû àêòèâíû , è êàæäûé àêòèâíûé ïðîöåññõðàíèò èíäèâèäóàëüíûé ¾òåêóùèé îòëè÷èòåëüíûé ïðèçíàê¿.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÓòâåðæäåíèå 1.Åñëè â íà÷àëå i -ãî òóðà èìååòñÿ k > 1 àêòèâíûõ ïðîöåññîâ, èâñå ¾òåêóùèå îòëè÷èòåëüíûå ïðèçíàêè¿ ci , õðàíèìûå ýòèìèïðîöåññàìè, ïîïàðíî ðàçëè÷íû, òî â ñëåäóþùèé òóð ïåðåéäåòíå ìåíåå îäíîãî è íå áîëåå k/2 ïðîöåññîâ.

Ïî îêîí÷àíèè i -ãîòóðà òåêóùèå îòëè÷èòåëüíûå ïðèçíàêè àêòèâíûõ ïðîöåññîâáóäóò âíîâü ïîïàðíî ðàçëè÷íû, è ñðåäè íèõ áóäåò íàõîäèòüñÿñàìûé ìëàäøèé ïðèçíàê.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî óòâåðæäåíèÿ 1.Ïîñëå îáìåíà ñîîáùåíèÿìè âèäà hone, qi êàæäûé àêòèâíûéïðîöåññ ïîëó÷èò òåêóùèé îòëè÷èòåëüíûé ïðèçíàê ñâîåãîáëèæàéøåãî àêòèâíîãî ñîñåäà, ðàñïîëîæåííîãî ïðîòèâ õîäà÷àñîâîé ñòðåëêè. Ýòîò ïðèçíàê áóäåò íå ñîâïàäàòü ñ åãîñîáñòâåííûì îòëè÷èòåëüíûì ïðèçíàêîì.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî óòâåðæäåíèÿ 1.Ïîñëå îáìåíà ñîîáùåíèÿìè âèäà hone, qi êàæäûé àêòèâíûéïðîöåññ ïîëó÷èò òåêóùèé îòëè÷èòåëüíûé ïðèçíàê ñâîåãîáëèæàéøåãî àêòèâíîãî ñîñåäà, ðàñïîëîæåííîãî ïðîòèâ õîäà÷àñîâîé ñòðåëêè.

Ýòîò ïðèçíàê áóäåò íå ñîâïàäàòü ñ åãîñîáñòâåííûì îòëè÷èòåëüíûì ïðèçíàêîì.Ñëåäîâàòåëüíî, êàæäûé àêòèâíûé ïðîöåññ ïðîäîëæèò ýòîò òóð,è ïðîèçîéäåò îáìåí ñîîáùåíèÿìè âèäà htwo, qi. Ïîýòîìóêàæäûé àêòèâíûé ïðîöåññ ïîëó÷èò òàêæå òåêóùèéîòëè÷èòåëüíûé ïðèçíàê âòîðîãî ïî áëèçîñòè àêòèâíîãî ñîñåäà,ðàñïîëîæåííîãî ïðîòèâ õîäà ÷àñîâîé ñòðåëêè.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî óòâåðæäåíèÿ 1.Ïîñëå îáìåíà ñîîáùåíèÿìè âèäà hone, qi êàæäûé àêòèâíûéïðîöåññ ïîëó÷èò òåêóùèé îòëè÷èòåëüíûé ïðèçíàê ñâîåãîáëèæàéøåãî àêòèâíîãî ñîñåäà, ðàñïîëîæåííîãî ïðîòèâ õîäà÷àñîâîé ñòðåëêè. Ýòîò ïðèçíàê áóäåò íå ñîâïàäàòü ñ åãîñîáñòâåííûì îòëè÷èòåëüíûì ïðèçíàêîì.Ñëåäîâàòåëüíî, êàæäûé àêòèâíûé ïðîöåññ ïðîäîëæèò ýòîò òóð,è ïðîèçîéäåò îáìåí ñîîáùåíèÿìè âèäà htwo, qi. Ïîýòîìóêàæäûé àêòèâíûé ïðîöåññ ïîëó÷èò òàêæå òåêóùèéîòëè÷èòåëüíûé ïðèçíàê âòîðîãî ïî áëèçîñòè àêòèâíîãî ñîñåäà,ðàñïîëîæåííîãî ïðîòèâ õîäà ÷àñîâîé ñòðåëêè.Âñå àêòèâíûå ïðîöåññû òåïåðü õðàíÿò ðàçíûå çíà÷åíèÿ acn , àýòî îçíà÷àåò, ÷òî ïðîöåññû, âûäåðæàâøèå ýòîò òóð, áóäóò âêîíöå åãî õðàíèòü ðàçíûå îòëè÷èòåëüíûå ïðèçíàêè.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî óòâåðæäåíèÿ 1.Ýòîò òóð âûäåðæèò, ïî êðàéíåé ìåðå, òîò îòëè÷èòåëüíûéïðèçíàê, êîòîðûé áûë íàèìåíüøèì â íà÷àëå òóðà, è çíà÷èò,õîòÿ áû îäèí ïðîöåññ ïåðåéäåò â ñëåäóþùèé òóð.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî óòâåðæäåíèÿ 1.Ýòîò òóð âûäåðæèò, ïî êðàéíåé ìåðå, òîò îòëè÷èòåëüíûéïðèçíàê, êîòîðûé áûë íàèìåíüøèì â íà÷àëå òóðà, è çíà÷èò,õîòÿ áû îäèí ïðîöåññ ïåðåéäåò â ñëåäóþùèé òóð.À ïîñêîëüêó îòëè÷èòåëüíûé ïðèçíàê, êîòîðûé ðàñïîëîæåíâñëåä çà ëîêàëüíûì ìèíèìóìîì, íå áóäåò ëîêàëüíûììèíèìóìîì, ÷èñëî ïðîöåññîâ, ïåðåøåäøèõ â ñëåäóþùèé òóð,íå áóäåò ïðåâîñõîäèòü k/2 .Èç óòâåðæäåíèÿ 1 ñëåäóåò, ÷òî íàñòóïèò è òàêîé òóð (åãî íîìåðíå áóäåò ïðåâîñõîäèòü ≤ blog Nc + 1) , â íà÷àëå êîòîðîãî áóäåòðîâíî îäèí àêòèâíûé ó÷àñòíèê, à èìåííî ñàìûé ìëàäøèéñðåäè îòëè÷èòåëüíûõ ïðèçíàêîâ âñåõ èíèöèàòîðîâ.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÓòâåðæäåíèå 2.Åñëè â íà÷àëå òóðà åñòü òîëüêî îäèí àêòèâíûé ïðîöåññ p ñòåêóùèì îòëè÷èòåëüíûì ïðèçíàêîì cip , òî ïî îêîí÷àíèè ýòîãîòóðà àëãîðèòì çàâåðøèò ñâîþ ðàáîòó, è ïðè ýòîì äëÿ êàæäîãîïðîöåññà q áóäåò âûïîëíåíî ðàâåíñòâî winq = cip .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî óòâåðæäåíèÿ 2.Ñîîáùåíèå hone, cip i, îòïðàâëåííîå ïðîöåññîì p , áóäåòðåòðàíñëèðîâàíî âñåìè ïðîöåññàìè è â êîíöå êîíöîâ áóäåòïîëó÷åíî ñàìèì ïðîöåññîì p .