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

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

Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî òåîðåìû.Äàííûé àëãîðèòì çàâåðøàåò ñâîé âûïîëíåíèå â êàæäîì èçïðîöåññîâ, è ïðè ýòîì âñå ïðîöåññû áóäóò ñîãëàñîâàííîîïîâåùåíû îá îòëè÷èòåëüíîì ïðèçíàêå ëèäåðà (ýòîò ïðèçíàêÿâëÿåòñÿ çíà÷åíèåì ïåðåìåííîé winq ) .Ïðîöåññ ñ óêàçàííûì ïðèçíàêîì áóäåò ïðåáûâàòü â ñîñòîÿíèèleader , à âñå îñòàëüíûå ïðîöåññû â ñîñòîÿíèè lost.Ïîòðåáóåòñÿ ñàìîå áîëüøåå blog Nc + 1 òóðîâ, â êàæäîì èçêîòîðûõ ïðîèñõîäèò îáìåí ðîâíî 2N ñîîáùåíèÿìè; ýòî èñëóæèò îáîñíîâàíèåì îöåíêè ñëîæíîñòè 2N log N + O(N) ïî÷èñëó îáìåíîâ ñîîáùåíèÿìè.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÇàäà÷è.1. Ïðèâåäèòå íà÷àëüíóþ êîíôèãóðàöèþ äëÿ àëãîðèòìàÏåòåðñîíà/ÄîëåâàÊëåéâàÐîäå, ïðè êîòîðîé àëãîðèòìóäåéñòâèòåëüíî ïîòðåáóåòñÿ ïðîâåñòè blog Nc + 1 òóðîâ.2. Ïðèâåäèòå òàêæå íà÷àëüíóþ êîíôèãóðàöèþ, ïðè êîòîðîéýòîìó àëãîðèòìó ïîòðåáóåòñÿ âñåãî äâà òóðà, íåçàâèñèìîîò ÷èñëà èíèöèàòîðîâ.3.

Ìîæåò ëè àëãîðèòì çàâåðøèòü ðàáîòó çà îäèí òóð?Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.6.Åñëè âûïîëíåíû ñëåäóþùèå óñëîâèÿ:Iêîëüöî îäíîíàïðàâëåííîå,Iïðîöåññû íå îñâåäîìëåíû î ðàçìåðàõ êîëüöà,Iâ êàíàëàõ ïîääåðæèâàåòñÿ î÷åðåäíîñòü ñîîáùåíèé,Iâñå ïðîöåññû ÿâëÿþòñÿ èíèöèàòîðàìè,òî ñëîæíîñòü â ñðåäíåì âñÿêîãî àëãîðèòìà èçáðàíèÿ ëèäåðàNPáóäåò íå ìåíüøå, ÷åì N · HN , ãäå HN =1/k .k=1Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.7.Âñÿêèé àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå ñðàâíåíèÿ äëÿïðîèçâîëüíûõ ñåòåé èìååò ñëîæíîñòü (è â ñðåäíåì, è âíàèõóäøåì ñëó÷àå) íå ìåíüøóþ, ÷åì Ω(|E | + N log N) .Äîêàçàòåëüñòâî.ÑàìîñòîÿòåëüíîÑëåäñòâèå.Âñÿêèé äåöåíòðàëèçîâàííûé âîëíîâîé àëãîðèòì äëÿïðîèçâîëüíûõ ñåòåé áåç ïðåäâàðèòåëüíîé îñâåäîìëåííîñòè îñîñåäÿõ èìååò ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè, íåìåíüøóþ ÷åì Ω(|E | + N log N) .Äîêàçàòåëüñòâî.ÑàìîñòîÿòåëüíîÝôôåêò óãàñàíèÿÀëãîðèòì èçáðàíèÿ ëèäåðà ìîæíî ïîëó÷èòü èç ïðîèçâîëüíîãîâîëíîâîãî àëãîðèòìà ïðè ïîìîùè êîíñòðóêöèè, êîòîðàÿ íîñèòíàçâàíèå óãàñàíèå .Êàæäûé èíèöèàòîð çàïóñêàåò îòäåëüíóþ âîëíó.

×òîáûîòëè÷àòüñÿ îò ñîîáùåíèé äðóãèõ âîëí, ñîîáùåíèÿ, äâèæóùèåñÿïî âîëíå, çàïóùåííîé ïðîöåññîì p , äîëæíû áûòü ïîìå÷åíûîòëè÷èòåëüíûì ïðèçíàêîì ïðîöåññà p .Äàííûé àëãîðèòì ãàðàíòèðóåò, ÷òî íåçàâèñèìî îò êîëè÷åñòâàçàïóùåííûõ âîëí òîëüêî îäíà âîëíà ïðèâåäåò ê ðåøåíèþ, àèìåííî, òà âîëíà, êîòîðóþ çàïóñòèë èíèöèàòîð ñ ñàìûììëàäøèì îòëè÷èòåëüíûì ïðèçíàêîì. Âñå îñòàëüíûå âîëíûáóäóò ïðåðâàíû åùå äî òîãî, êàê áóäåò ïðèíÿòî ðåøåíèå.Ýôôåêò óãàñàíèÿÀëãîðèòì èçáðàíèÿ ëèäåðà Ex(A) , ñîîòâåòñòâóþùèéâîëíîâîìó àëãîðèòìó A , óñòðîåí òàê.Âñÿêèé ïðîöåññ â êàæäûé ìîìåíò âðåìåíè àêòèâåí ïîîòíîøåíèþ íå áîëåå ÷åì ê îäíîé âîëíå; ýòà âîëíà íàçûâàåòñÿåãî òåêóùåé àêòèâíîé âîëíîé , îáîçíà÷àåòñÿ caw è èìååòïåðâîíà÷àëüíîå çíà÷åíèå udef .Èíèöèàòîðû âûáîðîâ ïîñòóïàþò òàê, êàê áóäòî êàæäûé èç íèõçàïóñêàåò âîëíó è ïðèäàåò caw ñâîé îòëè÷èòåëüíûé ïðèçíàê âêà÷åñòâå çíà÷åíèÿ.Ýôôåêò óãàñàíèÿÊàê òîëüêî ñîîáùåíèå íåêîòîðîé âîëíû, çàïóùåííîéïðîöåññîì q , äîñòèãàåò ïðîöåññà p , òî p ïðîâîäèò ñëåäóþùèéàíàëèç ýòîãî ñîîáùåíèÿ.IÅñëè q > cawp , òî ñîîáùåíèå ïðîñòî èãíîðèðóåòñÿ, ÷òîíåìåäëåííî ïðèâîäèò ê òîìó, ÷òî âîëíà, çàïóùåííàÿïðîöåññîì q , óãàñàåò.IÅñëè q = cawp , òî óêàçàííîå ñîîáùåíèå îáðàáàòûâàåòñÿòàê, êàê ýòî ïðåäïèñàíî âîëíîâûì àëãîðèòìîì.IÅñëè q < cawp èëè cawp èìååò çíà÷åíèå udef , òî pïðèñîåäèíÿåòñÿ ê âîëíå, çàïóùåííîé ïðîöåññîì q ,óñòàíàâëèâàÿ â ñâîèõ ïåðåìåííûõ ïåðâîíà÷àëüíûåçíà÷åíèÿ, à òàêæå âûïîëíÿÿ ïðèñâàèâàíèå cawp := q .Êîãäà âîëíà, çàïóùåííàÿ ïðîöåññîì q , ïðèâîäèò êîñóùåñòâëåíèþ ñîáûòèÿ ðåøåíèÿ (â áîëüøèíñòâå àëãîðèòìîâðåøåíèå âñåãäà ïðèíèìàåò ñàì ïðîöåññ q ), ïðîöåññ q áóäåòñ÷èòàòüñÿ èçáðàííûì.Ýôôåêò óãàñàíèÿÇàäà÷è.1.

Ðàçðàáîòàéòå àëãîðèòì èçáðàíèÿ ëèäåðà â ïðîèçâîëüíîéñåòè íà îñíîâå ýôôåêòà óãàñàíèÿ, ïðèìåíåííîãî êâîëíîâîìó àëãîðèòìó ýõà. Îöåíèòå ñëîæíîñòü ïî ÷èñëóñîîáùåíèé ïîñòðîåííîãî Âàìè àëãîðèòìà. Îáîñíóéòå åãîêîððåêòíîñòü.2. Ðàçðàáîòàéòå àëãîðèòì èçáðàíèÿ ëèäåðà â êîëüöåâîé ñåòèñåòè íà îñíîâå ýôôåêòà óãàñàíèÿ, ïðèìåíåííîãî êâîëíîâîìó àëãîðèòìó â êîëüöàõ. Ñðàâíèòå ïîñòðîåííûéÂàìè àëãîðèòì ñ àëãîðèòìîì ×åíÿÐîáåðòñà.

 ÷åìñîñòîèò ñõîäñòâî è îòëè÷èå ýòèõ äâóõ àëãîðèòìîâ?ÊÎÍÅÖ ËÅÊÖÈÈ 8..