Лекция 8. Волновые алгоритмы - фазовый_ Финна. Распред. алгоритмы обхода - Тарри_ в глубину_ Авербаха и Сидона (1185658), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

â êîíôèãóðàöèè γ â êàíàëàõ íåò ñîîáùåíèé,Recp [q] = Sentq äëÿ êàæäîãî êàíàëà qp .Êàæäûé èíèöèàòîð îòïðàâèë ñîîáùåíèå.Êàæäûé íå-èíèöèàòîð îòïðàâëÿåò ïåðâîå ñîîáùåíèå âñåìñîñåäÿì ñðàçó ïîñëå ïîëó÷åíèÿ ïåðâîãî ñîîáùåíèÿ.Çíà÷èò, åñëè ñèëüíî ñâÿçíàÿ ñåòü èìååò õîòü îäíîãîèíèöèàòîðà, òî Sentp > 0 äëÿ êàæäîãî óçëà p .Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Äîïóñòèì, ÷òî ó ïðîöåññà p â êîíôèãóðàöèè γ ïåðåìåííàÿ Sentèìååò íàèìåíüøåå çíà÷åíèå, ò.å.

Sentq ≥ Sentp äëÿ âñåõ q . ÷àñòíîñòè, ýòî âåðíî äëÿ âñåõ ïðîöåññîâ q , ÿâëÿþùèõñÿñîñåäÿìè p íà âõîäå.Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Äîïóñòèì, ÷òî ó ïðîöåññà p â êîíôèãóðàöèè γ ïåðåìåííàÿ Sentèìååò íàèìåíüøåå çíà÷åíèå, ò.å. Sentq ≥ Sentp äëÿ âñåõ q . ÷àñòíîñòè, ýòî âåðíî äëÿ âñåõ ïðîöåññîâ q , ÿâëÿþùèõñÿñîñåäÿìè p íà âõîäå.Òîãäà èç ðàâåíñòâà Recp [q] = Sentq ñëåäóåòminq Recp [q] ≥ Sentp .Ôàçîâûé àëãîðèòìp is initiator thenr ∈ Outp do send htoki to r ;Sentp := Sentp + 1 end;while minq Recp [q] < D dobegin receive htoki (from neighbor q0 ) ;Recp [q0 ] := Recp [q0 ] + 1 ;if minq Recp [q] ≥ Sentp and Sentp < D thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1 endend;decidebegin ifbegin forallendÇíà÷èò, Sentp = D , ò.ê.

â ïðîòèâíîì ñëó÷àå p ïðèøëîñü áûîòïðàâëÿòü äîïîëíèòåëüíîå ñîîáùåíèå, êàê òîëüêî îí âïîñëåäíèé ðàç ïîëó÷èë íåêîòîðîå ñîîáùåíèå.Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Äîïóñòèì, ÷òî ó ïðîöåññà p â êîíôèãóðàöèè γ ïåðåìåííàÿ Sentèìååò íàèìåíüøåå çíà÷åíèå, ò.å.

Sentq ≥ Sentp äëÿ âñåõ q . ÷àñòíîñòè, ýòî âåðíî äëÿ âñåõ ïðîöåññîâ q , ÿâëÿþùèõñÿñîñåäÿìè p íà âõîäå.Òîãäà èç ðàâåíñòâà Recp [q] = Sentq ñëåäóåòminq Recp [q] ≥ Sentp .Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Äîïóñòèì, ÷òî ó ïðîöåññà p â êîíôèãóðàöèè γ ïåðåìåííàÿ Sentèìååò íàèìåíüøåå çíà÷åíèå, ò.å. Sentq ≥ Sentp äëÿ âñåõ q . ÷àñòíîñòè, ýòî âåðíî äëÿ âñåõ ïðîöåññîâ q , ÿâëÿþùèõñÿñîñåäÿìè p íà âõîäå.Òîãäà èç ðàâåíñòâà Recp [q] = Sentq ñëåäóåòminq Recp [q] ≥ Sentp .Çíà÷èò, Sentp = D ; â ïðîòèâíîì ñëó÷àå p ïðèøëîñü áûîòïðàâëÿòü äîïîëíèòåëüíîå ñîîáùåíèå, êàê òîëüêî îí âïîñëåäíèé ðàç ïîëó÷èë íåêîòîðîå ñîîáùåíèå.Çíà÷èò, Sentp = D äëÿ âñåõ p , è, ñëåäîâàòåëüíî, äëÿ âñåõêàíàëîâ qp èìååò ìåñòî ðàâåíñòâî Recp [q] = D .Îòñþäà çàêëþ÷àåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî âñÿêîìó ðåøåíèþ ïðåäøåñòâóåò õîòü îäíîñîáûòèå â êàæäîì èç ïðîöåññîâ.Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî âñÿêîìó ðåøåíèþ ïðåäøåñòâóåò õîòü îäíîñîáûòèå â êàæäîì èç ïðîöåññîâ.Ðàññìîòðèì ïóòü â ñåòè P = p0 , p1 , .

. . , p` , ãäå ` ≤ D .(i+1)(i+1)Ïî ëåììå 7.1. fpi pi+1 gpi pi+1 âåðíî äëÿ ëþáîãî i, 0 ≤ i < ` , è,(i+1)(i+2)ñîãëàñíî àëãîðèòìó, gpi pi+1 fpi+1 pi+2 âåðíî äëÿ ëþáîãî(1)(`)i, 0 ≤ i < ` − 1 . Ñëåäîâàòåëüíî, fp0 p1 gp`−1 p` .Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî âñÿêîìó ðåøåíèþ ïðåäøåñòâóåò õîòü îäíîñîáûòèå â êàæäîì èç ïðîöåññîâ.Ðàññìîòðèì ïóòü â ñåòè P = p0 , p1 , . . . , p` , ãäå ` ≤ D .(i+1)(i+1)Ïî ëåììå 7.1. fpi pi+1 gpi pi+1 âåðíî äëÿ ëþáîãî i, 0 ≤ i < ` , è,(i+1)(i+2)ñîãëàñíî àëãîðèòìó, gpi pi+1 fpi+1 pi+2 âåðíî äëÿ ëþáîãî(1)(`)i, 0 ≤ i < ` − 1 .

Ñëåäîâàòåëüíî, fp0 p1 gp`−1 p` .Òàê êàê äèàìåòð ñåòè ðàâåí D , äëÿ êàæäîé ïàðû ïðîöåññîâ q èp ñóùåñòâóåò ïóòü q = p0 , p1 , . . . , p` = p äëèíû íå áîëüøå D .Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî âñÿêîìó ðåøåíèþ ïðåäøåñòâóåò õîòü îäíîñîáûòèå â êàæäîì èç ïðîöåññîâ.Ðàññìîòðèì ïóòü â ñåòè P = p0 , p1 , . . . , p` , ãäå ` ≤ D .(i+1)(i+1)Ïî ëåììå 7.1. fpi pi+1 gpi pi+1 âåðíî äëÿ ëþáîãî i, 0 ≤ i < ` , è,(i+1)(i+2)ñîãëàñíî àëãîðèòìó, gpi pi+1 fpi+1 pi+2 âåðíî äëÿ ëþáîãî(1)(`)i, 0 ≤ i < ` − 1 . Ñëåäîâàòåëüíî, fp0 p1 gp`−1 p` .Òàê êàê äèàìåòð ñåòè ðàâåí D , äëÿ êàæäîé ïàðû ïðîöåññîâ q èp ñóùåñòâóåò ïóòü q = p0 , p1 , . . .

, p` = p äëèíû íå áîëüøå D .Ïîýòîìó äëÿ êàæäîãî q íàéäåòñÿ òàêîå ` ≤ D è òàêîé ñîñåä r(1)(`)íà âõîäå ïðîöåññà p , äëÿ êîòîðûõ fqq0 grp .(`)À â ñèëó óñòðîéñòâà àëãîðèòìà ñîáûòèå grp ïðåäøåñòâóåòñîáûòèþ decidep .Ôàçîâûé àëãîðèòìÑëîæíîñòü ôàçîâîãî àëãîðèòìà. àëãîðèòìå ïî êàæäîìó êàíàëó ïåðåäàåòñÿ D ñîîáùåíèé, èïîýòîìó åãî ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè ðàâíà|E |D .Íóæíî èìåòü â âèäó, îäíàêî, ÷òî çäåñü |E | îáîçíà÷àåòêîëè÷åñòâî greenîäíîñòîðîííèõ êàíàëîâ. Åñëè ôàçîâûéàëãîðèòì èñïîëüçóåòñÿ äëÿ íåîðèåíòèðîâàííîé ñåòè, òî êàæäûéåå êàíàë ñëåäóåò ðàññìàòðèâàòü êàê äâà îäíîñòîðîííèõ êàíàëà,è ïîýòîìó ñëîæíîñòü ïî ÷èñëó ñîîáùåíèé áóäåò ðàâíà 2|E |D .Ôàçîâûé àëãîðèòìÇàäà÷è.1.

Ïîêàæèòå, ÷òî âçàèìîñâÿçü, êîòîðàÿ ïðîÿâëÿåòñÿ âëåììå 7.1., ñîõðàíÿåòñÿ è â òîì ñëó÷àå, êîãäà ñîîáùåíèÿìîãóò óòåðÿíû â êàíàëå pq , íî íå ñîõðàíÿåòñÿ, êîãäàñîîáùåíèÿ ìîãóò äóáëèðîâàòüñÿ. Êàêîé èç ýòàïîâäîêàçàòåëüñòâà óòðàòèò ñèëó, åñëè ñîîáùåíèÿ ìîãóòäóáëèðîâàòüñÿ?2.

Ïðåîáðàçóéòå ôàçîâûé àëãîðèòì äëÿ âû÷èñëåíèÿìàêñèìóìà íà ìíîæåñòâå öåëî÷èñëåííûõ âõîäíûõ äàííûõâñåõ ïðîöåññîâ.Êàêîâà ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìèïîñòðîåííîãî àëãîðèòìà?Ìîæíî ëè ïðè ïîìîùè ôàçîâîãî àëãîðèòìà âû÷èñëÿòüñóììû âõîäíûõ äàííûõ âñåõ ïðîöåññîâ?Àëãîðèòì ÔèííàÀëãîðèòì Ôèííà ýòî åùå îäèí âîëíîâîéàëãîðèòì, êîòîðûé ìîæíî èñïîëüçîâàòü äëÿïðîèçâîëüíûõ îðèåíòèðîâàííûõ ñåòåé.Çäåñü íå òðåáóåòñÿ, ÷òîáû äèàìåòð ñåòè áûëèçâåñòåí çàðàíåå, íî çàòî ýòîò àëãîðèòì îïèðàåòñÿíà îäíîçíà÷íóþ èäåíòèôèöèðóåìîñòü ïðîöåññîâ. ñîîáùåíèÿõ ïðîöåññû îáìåíèâàþòñÿîòëè÷èòåëüíûìè ïðèçíàêàìè, è ýòî ïðèâîäèò êòîìó, ÷òî áèòîâàÿ ñëîæíîñòü àëãîðèòìàñòàíîâèòñÿ äîñòàòî÷íî áîëüøîé.Àëãîðèòì ÔèííàÎñíîâíàÿ èäåÿ.Ïðîöåññ p ôîðìèðóåò äâà ìíîæåñòâà îòëè÷èòåëüíûõ ïðèçíàêîâIncp è NIncp .IIncp ýòî ìíîæåñòâî òàêèõ ïðîöåññîâ q , ÷òî íåêîòîðîåñîáûòèå â q ïðåäøåñòâóåò (ïî îòíîøåíèþ ) ñàìîìóïîñëåäíåìó ñîáûòèþ, ñëó÷èâøåìóñÿ â p ,INIncp ìíîæåñòâî òàêèõ ïðîöåññîâ q , ÷òî ó êàæäîãîñîñåäà r ïðîöåññà q êàêîå-íèáóäü ñîáûòèå â r ïðåäøåñòâóåòñàìîìó ïîñëåäíåìó ñîáûòèþ, ñëó÷èâøåìóñÿ â p .Àëãîðèòì ÔèííàÎñíîâíàÿ èäåÿ.Ìíîæåñòâà Incp è NIncp ôîðìèðóþòñÿ òàê.1) Âíà÷àëå Incp = {p} è NIncp = ∅ .Àëãîðèòì ÔèííàÎñíîâíàÿ èäåÿ.Ìíîæåñòâà Incp è NIncp ôîðìèðóþòñÿ òàê.1) Âíà÷àëå Incp = {p} è NIncp = ∅ .2) Ïðîöåññ p îòïðàâëÿåò ñîîáùåíèÿ, ñîäåðæàùèå Incp è NIncp ,âñÿêèé ðàç, êîãäà îäíî èç ýòèõ ìíîæåñòâ ðàñøèðÿåòñÿ.Àëãîðèòì ÔèííàÎñíîâíàÿ èäåÿ.Ìíîæåñòâà Incp è NIncp ôîðìèðóþòñÿ òàê.1) Âíà÷àëå Incp = {p} è NIncp = ∅ .2) Ïðîöåññ p îòïðàâëÿåò ñîîáùåíèÿ, ñîäåðæàùèå Incp è NIncp ,âñÿêèé ðàç, êîãäà îäíî èç ýòèõ ìíîæåñòâ ðàñøèðÿåòñÿ.3) Êîãäà p ïîëó÷àåò ñîîáùåíèå c ìíîæåñòâàìè Inc è NInc ,ïîëó÷åííûå îòëè÷èòåëüíûå ïðèçíàêè äîáàâëÿþòñÿ êìíîæåñòâàìIncp è NIncp .Àëãîðèòì ÔèííàÎñíîâíàÿ èäåÿ.Ìíîæåñòâà Incp è NIncp ôîðìèðóþòñÿ òàê.1) Âíà÷àëå Incp = {p} è NIncp = ∅ .2) Ïðîöåññ p îòïðàâëÿåò ñîîáùåíèÿ, ñîäåðæàùèå Incp è NIncp ,âñÿêèé ðàç, êîãäà îäíî èç ýòèõ ìíîæåñòâ ðàñøèðÿåòñÿ.3) Êîãäà p ïîëó÷àåò ñîîáùåíèå c ìíîæåñòâàìè Inc è NInc ,ïîëó÷åííûå îòëè÷èòåëüíûå ïðèçíàêè äîáàâëÿþòñÿ êìíîæåñòâàìIncp è NIncp .4) Åñëè p ïîëó÷èë ñîîáùåíèÿ îò âñåõ ñâîèõ ñîñåäåé íà âõîäå,òî îòëè÷èòåëüíûé ïðèçíàê p âñòàâëÿåòñÿ â NIncp .Àëãîðèòì ÔèííàÎñíîâíàÿ èäåÿ.Ìíîæåñòâà Incp è NIncp ôîðìèðóþòñÿ òàê.1) Âíà÷àëå Incp = {p} è NIncp = ∅ .2) Ïðîöåññ p îòïðàâëÿåò ñîîáùåíèÿ, ñîäåðæàùèå Incp è NIncp ,âñÿêèé ðàç, êîãäà îäíî èç ýòèõ ìíîæåñòâ ðàñøèðÿåòñÿ.3) Êîãäà p ïîëó÷àåò ñîîáùåíèå c ìíîæåñòâàìè Inc è NInc ,ïîëó÷åííûå îòëè÷èòåëüíûå ïðèçíàêè äîáàâëÿþòñÿ êìíîæåñòâàìIncp è NIncp .4) Åñëè p ïîëó÷èë ñîîáùåíèÿ îò âñåõ ñâîèõ ñîñåäåé íà âõîäå,òî îòëè÷èòåëüíûé ïðèçíàê p âñòàâëÿåòñÿ â NIncp .5) Åñëè Incp = NIncp , òî p ïðèíèìàåò ðåøåíèå.Ýòî îçíà÷àåò, ÷òî êàêîâ áû íè áûë ïðîöåññ q , åñëè íåêîòîðîåñîáûòèå â q ïðåäøåñòâóåò dp , òî ó âñÿêîãî ñîñåäà r ïðîöåññà qòàêæå ïðîèçîøëî êàêîå-íèáóäü ñîáûòèå, ïðåäøåñòâóþùåå dp .Îòñþäà ñëåäóåò, ÷òî äëÿ íàøåãî àëãîðèòìà òðåáîâàíèåçàâèñèìîñòè ñîáëþäåíî.Àëãîðèòì Ôèííàvar: ìíâî ïðîöåññîâinit {p} ;: ìíâî ïðîöåññîâinit ∅ ;: bool for q ∈ Inpinit false ;(* èíäèêàòîðû ïîëó÷åíèÿ ïðîöåññîì p ñîîáùåíèÿ îò q *)if p is initiator thenforall r ∈ Outp do send hsets, Incp , NIncp i to r ;while Incp 6= NIncp dobegin receive hsets, Inc, NInci from q0 ;Incp := Incp ∪ Inc ; NIncp := NIncp ∪ NInc ;recp [q0 ] := true ;if ∀q ∈ Inp : recp [q] then NIncp := NIncp ∪ {p} ;if Incp or NIncp has changed thenforall r ∈ Outp do send hsets, Incp , NIncp i to rend;decideIncpNIncprecp [q]beginendÔàçîâûé àëãîðèòìp2Inc2 = (2)NInc = ∅2@@@@@ Inc4 = (4)R@p4p1 NInc = ∅4@Inc1 = (1) @@NInc1 = ∅@@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2Inc2 = (2)NInc = ∅2@@@h(1), ∅i@@ Inc4 = (4)R@p4p1 NInc = ∅4@Inc1 = (1) @@NInc1 = ∅@ h(1), ∅i@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2)NInc = ∅2@@@@@ Inc4 = (4)R@p4p1 NInc = ∅4@Inc1 = (1) @@NInc1 = ∅@ h(1), ∅i@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2p1 Inc2 = (1, 2)NInc = (2)2@@@@h(1, 2), (2)i@ Inc4 = (4)R@p4NInc = ∅4@Inc1 = (1) @@NInc1 = ∅@ h(1), ∅i@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2)NInc = (2)2@@@@p1 @ Inc4 = (1, 2, 4)Rh(1, 2, 4), (2)i @p4NInc = (1)4@Inc1 = (1) @@NInc1 = ∅@h(1), ∅i@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2)NInc = (2)2@@@@@ Inc4 = (1, 2, 4)R@p4p1 NInc = (1)4@Inc1 = (1, 2, 4)@@NInc1 = (2)@h(1), ∅i@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2)NInc = (2)2@@@h(1, 2, 4), (1, 2)i @@ Inc4 = (1, 2, 4)R@p4p1 NInc = (1)4@Inc1 = (1, 2, 4)@ h(1, 2, 4), (1, 2)i@NInc1 = (1, 2)@h(1), ∅i@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2p1 Inc2 = (1, 2, 4)NInc = (1, 2)2@@@@h(1, 2, 4), (1, 2)i@ Inc4 = (1, 2, 4)R@p4NInc = (1)4@Inc1 = (1, 2, 4)@ h(1, 2, 4), (1, 2)i@NInc1 = (1, 2)@h(1), ∅i@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2, 4)NInc = (1, 2)2@@@@p1 @ Inc4 = (1, 2, 4)Rh(1, 2, 4), (1, 2)i @p4NInc = (1, 2)4@Inc1 = (1, 2, 4)@ h(1, 2, 4), (1, 2)i@h(1), ∅iNInc1 = (1, 2)@@ Inc3 = (3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2, 4)NInc = (1, 2)2@@@@@ Inc4 = (1, 2, 4)R@p4p1 NInc = (1, 2)4@Inc1 = (1, 2, 4)@ h(1, 2, 4), (1, 2)i@NInc1 = (1, 2)@@ Inc3 = (1, 3)R@p3NInc = ∅3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2, 4)NInc = (1, 2)2@@@@@ Inc4 = (1, 2, 4)R@p4p1 NInc = (1, 2)4@Inc1 = (1, 2, 4)@ h(1, 2, 4), (1, 2)i@h(1, 3), (3)iNInc1 = (1, 2)@@ Inc3 = (1, 3)R@p3NInc = (3)3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2, 4)NInc = (1, 2)2@@@@@ Inc4 = (1, 2, 3, 4)R@p4p1 NInc = (1, 2, 3)4@Inc1 = (1, 2, 4)@h(1, 2, 4), (1, 2)i@NInc1 = (1, 2)@@ Inc3 = (1, 3)R@p3NInc = (3)3Ôàçîâûé àëãîðèòìp2Inc2 = (1, 2, 4)NInc = (1, 2)2@@@@decide@ Inc4 = (1, 2, 3, 4)R@h(1, 2, 3, 4), (1, 2, 3, 4)ip1 p4NInc = (1, 2, 3, 4)4@Inc1 = (1, 2, 4)@h(1, 2, 4), (1, 2)i@NInc1 = (1, 2)@@ Inc3 = (1, 3)R@p3NInc = (3) 3Àëãîðèòì ÔèííàÒåîðåìà îá àëãîðèòìå ÔèííàÀëãîðèòì Ôèííà ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ìíîæåñòâà Incp è NIncp ìîãóò òîëüêî óâåëè÷èâàòüñÿ.

Èõñóììàðíûé ðàçìåð âàðüèðóåòñÿ îò 1 â ïåðâîì ñîîáùåíèè äî íåáîëåå ÷åì 2N â ïîñëåäíåì ñîîáùåíèè. Çíà÷èò, îáùååêîëè÷åñòâî ñîîáùåíèé îãðàíè÷åíî âåëè÷èíîé 2N|E | . Ïîýòîìóâûïîëíåíèÿ àëãîðèòì çàâåðøàþòñÿ.Àëãîðèòì ÔèííàÒåîðåìà îá àëãîðèòìå ÔèííàÀëãîðèòì Ôèííà ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ìíîæåñòâà Incp è NIncp ìîãóò òîëüêî óâåëè÷èâàòüñÿ. Èõñóììàðíûé ðàçìåð âàðüèðóåòñÿ îò 1 â ïåðâîì ñîîáùåíèè äî íåáîëåå ÷åì 2N â ïîñëåäíåì ñîîáùåíèè. Çíà÷èò, îáùååêîëè÷åñòâî ñîîáùåíèé îãðàíè÷åíî âåëè÷èíîé 2N|E | . Ïîýòîìóâûïîëíåíèÿ àëãîðèòì çàâåðøàþòñÿ.Ðàññìîòðèì çàêëþ÷èòåëüíóþ êîíôèãóðàöèþ γ âû÷èñëåíèÿ C .Êàê è â äîêàçàòåëüñòâå ïðåäûäóùåé òåîðåìû, ìîæíî ïîêàçàòü,÷òî åñëè ïðîöåññ p ñóìåë îòïðàâèòü õîòÿ áû îäíî ñîîáùåíèå(êàæäîìó ñîñåäó), è q ñîñåä ïðîöåññà p íà âûõîäå, òî qòàêæå ñóìåë îòïðàâèòü õîòü îäíî ñîîáùåíèå.Îòñþäà ñëåäóåò, ÷òî êàæäûé ïðîöåññ ñóìåë îòïðàâèòü õîòÿ áûîäíî ñîîáùåíèå (ïî êàæäîìó êàíàëó).Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî â γ êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî â γ êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.1) Äëÿ êàæäîãî ðåáðà pq â êîíôèãóðàöèè γ âûïîëíÿåòñÿIncp ⊆ Incq , ò.ê., ñîâåðøèâ ïîñëåäíåå èçìåíåíèå ìíîæåñòâàIncp , ïðîöåññ p îòïðàâèë ñîîáùåíèå hsets, Incp , NIncp i .Êàê òîëüêî îíî áûëî ïîëó÷åíî, q âûïîëíèë îïåðàòîðIncq := Incq ∪ Incp .Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî â γ êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.1) Äëÿ êàæäîãî ðåáðà pq â êîíôèãóðàöèè γ âûïîëíÿåòñÿIncp ⊆ Incq , ò.ê., ñîâåðøèâ ïîñëåäíåå èçìåíåíèå ìíîæåñòâàIncp , ïðîöåññ p îòïðàâèë ñîîáùåíèå hsets, Incp , NIncp i .Êàê òîëüêî îíî áûëî ïîëó÷åíî, q âûïîëíèë îïåðàòîðIncq := Incq ∪ Incp .Ñèëüíàÿ ñâÿçíîñòü ñåòè ïðèâîäèò ê òîìó, ÷òî Incp = Incq äëÿâñåõ p è q .

Характеристики

Список файлов лекций