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

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 7.Âîëíîâûå àëãîðèòìû.Ôàçîâûé àëãîðèòì.Àëãîðèòì Ôèííà.Ðàñïðåäåëåííûå àëãîðèòìû îáõîäà:îñíîâíûå ñâîéñòâà.Àëãîðèòì îáõîäà Òàððè.Ðàñïðåäåëåííûé îáõîä â ãëóáèíó.Àëãîðèòìû Àâåðáàõà è Ñèäîíà.Âîëíîâûå àëãîðèòìûÎïðåäåëåíèå.Âîëíîâûì àëãîðèòìîì íàçûâàåòñÿ ðàñïðåäåëåííûé àëãîðèòì,êîòîðûé óäîâëåòâîðÿåò ñëåäóþùèì òðåì òðåáîâàíèÿì.1.Çàâåðøåíèå.Êàæäîå âû÷èñëåíèå êîíå÷íî:∀C : |C | < ∞.2.Êàæäîå âû÷èñëåíèå ñîäåðæèò õîòÿ áû îäíîñîáûòèå ðåøåíèÿ:Ðåøåíèå.∀C : ∃e ∈ C : e ÿâëÿåòñÿ ñîáûòèåì ðåøåíèÿ decide.3. ëþáîì âû÷èñëåíèè âñÿêîìó ñîáûòèþðåøåíèÿ ïðåäøåñòâóåò â ïðè÷èííî-ñëåäñòâåííîìîòíîøåíèè õîòÿ áû îäíî ñîáûòèå â êàæäîì èç ïðîöåññîâ:Çàâèñèìîñòü.Âîëíîâûå àëãîðèòìûÂîëíîâûå àëãîðèòìû ïðèãîäíû äëÿ ðåøåíèÿ ñëåäóþùèõ çàäà÷:1.Øèðîêîâåùàòåëüíîå ðàñïðîñòðàíåíèå èíôîðìàöèè ñïîäòâåðæäåíèåì.2.Ñèíõðîíèçàöèè ïðîöåññîâ ñèñòåìû.3.Âû÷èñëåíèÿ ãëîáàëüíîé ôóíêöèè òî÷íîé íèæíåéãðàíè.4.

è ìíîãèõ äðóãèõ (èçáðàíèÿ ëèäåðà, îáíàðóæåíèÿçàâåðøåíèÿ è äð.)Âîëíîâûå àëãîðèòìûÎñíîâíûå âîëíîâûå àëãîðèòìû:1.Âîëíîâûå àëãîðèòìû â êîëüöàõ.2.Äðåâåñíûé âîëíîâîé àëãîðèòì.3.Àëãîðèòì ýõà.Âîëíîâûå àëãîðèòìûÎñíîâíûå âîëíîâûå àëãîðèòìû:1.Âîëíîâûå àëãîðèòìû â êîëüöàõ.2.Äðåâåñíûé âîëíîâîé àëãîðèòì.3.Àëãîðèòì ýõà.Íî ýòè àëãîðèòìû ðàáîòàþò òîëüêî â ñåòÿõ ñ äâóñòîðîííèìèêàíàëàìè ñâÿçè (íåîðèåíòèðîâàííûìè ãðàôàìè).Ðàññìîòðèì åùå íåñêîëüêî áîëåå îáùèõ àëãîðèòìîâ: ôàçîâûéàëãîðèòì è àëãîðèòì Ôèííà.Ôàçîâûé àëãîðèòìÔàçîâûé àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì àëãîðèòìîì,ïðèãîäíûì äëÿ ñåòåé ñ ïðîèçâîëüíîé òîïîëîãèåé.

Åãî ìîæíîèñïîëüçîâàòü â êà÷åñòâå âîëíîâîãî àëãîðèòìà äëÿîðèåíòèðîâàííûõ ñåòåé.Ôàçîâûé àëãîðèòìÔàçîâûé àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì àëãîðèòìîì,ïðèãîäíûì äëÿ ñåòåé ñ ïðîèçâîëüíîé òîïîëîãèåé. Åãî ìîæíîèñïîëüçîâàòü â êà÷åñòâå âîëíîâîãî àëãîðèòìà äëÿîðèåíòèðîâàííûõ ñåòåé. ýòîì àëãîðèòìå òðåáóåòñÿ, ÷òîáû âñå ïðîöåññû ðàñïîëàãàëèñâåäåíèÿìè î äèàìåòðå ñåòè D . Àëãîðèòì áóäåò îñòàâàòüñÿêîððåêòíûì (õîòÿ è ìåíåå ýôôåêòèâíûì), åñëè âñå ïðîöåññûáóäóò èñïîëüçîâàòü âìåñòî D êîíñòàíòó D 0 , ïðåâûøàþùóþäèàìåòð ñåòè.Ôàçîâûé àëãîðèòìÔàçîâûé àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì àëãîðèòìîì,ïðèãîäíûì äëÿ ñåòåé ñ ïðîèçâîëüíîé òîïîëîãèåé.

Åãî ìîæíîèñïîëüçîâàòü â êà÷åñòâå âîëíîâîãî àëãîðèòìà äëÿîðèåíòèðîâàííûõ ñåòåé. ýòîì àëãîðèòìå òðåáóåòñÿ, ÷òîáû âñå ïðîöåññû ðàñïîëàãàëèñâåäåíèÿìè î äèàìåòðå ñåòè D . Àëãîðèòì áóäåò îñòàâàòüñÿêîððåêòíûì (õîòÿ è ìåíåå ýôôåêòèâíûì), åñëè âñå ïðîöåññûáóäóò èñïîëüçîâàòü âìåñòî D êîíñòàíòó D 0 , ïðåâûøàþùóþäèàìåòð ñåòè.Ôàçîâûé àëãîðèòì ìîæíî ïðèìåíÿòü äëÿ âñÿêîéîðèåíòèðîâàííîé ñåòè, ïî êàíàëàì êîòîðîé îñóùåñòâëÿåòñÿîäíîñòîðîííÿÿ ïåðåäà÷à ñîîáùåíèé.  ýòîì ñëó÷àå ñîñåäÿìèâåðøèíû p áóäóò ñîñåäè íà âõîäå (ïðîöåññû, êîòîðûå ìîãóòîòïðàâëÿòü ñîîáùåíèÿ ïðîöåññó p ) è ñîñåäè íà âûõîäå(ïðîöåññû, êîòîðûì p ìîæåò îòïðàâëÿòü ñîîáùåíèÿ).

Ñîñåäè píà âõîäå îáðàçóþò ìíîæåñòâî Inp , à ñîñåäè íà âûõîäå ìíîæåñòâî Outp .Ôàçîâûé àëãîðèòìÎñíîâíàÿ èäåÿ. ôàçîâîì àëãîðèòìå âñÿêèé ïðîöåññ îòïðàâëÿåòâ òî÷íîñòè D ñîîáùåíèé êàæäîìó ñîñåäó íàâûõîäå.Ïðè ýòîì (i + 1) -å ñîîáùåíèå îòïðàâëÿåòñÿêàæäîìó ñîñåäó íà âûõîäå òîëüêî ïîñëå òîãî, êàêáûëè ïîëó÷åíû i ñîîáùåíèé îò êàæäîãî ñîñåäà íàâõîäå.Êàê òîëüêî îò êàæäîãî ñîñåäà áóäåò ïîëó÷åíî âòî÷íîñòè D ñîîáùåíèé, ïðîöåññ çàâåðøàåòàëãîðèòì è ïðèíèìàåò ðåøåíèå.Ôàçîâûé àëãîðèòìD: integer= äèàìåòð ñåòè ;var Recp [q]: 0..Dinit 0 äëÿ êàæäîãî q ∈ Inp ;(* ×èñëî ñîîáùåíèé, ïîëó÷åííûõ îò q *)Sentp: 0..Dinit 0 ;(* ×èñëî ñîîáùåíèé, îòïðàâëåííûõ êàæäîìó ñîñåäó íà âûõîäå *begin if p is initiator thenbegin forall r ∈ 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;decideconsendÔàçîâûé àëãîðèòìD=3p2Rec2 = (0)Sent = 02@@@@@ Rec4 = (0, 0)R@p1 p4Sent = 04@Rec1 = (0) @@Sent1 = 0@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (0)Sent = 02@@@tok@@ Rec4 = (0, 0)R@p1 p4Sent = 04@Rec1 = (0) @ tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (1)Sent = 02@@@@@ Rec4 = (0, 0)R@p1 p4Sent = 04@Rec1 = (0) @ tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (1)Sent = 12@@@tok@@ Rec4 = (0, 0)R@p1 p4Sent = 04@Rec1 = (0) @ tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (1)Sent = 12@@@@@ Rec4 = (1, 0)R@p1 p4Sent = 04@Rec1 = (0) @ tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (1)Sent = 12@@@@tokp1 @ Rec4 = (1, 0)R@p4Sent = 14@Rec1 = (0) @ tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2tokRec2 = (1)Sent = 12@@@@@ Rec4 = (1, 0)R@p1 p4Sent = 14@Rec1 = (1) @ tok@Sent1 = 2@ tok@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@tok @@ Rec4 = (1, 0)R@p1 p4Sent = 14@Rec1 = (1) @ tok@Sent1 = 2@ tok@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@@ Rec4 = (2, 0)R@p1 p4Sent = 14@Rec1 = (1) @ tok@Sent1 = 2@ tok@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@@ Rec4 = (2, 0)R@p1 p4Sent = 14@Rec1 = (1) @ tok@tokSent1 = 2@@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@p1 @ Rec4 = (2, 1)R@tokp4Sent = 24@Rec1 = (1) @tok@Sent1 = 2@@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìD=3p2tokRec2 = (2)Sent = 22@@@@@ Rec4 = (2, 1)R@p1 p4Sent = 24@Rec1 = (2) @tok@Sent1 = 3@ tok@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìdecideD=3p2Rec2 = (3)Sent = 32@@@tok@@ Rec4 = (2, 1)R@p1 p4Sent = 24@Rec1 = (2) @tok@Sent1 = 3@ tok@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìÏî êàæäîìó êàíàëó ïåðåäàåòñÿ íå áîëåå D ñîîáùåíèé.Äëÿ êàæäîãî ðåáðà pq âûðàæåíèå(i)fpq îáîçíà÷àåò i -å ñîáûòèå îòïðàâëåíèÿ ïðîöåññîì pñîîáùåíèÿ ïðîöåññó q ,(i)gpq îáîçíà÷àåò i -å ñîáûòèå ïðèåìà ïðîöåññîì qñîîáùåíèÿ îò ïðîöåññà p .Åñëè â êàíàëàõ ïîääåðæèâàåòñÿ î÷åðåäíîñòü ñîîáùåíèé, òî(i)(i)fpq gpq î÷åâèäíî âûïîëíÿåòñÿ.(i)(i)Îäíàêî îòíîøåíèå fpq gpq ñîáëþäàåòñÿ è â òåõ ñëó÷àÿõ,êîãäà êàíàë íå ÿâëÿåòñÿ î÷åðåäüþ.Ôàçîâûé àëãîðèòìËåììà 7.1.(i)(i)Ñîîòíîøåíèå fpq gpq ñîáëþäàåòñÿ è òîãäà, êîãäà êàíàë íåÿâëÿåòñÿ î÷åðåäüþ.Äîêàçàòåëüñòâî.(m )Ïóñòü m` òàêîâî, ÷òî fpq ` ýòî ñîáûòèå îòïðàâëåíèÿ ñîîá(`)ùåíèÿ, êîòîðîå ñîîòâåòñòâóåò gpq , ò.å.

ïðè âûïîëíåíèè ` -ãîñîáûòèÿ ïðèåìà ïðîöåññ q ïîëó÷àåò m` -å ñîîáùåíèå îò p .(m` )Ïî îïðåäåëåíèþ îòíîøåíèÿ èìååì fpq(`) gpq .Ôàçîâûé àëãîðèòìËåììà 7.1.(i)(i)Ñîîòíîøåíèå fpq gpq ñîáëþäàåòñÿ è òîãäà, êîãäà êàíàë íåÿâëÿåòñÿ î÷åðåäüþ.Äîêàçàòåëüñòâî.(m )Ïóñòü m` òàêîâî, ÷òî fpq ` ýòî ñîáûòèå îòïðàâëåíèÿ ñîîá(`)ùåíèÿ, êîòîðîå ñîîòâåòñòâóåò gpq , ò.å. ïðè âûïîëíåíèè ` -ãîñîáûòèÿ ïðèåìà ïðîöåññ q ïîëó÷àåò m` -å ñîîáùåíèå îò p .(m` )Ïî îïðåäåëåíèþ îòíîøåíèÿ èìååì fpq(`) gpq .Êàæäîå ñîîáùåíèå ïðèíèìàåòñÿ îäíîêðàòíî, ïîýòîìó âñå m`ðàçëè÷íû.

Ñëåäîâàòåëüíî, õîòÿ áû îäíî èç ÷èñåë m1 , . . . , miáóäåò íå ìåíüøå, ÷åì i .Ôàçîâûé àëãîðèòìËåììà 7.1.(i)(i)Ñîîòíîøåíèå fpq gpq ñîáëþäàåòñÿ è òîãäà, êîãäà êàíàë íåÿâëÿåòñÿ î÷åðåäüþ.Äîêàçàòåëüñòâî.(m )Ïóñòü m` òàêîâî, ÷òî fpq ` ýòî ñîáûòèå îòïðàâëåíèÿ ñîîá(`)ùåíèÿ, êîòîðîå ñîîòâåòñòâóåò gpq , ò.å. ïðè âûïîëíåíèè ` -ãîñîáûòèÿ ïðèåìà ïðîöåññ q ïîëó÷àåò m` -å ñîîáùåíèå îò p .(m` )Ïî îïðåäåëåíèþ îòíîøåíèÿ èìååì fpq(`) gpq .Êàæäîå ñîîáùåíèå ïðèíèìàåòñÿ îäíîêðàòíî, ïîýòîìó âñå m`ðàçëè÷íû. Ñëåäîâàòåëüíî, õîòÿ áû îäíî èç ÷èñåë m1 , .

. . , miáóäåò íå ìåíüøå, ÷åì i .Âûáåðåì j ≤ i òàêîå, ÷òî mj ≥ i .(i)(mj )Òîãäà fpq fpq(j)(i) gpq gpq .Ôàçîâûé àëãîðèòìÒåîðåìà î ôàçîâîì àëãîðèòìåÔàçîâûé àëãîðèòì ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó îòïðàâëÿåòñÿ íå áîëåå D ñîîáùåíèé.Çíà÷èò, âñå âû÷èñëåíèÿ àëãîðèòìà çàâåðøàþòñÿ.Ïóñòü γ çàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ âû÷èñëåíèÿ C .Ôàçîâûé àëãîðèòìÒåîðåìà î ôàçîâîì àëãîðèòìåÔàçîâûé àëãîðèòì ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó îòïðàâëÿåòñÿ íå áîëåå D ñîîáùåíèé.Çíà÷èò, âñå âû÷èñëåíèÿ àëãîðèòìà çàâåðøàþòñÿ.Ïóñòü γ çàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ âû÷èñëåíèÿ C .Ñíà÷àëà ïîêàæåì, ÷òî êàæäûé ïðîöåññ îòïðàâèë õîòü îäíîñîîáùåíèå.Ôàçîâûé àëãîðèòìÒåîðåìà î ôàçîâîì àëãîðèòìåÔàçîâûé àëãîðèòì ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó îòïðàâëÿåòñÿ íå áîëåå D ñîîáùåíèé.Çíà÷èò, âñå âû÷èñëåíèÿ àëãîðèòìà çàâåðøàþòñÿ.Ïóñòü γ çàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ âû÷èñëåíèÿ C .Ñíà÷àëà ïîêàæåì, ÷òî êàæäûé ïðîöåññ îòïðàâèë õîòü îäíîñîîáùåíèå.Ò.ê.

â êîíôèãóðàöèè γ â êàíàëàõ íåò ñîîáùåíèé,Recp [q] = Sentq äëÿ êàæäîãî êàíàëà qp .Ôàçîâûé àëãîðèòìp is initiator thenbegin forall r ∈ 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 ifendÊàæäûé èíèöèàòîð îòïðàâèë ñîîáùåíèå.Ôàçîâûé àëãîðèòì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Êàæäûé íå-èíèöèàòîð îòïðàâëÿåò ïåðâîå ñîîáùåíèå âñåìñîñåäÿì ñðàçó ïîñëå ïîëó÷åíèÿ ïåðâîãî ñîîáùåíèÿ îòêàêîãî-íèáóäü ñîñåäà.Ôàçîâûé àëãîðèòìÒåîðåìà î ôàçîâîì àëãîðèòìåÔàçîâûé àëãîðèòì ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó îòïðàâëÿåòñÿ íå áîëåå D ñîîáùåíèé.Çíà÷èò, âñå âû÷èñëåíèÿ àëãîðèòìà çàâåðøàþòñÿ.Ïóñòü γ çàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ âû÷èñëåíèÿ C .Ñíà÷àëà ïîêàæåì, ÷òî êàæäûé ïðîöåññ îòïðàâèë õîòü îäíîñîîáùåíèå.Ò.ê.