8 Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон
Описание файла
PDF-файл из архива "8 Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 7.Âîëíîâûå àëãîðèòìû.Ôàçîâûé àëãîðèòì.Àëãîðèòì Ôèííà.Ðàñïðåäåëåííûå àëãîðèòìû îáõîäà:îñíîâíûå ñâîéñòâà.Àëãîðèòì îáõîäà Òàððè.Ðàñïðåäåëåííûé îáõîä â ãëóáèíó.Àëãîðèòìû Àâåðáàõà è Ñèäîíà.Âîëíîâûå àëãîðèòìûÎïðåäåëåíèå.Âîëíîâûì àëãîðèòìîì íàçûâàåòñÿ ðàñïðåäåëåííûé àëãîðèòì,êîòîðûé óäîâëåòâîðÿåò ñëåäóþùèì òðåì òðåáîâàíèÿì.1.Çàâåðøåíèå.Êàæäîå âû÷èñëåíèå êîíå÷íî:∀C : |C | < ∞.2.Êàæäîå âû÷èñëåíèå ñîäåðæèò õîòÿ áû îäíîñîáûòèå ðåøåíèÿ:Ðåøåíèå.∀C : ∃e ∈ C : e ÿâëÿåòñÿ ñîáûòèåì ðåøåíèÿ decide.3. ëþáîì âû÷èñëåíèè âñÿêîìó ñîáûòèþðåøåíèÿ ïðåäøåñòâóåò â ïðè÷èííî-ñëåäñòâåííîìîòíîøåíèè õîòÿ áû îäíî ñîáûòèå â êàæäîì èç ïðîöåññîâ:Çàâèñèìîñòü.Âîëíîâûå àëãîðèòìûÂîëíîâûå àëãîðèòìû ïðèãîäíû äëÿ ðåøåíèÿ ñëåäóþùèõ çàäà÷:1.Øèðîêîâåùàòåëüíîå ðàñïðîñòðàíåíèå èíôîðìàöèè ñïîäòâåðæäåíèåì.2.Ñèíõðîíèçàöèè ïðîöåññîâ ñèñòåìû.3.Âû÷èñëåíèÿ ãëîáàëüíîé ôóíêöèè òî÷íîé íèæíåéãðàíè.4.
è ìíîãèõ äðóãèõ (èçáðàíèÿ ëèäåðà, îáíàðóæåíèÿçàâåðøåíèÿ è äð.)Âîëíîâûå àëãîðèòìûÎñíîâíûå âîëíîâûå àëãîðèòìû:1.Âîëíîâûå àëãîðèòìû â êîëüöàõ.2.Äðåâåñíûé âîëíîâîé àëãîðèòì.3.Àëãîðèòì ýõà.Íî ýòè àëãîðèòìû ðàáîòàþò òîëüêî â ñåòÿõ ñ äâóñòîðîííèìèêàíàëàìè ñâÿçè (íåîðèåíòèðîâàííûìè ãðàôàìè).Ðàññìîòðèì åùå íåñêîëüêî áîëåå îáùèõ àëãîðèòìîâ: ôàçîâûéàëãîðèòì è àëãîðèòì Ôèííà.Ôàçîâûé àëãîðèòìÔàçîâûé àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì àëãîðèòìîì,ïðèãîäíûì äëÿ ñåòåé ñ ïðîèçâîëüíîé òîïîëîãèåé. Îí ïðèãîäåíäëÿ îðèåíòèðîâàííûõ ñåòåé. ýòîì àëãîðèòìå òðåáóåòñÿ, ÷òîáû âñå ïðîöåññû ðàñïîëàãàëèñâåäåíèÿìè î äèàìåòðå ñåòè D .
Àëãîðèòì áóäåò îñòàâàòüñÿêîððåêòíûì (õîòÿ è ìåíåå ýôôåêòèâíûì), åñëè âñå ïðîöåññûáóäóò èñïîëüçîâàòü âìåñòî D êîíñòàíòó D 0 , ïðåâûøàþùóþäèàìåòð ñåòè.Ôàçîâûé àëãîðèòì ïðèìåíèì äëÿ âñÿêîé îðèåíòèðîâàííîéñåòè, ïî êàíàëàì êîòîðîé îñóùåñòâëÿåòñÿ îäíîñòîðîííÿÿïåðåäà÷à ñîîáùåíèé.  ýòîì ñëó÷àå ñîñåäÿìè âåðøèíû p áóäóòñîñåäè íà âõîäå (ïðîöåññû, êîòîðûå ìîãóò îòïðàâëÿòüñîîáùåíèÿ ïðîöåññó p ) è ñîñåäè íà âûõîäå (ïðîöåññû, êîòîðûìp ìîæåò îòïðàâëÿòü ñîîáùåíèÿ). Ñîñåäè p íà âõîäå îáðàçóþòìíîæåñòâî Inp , à ñîñåäè íà âûõîäå ìíîæåñòâî Outp .Ôàçîâûé àëãîðèòìÎñíîâíàÿ èäåÿ.1.
Êàæäûé ïðîöåññ îòïðàâëÿåò â òî÷íîñòè Dñîîáùåíèé êàæäîìó ñîñåäó íà âûõîäå.2. Êàæäîìó ñîñåäó íà âûõîäå áóäåò îòïðàâëåíî(i + 1) -îå ñîîáùåíèå ïîñëå òîãî, êàê îò êàæäîãîñîñåäà íà âõîäå áûëè ïîëó÷åíû i ñîîáùåíèé.3. Êàê òîëüêî îò êàæäîãî ñîñåäà áóäåò ïîëó÷åíî âòî÷íîñòè 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=3p2tokRec2 = (0)Sent = 02@@@@@ 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@@@@p1 @ Rec4 = (1, 0)R@p4tokSent = 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@tokSent1 = 2@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@tok@@ Rec4 = (1, 0)R@p1 p4Sent = 14@Rec1 = (1) @tok@tokSent1 = 2@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@@ Rec4 = (2, 0)R@p1 p4Sent = 14@Rec1 = (1) @tok@tokSent1 = 2@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@@ Rec4 = (2, 0)R@p1 p4Sent = 14@Rec1 = (1) @toktok@Sent1 = 2@@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@p1 @ Rec4 = (2, 1)R@p4tokSent = 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@tokSent1 = 3@@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìdecideD=3p2Rec2 = (3)Sent = 32@@@tok@@ Rec4 = (2, 1)R@p1 p4Sent = 24@Rec1 = (2) @tok@tokSent1 = 3@@ 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 .Êàæäîå ñîîáùåíèå ïðèíèìàåòñÿ îäíîêðàòíî, ïîýòîìó âñå m`ðàçëè÷íû. Ñëåäîâàòåëüíî, õîòÿ áû îäíî èç ÷èñåë m1 , . . . , miáóäåò íå ìåíüøå, ÷åì i .Âûáåðåì j ≤ i òàêîå, ÷òî mj ≥ i .(i)(mj )Òîãäà fpq fpq(j)(i) gpq gpq .Ôàçîâûé àëãîðèòìÒåîðåìà î ôàçîâîì àëãîðèòìåÔàçîâûé àëãîðèòì ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó îòïðàâëÿåòñÿ íå áîëåå 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 .Ñíà÷àëà ïîêàæåì, ÷òî êàæäûé ïðîöåññ îòïðàâèë õîòü îäíîñîîáùåíèå.Ò.ê.
â êîíôèãóðàöèè γ â êàíàëàõ íåò ñîîáùåíèé,Recp [q] = Sentq äëÿ êàæäîãî êàíàëà qp .Êàæäûé èíèöèàòîð îòïðàâèë ñîîáùåíèå.Êàæäûé íå-èíèöèàòîð îòïðàâëÿåò ïåðâîå ñîîáùåíèå âñåìñîñåäÿì ñðàçó ïîñëå ïîëó÷åíèÿ ïåðâîãî ñîîáùåíèÿ.Çíà÷èò, åñëè ñèëüíî ñâÿçíàÿ ñåòü èìååò õîòü îäíîãîèíèöèàòîðà, òî Sentp > 0 äëÿ êàæäîãî óçëà 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 .Çíà÷èò, Sentp = D ; â ïðîòèâíîì ñëó÷àå p ïðèøëîñü áûîòïðàâëÿòü äîïîëíèòåëüíîå ñîîáùåíèå, êàê òîëüêî îí âïîñëåäíèé ðàç ïîëó÷èë íåêîòîðîå ñîîáùåíèå.Çíà÷èò, Sentp = D äëÿ âñåõ p , è, ñëåäîâàòåëüíî, äëÿ âñåõêàíàëîâ qp èìååò ìåñòî ðàâåíñòâî Recp [q] = D .Îòñþäà çàêëþ÷àåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî âñÿêîìó ðåøåíèþ ïðåäøåñòâóåò õîòü îäíîñîáûòèå â êàæäîì èç ïðîöåññîâ.Ðàññìîòðèì ïóòü â ñåòè P = p0 , p1 , .