7 Волновые алгоритмы - определение, основные свойства, область применения. Древесный алгоритм. Алгоритм эха, страница 2

ðàâíî 2(N-1) .ÏóñòüF ýòî ÷èñëî áèòîâ rec ñî çíà÷åíèåì false â êîíôèãóðàöèè γ ,K êîëè÷åñòâî ïðîöåññîâ, êîòîðûå óæå îòïðàâèëè ñîîáùåíèÿâ êîíôèãóðàöèè γ . Ïðèåì êàæäîãî îòïðàâëåííîãî ñîîáùåíèÿîáðàùàåò îäèí èç áèòîâ ìàññèâà rec â true .Òàêèì îáðàçîì, îáùåå ÷èñëî áèòîâ rec ðàâíî 2N − 2 , è K èçíèõ ìîãóò èìåòü çíà÷åíèå true .  çàêëþ÷èòåëüíîéêîíôèãóðàöèè γ íèêàêèõ ñîîáùåíèé íå ïåðåñûëàåòñÿ, èïîýòîìó F = (2N − 2) − K .Äðåâåñíûé àëãîðèòìÄîêàçàòåëüñòâî.3) Äîïóñòèì, ÷òî íè îäèí èç ïðîöåññîâ íå ïðèíÿë ðåøåíèÿ â γ .Òîãäà N − K ïðîöåññîâ, êîòîðûå â γ åùå íå îòïðàâëÿëèñîîáùåíèÿ, èìåþò â rec ïî ìåíüøåé ìåðå äâà áèòà ñîçíà÷åíèåì false .

Èíà÷å îíè ìîãëè áû îòïðàâèòü ñîîáùåíèå,õîòÿ γ çàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ.Êðîìå òîãî, K ïðîöåññîâ, êîòîðûå â γ óæå îòïðàâèëèñîîáùåíèå, èìåþò â rec õîòÿ áû ïî îäíîìó áèòó ñî çíà÷åíèåìfalse . Èíà÷å îíè ìîãëè áû ïðèíÿòü ðåøåíèå âîïðåêèñäåëàííîìó ïðåäïîëîæåíèþ î γ .Çíà÷èò, F ≥ 2(N − K ) + K .Ðàíåå ìû ïîêàçàëè, ÷òî F = (2N − 2) − K .Ïîýòîìó (2N − 2) − K ≥ 2(N − K ) + K .Îòñþäà ñëåäóåò −2 ≥ 0 .Ïîëó÷åííîå ïðîòèâîðå÷èå îçíà÷àåò, ÷òî õîòÿ áû îäíî ðåøåíèåâ γ óæå ïðèíÿòî.Äðåâåñíûé àëãîðèòìÄîêàçàòåëüñòâî.4) Ïîêàæåì, ÷òî ðåøåíèþ ïðåäøåñòâóåò êàêîå-ëèáî ñîáûòèå âêàæäîì èç ïðîöåññîâ.Ïîêàæåì èíäóêöèåé ïî ÷èñëó ñîáûòèé ïðèåìà, ÷òî∀ s ∈ Tpq ∃e ∈ Cs : e gpq .Äîïóñòèì, ýòî âåðíî äëÿ âñåõ ñîáûòèé ïðèåìà,ïðåäøåñòâóþùèõ ñîáûòèþ gpq . Òîãäà ñîáûòèþ gpqïðåäøåñòâóåò ñîáûòèå fpq (â ïðîöåññå p ). Ïîýòîìó èçóñòðîéñòâà ïðîãðàììû p ñëåäóåò, ÷òî äëÿ âñåõ r ∈ Neighp ïðèr 6= q ñîáûòèþ fpq ïðåäøåñòâóåò ñîáûòèå grp .Èç èíäóêòèâíîé ãèïîòåçû âûòåêàåò, ÷òî äëÿ âñåõ òàêèõ r è äëÿâñåõ s ∈ Trp íàéäåòñÿ òàêîå ñîáûòèå e ∈ Cs , ÷òî e grp .Çíà÷èò, e gpq .Äðåâåñíûé àëãîðèòìÄîêàçàòåëüñòâî.5) Ðåøåíèþ decidep â óçëå p ïðåäøåñòâóåò ñîáûòèå grp äëÿ âñåõr ∈ Neighp .Îòñþäà ñëåäóåò, ÷òî∀ s ∈ P ∃e ∈ Cs : e dp .Àëãîðèòì ýõàÀëãîðèòì ýõà ýòî öåíòðàëèçîâàííûé âîëíîâîé àëãîðèòì äëÿñåòåé ñ ïðîèçâîëüíîé òîïîëîãèåé.Àëãîðèòì íàâîäíÿåò ñîîáùåíèÿìè tok âñå ïðîöåññû, âûäåëÿÿòàêèì îáðàçîì îñòîâíîå äåðåâî.

Ìàðêåðû âîçâðàùàþòñÿ¾ýõîì¿ îáðàòíî ïî ðåáðàì ýòîãî äåðåâà, íàïîìèíàÿ ïîòîêñîîáùåíèé â äðåâåñíîì àëãîðèòìå. Ñöåíàðèé ðàáîòû òàêîâ.1) Èíèöèàòîð îòïðàâëÿåò ñîîáùåíèå âñåì ñâîèì ñîñåäÿì.2) Ïîñëå ïîëó÷åíèÿ ïåðâîãî ñîîáùåíèÿ âñÿêèé íåèíèöèàòîðïåðåïðàâëÿåò ñîîáùåíèÿ âñåì ñâîèì ñîñåäÿì, çà èñêëþ÷åíèåìòîãî, îò êîòîðîãî áûëî ïîëó÷åíî ýòî ñîîáùåíèå.3) Êàê òîëüêî íåèíèöèàòîð ïîëó÷èò ñîîáùåíèÿ îò âñåõ ñâîèõñîñåäåé, îí îòïðàâëÿåò ýõî ðîäèòåëüñêîìó ïðîöåññó.4) Êàê òîëüêî èíèöèàòîð ïîëó÷èò ñîîáùåíèÿ îò âñåõ ñâîèõñîñåäåé, îí ïðèíèìàåò ðåøåíèå.Àëãîðèòì ýõàvarrecp: integerfatherp : PÄëÿ èíèöèàòîðà:begin forallwhiledecideinitinit0; (*Ïîäñ÷åò ÷èñëà ïðèíÿòûõ ñîîáùåíèé*)undef ;q ∈ Neighp do send tok to q ;recp < #Neighp dobegin receive tok ; recp := recp + 1end;endÄëÿ íåèíèöèàòîðà:begin receive tok from neighbor q ; fatherp := q ; recp := recp + 1 ;forall q ∈ Neighp , q 6= fatherp do send tok to q ;while recp < #Neighp dobegin receive tok ; recp := recp + 1 end;send tok to fatherpendÀëãîðèòì ýõàÈíèöèàòîð00HHHHHHHH0@@@@@ @@@@@ 00000Àëãîðèòì ýõàÈíèöèàòîð~HHH00HHHHH0@@@@@ @@@@@ 00000Àëãîðèòì ýõàÈíèöèàòîð~HHH0toc0HHHtocHH0@@@@@ @@@@@ 00000Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHtocHHtoc0~1@@@@@@toc@ toc@toc@@ 0 00000Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHtoc HHHHHHtocHHHH~ 1~1@@@@@@toc@ toctoc@ toctoc@@ 0 00000Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHtocHH~~ 11@@@@@@toc@ toctoc@ toctoc@@ 1 00000Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH1~~ 2@@@@@@toctoc@ toctoc@ toc@@ 1 00000Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH1~~ 2@@@@@@ toc@@@toctoc@ toctoc@@@@@ ~ 100001Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH1~~ 3@@@@@@@@@toctoc@ toctoc@@@@@ ~ 100001Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH1~~ 3@@@@@@@@@@@@toctoc@@toc@@@@@ @~~ toc 100101Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH1~~ 3@@@@@@@@@@@@@@toctoc@@@@@ @~ toc~~ toc 100111Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH1~~ 3@@@@@@toc@@@@@@@@toctoc@@@@@ @~ toc~~ 100121Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH1~~ 3@@@@@@ toctoc@@@@@@@@toctoc@@@@@ @~~~ 100221Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHHtoc1~~ 4@@@@@@ toc@@@@@@@@@toctoc@@@@ @~~~ 100221Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH2~~ 4@@@@@@ toc@@@@@@@@@toctoc@@@@ @~~~ 100221Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH3~~ 4@@@@@@@@@@@@@@@toctoc@@@@ @~~~ 100221Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH3~~ 4@@@@@@@@@@@@@@@toc@@@@@~ toc~~~ 110221Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH3~~ 4@@@@@@@@toc@@@@@@@toc@@@@ @~~~~~ 111221Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH3~~ 4@@@@@@@@toc@@@@@@@@@@@ @~toc~~~~ 112221Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH3~~ 4@@@@toc@@@@toc@@@@@@@@@@@ @~~~~~ 122221Àëãîðèòì ýõàÈíèöèàòîð~HHHHHHHH~4~ 4@@@@@@@@toc@@@@@@@@@@@ @~~~~~ 122221Àëãîðèòì ýõàÈíèöèàòîð~toc HHHHHHHH~5~ 4@@@@@@@@@@@@@@@@@@@ @~~~~~ 122221Àëãîðèòì ýõàÈíèöèàòîð~DECIDE!HHHHHHHH~5~ 4@@@@@@@@@@@@@@@@@@@ @~~~~~ 222221Àëãîðèòì ýõàÓòâåðæäåíèå 14.Àëãîðèòì ýõà ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì.ÄîêàçàòåëüñòâîÇàäà÷à äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ.Çàäà÷è íà äîìÇàäà÷à 7.Ïðèâåäèòå ïðèìåð PIF-àëãîðèòìà äëÿ ñèñòåì ñ ñèíõðîííûìîáìåíîì ñîîáùåíèÿìè, êîòîðûé íå ïîçâîëÿåò ïðîâîäèòüâû÷èñëåíèå òî÷íûõ íèæíèõ ãðàíåéÇàäà÷à 8.Ïîêàæèòå, ÷òî â êàæäîì âû÷èñëåíèè äðåâåñíîãî àëãîðèòìà âòî÷íîñòè äâà ïðîöåññà ïðèíèìàþò ðåøåíèå.ÊÎÍÅÖ ËÅÊÖÈÈ 7..