8 Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон, страница 2
Описание файла
PDF-файл из архива "8 Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
. . , 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 |îáîçíà÷àåò êîëè÷åñòâî îäíîñòîðîííèõ êàíàëîâ.Åñëè ôàçîâûé àëãîðèòì èñïîëüçóåòñÿ äëÿíåîðèåíòèðîâàííîé ñåòè, òî êàæäûé åå êàíàëñëåäóåò ðàññìàòðèâàòü êàê äâà îäíîñòîðîííèõêàíàëà, è ïîýòîìó ñëîæíîñòü ïî ÷èñëó ñîîáùåíèéáóäåò ðàâíà 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 = ∅ .2) Ïðîöåññ p îòïðàâëÿåò ñîîáùåíèÿ, ñîäåðæàùèå Incp è NIncp ,âñÿêèé ðàç, êîãäà îäíî èç ýòèõ ìíîæåñòâ ðàñøèðÿåòñÿ.3) Êîãäà p ïîëó÷àåò ñîîáùåíèå c ìíîæåñòâàìè Inc è NInc ,ïîëó÷åííûå îòëè÷èòåëüíûå ïðèçíàêè äîáàâëÿþòñÿ êìíîæåñòâàìIncp è NIncp .4) Åñëè p ïîëó÷èë ñîîáùåíèÿ îò âñåõ ñâîèõ ñîñåäåé íà âõîäå,òî îòëè÷èòåëüíûé ïðèçíàê p âñòàâëÿåòñÿ â NIncp .5) Åñëè Incp = NIncp , òî p ïðèíèìàåò ðåøåíèå dp .Ðàâåíñòâî Incp = NIncp îçíà÷àåò, ÷òî êàêîâ áû íè áûë ïðîöåññq , åñëè íåêîòîðîå ñîáûòèå â q ïðåäøåñòâóåò dp , òî ó âñÿêîãîåãî ñîñåäà r êàêîå-íèáóäü ñîáûòèå òàêæå ïðåäøåñòâóåò dp .Ò.ê.
p ∈ Incp è ñåòü ñèëüíî ñâÿçíàÿ, êàêîå-íèáóäü ñîáûòèå âêàæäîì ïðîöåññå ïðåäøåñòâóåò 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Ôàçîâûé àëãîðèòì p2 p1 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Ôàçîâûé àëãîðèòì p2 p1 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)i p1 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 | . Ïîýòîìóâûïîëíåíèÿ àëãîðèòì çàâåðøàþòñÿ.Ðàññìîòðèì çàêëþ÷èòåëüíóþ êîíôèãóðàöèþ γ âû÷èñëåíèÿ C .Êàê è â äîêàçàòåëüñòâå ïðåäûäóùåé òåîðåìû, ìîæíî ïîêàçàòü,÷òî åñëè ïðîöåññ p ñóìåë îòïðàâèòü õîòÿ áû îäíî ñîîáùåíèå(êàæäîìó ñîñåäó), è q ñîñåä ïðîöåññà p íà âûõîäå, òî qòàêæå ñóìåë îòïðàâèòü õîòü îäíî ñîîáùåíèå.Îòñþäà ñëåäóåò, ÷òî êàæäûé ïðîöåññ ñóìåë îòïðàâèòü õîòÿ áûîäíî ñîîáùåíèå (ïî êàæäîìó êàíàëó).Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî â γ êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.1) Äëÿ êàæäîãî ðåáðà pq â êîíôèãóðàöèè γ âûïîëíÿåòñÿIncp ⊆ Incq , ò.ê., ñîâåðøèâ ïîñëåäíåå èçìåíåíèå ìíîæåñòâàIncp , ïðîöåññ p îòïðàâèë ñîîáùåíèå hsets, Incp , NIncp i .Êàê òîëüêî îíî áûëî ïîëó÷åíî, q âûïîëíèë îïåðàòîðIncq := Incq ∪ Incp .Ñèëüíàÿ ñâÿçíîñòü ñåòè ïðèâîäèò ê òîìó, ÷òî Incp = Incq äëÿâñåõ p è q .
Ò.ê. p ∈ Incp , äëÿ êàæäîãî ïðîöåññà p âêîíôèãóðàöèè γ âûïîëíÿåòñÿ Incp = P .Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.2) Àíàëîãè÷íûì îáðàçîì ìîæíî ïîêàçàòü, ÷òî äëÿ êàæäîéïàðû ïðîöåññîâ p è q âûïîëíÿåòñÿ NIncp = NIncq .Ïîñêîëüêó êàæäûé ïðîöåññ óñïåë îòïðàâèòü õîòÿ áû îäíîñîîáùåíèå ïî êàæäîìó êàíàëó, äëÿ ëþáîãî ïðîöåññà pâûïîëíÿåòñÿ òðåáîâàíèå ∀q ∈ Inp : recp [q] . Ñëåäîâàòåëüíî,p ∈ NIncp äëÿ êàæäîãî p .Îòñþäà ñëåäóåò, ÷òî NIncp = P äëÿ êàæäîãî ïðîöåññà p .Èç Incp = P è NIncp = P âûòåêàåò, ÷òî Incp = NIncp , è ýòîîçíà÷àåò, ÷òî â êîíôèãóðàöèè γ êàæäûé ïðîöåññ p ïðèíÿëðåøåíèå.Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî ðåøåíèþ dp â ïðîöåññå p ïðåäøåñòâóåòêàêîå-íèáóäü ñîáûòèå â êàæäîì èç ïðîöåññîâ.(f )(f )Äëÿ âñÿêîãî ñîáûòèÿ f â ïðîöåññå p îáîçíà÷èì Incp (NIncp )çíà÷åíèå Incp (NIncp , ñîîòâåòñòâåííî) ñðàçó ïîñëåîñóùåñòâëåíèÿ f . Ñëåäóþùèå äâà óòâåðæäåíèÿ îáîñíîâûâàþòñîäåðæàòåëüíûé ñìûñë ìíîæåñòâ Incp è NIncp .Óòâåðæäåíèå 1.(f )Åñëè ñóùåñòâóåò ñîáûòèå e ∈ Cq : e f , òî q ∈ Incp.Óòâåðæäåíèå 2.(f )Åñëè q ∈ NIncpe ∈ Cr : e f ., òî äëÿ âñåõ r ∈ Inq ñóùåñòâóåò ñîáûòèåÀëãîðèòì ÔèííàÓòâåðæäåíèå 1.Åñëè ñóùåñòâóåò ñîáûòèå e ∈ Cq : e f , òî q ∈ Inc (f ) .Îáîñíîâàíèå.Ñàìîñòîÿòåëüíî èíäóêöèåé ïî äëèíå ïðè÷èííî-ñëåäñòâåííîéöåïî÷êè ìåæäó ñîáûòèÿìè e è f .Àëãîðèòì ÔèííàÓòâåðæäåíèå 2.Åñëè q ∈ NInc (f ) , òî äëÿ âñåõ r ∈ Inq ñóùåñòâóåò ñîáûòèåe ∈ Cr : e f .Îáîñíîâàíèå.Ïóñòü aq îáîçíà÷àåò âíóòðåííåå ñîáûòèå â ïðîöåññå q ,ñâÿçàííîå ñ ïåðâûì âûïîëíåíèåì îïåðàòîðàNIncq := NIncq ∪ {q} ïðîöåññîì q .
