Лекция 8. Волновые алгоритмы - фазовый_ Финна. Распред. алгоритмы обхода - Тарри_ в глубину_ Авербаха и Сидона, страница 5
Описание файла
PDF-файл из архива "Лекция 8. Волновые алгоритмы - фазовый_ Финна. Распред. алгоритмы обхода - Тарри_ в глубину_ Авербаха и Сидона", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
Ýòî ãàðàíòèðóåò, ÷òî êàæäûéñîñåä r ïðîöåññà p îñâåäîìëåí ê ìîìåíòó îòïðàâëåíèÿ ìàðêåðàïðîöåññîì p î òîì, ÷òî ýòîò ìàðêåð óæå ïîáûâàë ó p .Êîãäà ïîçäíåå ìàðêåð äîñòèãíåò r , ïðîöåññ r óæå íå áóäåòîòïðàâëÿòü ìàðêåð ïðîöåññó p , åñëè òîëüêî p íå ÿâëÿåòñÿðîäèòåëüñêîé âåðøèíîé äëÿ r .Àëãîðèòì Àâåðáàõàvarusedp [q]fatherp: bool init false for each q ∈ Neighp ;(*Óêàçûâàåò, îòïðàâëÿë ëè p ìàðêåð ïðîöåññó q *): process init udef ;Òîëüêî äëÿ èíèöèàòîðà, âûïîëíèòü îäèí ðàç:begin fatherp := p ; choose q ∈ Neighp ;forall r ∈ Neighp do send hvisi to r ;forall r ∈ Neighp do receive hacki from r ;usedp [q] := true ; send htoki to qendÄëÿ êàæäîãî ïðîöåññà ïîñëå ïîëó÷åíèÿ htoki îò q0 :begin if fatherp = udef thenbegin fatherp := q0 ;forall r ∈ Neighp \ {fatherp } do send hvisi to r ;forall r ∈ Neighp \ {fatherp } do receive hacki from rend;if p is the initiator and ∀q ∈ Neighp : usedp [q]then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin if fatherp 6= q0 ∧ ¬usedp [q0 ]then q := q0else choose q ∈ Neighp \{fatherp } with ¬usedp [q]usedp [q] := true ; send htoki to qendelse beginusedp [fatherp ] := true ; send htoki to fatherpendÄëÿ êàæäîãî ïðîöåññà ïîñëå ïîëó÷åíèÿ hvisi îò q0 :begin usedp [q0 ] := true ; send hacki to q0 endendÀëãîðèòì ÀâåðáàõàÒåîðåìà î àëãîðèòìå ÀâåðáàõàÀëãîðèòì Àâåðáàõà ñòðîèò äåðåâî ïîèñêà â ãëóáèíó çà 4N − 2åäèíèö âðåìåíè, ïðîâîäÿ ïðè ýòîì 4|E | îáìåíîâ ñîîáùåíèÿìè.Àëãîðèòì Ñèäîíà àëãîðèòìå Ñèäîíà íå îòïðàâëÿþòñÿ ñîîáùåíèÿ ack, è çà ñ÷åòýòîãî óëó÷øàåòñÿ ñëîæíîñòü ïî âðåìåíè.
Ìàðêåð îòïðàâëÿåòñÿíåìåäëåííî, áåç çàäåðæêè íà äâå åäèíèöû âðåìåíè äëÿîæèäàíèÿ ïîäòâåðæäåíèé.Çäåñü âîçìîæíî âîçíèêíîâåíèå ñëåäóþùåé ñèòóàöèè. Âïðîöåññå p óæå ïîáûâàë ìàðêåð, è ýòîò ïðîöåññ óæå îòïðàâèëñîîáùåíèå vis ñâîåìó ñîñåäó r .Ïîçäíåå ìàðêåð äîñòàåòñÿ ïðîöåññó r , íî åùå äî òîãî, êàê visîò p äîñòèãëî r . Òîãäà r ìîæåò ïåðåäàòü ìàðêåð ïðîöåññó p ïîñòÿãèâàþùåìó ðåáðó.Àëãîðèòì Ñèäîíà×òîáû ñïðàâèòüñÿ ñ òàêîé ñèòóàöèåé, ïðîöåññ p çàïèñûâàåò (âïåðåìåííóþ lastp ) òåõ ñîñåäåé, êîòîðûì îí â ïîñëåäíþþî÷åðåäü îòïðàâëÿë ìàðêåð.Êîãäà ìàðêåð ïðîõîäèò òîëüêî ïî ðåáðàì äåðåâà, ïðîöåññ pïîëó÷àåò â î÷åðåäíîé ðàç ìàðêåð îò òîãî ñàìîãî ñîñåäà lastp .
Àâ òîì ñöåíàðèè, êîòîðûé áûë îïèñàí âûøå, p ïîëó÷àåò ìàðêåðîò äðóãîãî ñîñåäà, à èìåííî îò r .  ýòîì ñëó÷àå ìàðêåðèãíîðèðóåòñÿ, íî p ïîìå÷àåò ðåáðî rp êàê èñïîëüçîâàííîå, êàêáóäòî ïî íåìó áûëî ïîëó÷åíî ñîîáùåíèå vis îò r .Ïðîöåññ r ïîëó÷àåò îò p ñîîáùåíèå vis, ïîñëå òîãî êàê îíïåðåäàë ìàðêåð ïðîöåññó p , ò. å. r ïîëó÷àåò ñîîáùåíèå vis îòñâîåãî ñîñåäà lastr . Òîãäà r âåäåò ñåáÿ òàê, êàê åñëè áû îíâîîáùå íå ïåðåäàâàë ìàðêåð ïðîöåññó p , à èìåííî, r âûáèðàåòñëåäóþùåãî ñîñåäà è ïåðåäàåò åìó ìàðêåð.Àëãîðèòì Ñèäîíàvarusedp [q]fatherplastp: bool init false for each q ∈ Neighp ;(* Óêàçûâàåò, îòïðàâëÿë ëè p ìàðêåð ïðîöåññó q *): process init udef ;: process init udef ;Òîëüêî äëÿ èíèöèàòîðà, âûïîëíèòü îäèí ðàç:begin fatherp := p ; choose q ∈ Neighp ;forall r ∈ Neighp do send vis to r ;usedp [q] := true ; lastp := q ; send tok to qendÄëÿ êàæäîãî ïðîöåññà ïîñëå ïîëó÷åíèÿ vis îò q0 :begin usedp [q0 ] := true ;if q0 = lastp then (* Èñòîëêîâûâàòü êàê ñîîáùåíèå tokforward tok message as upon receipt of tok messageendÄëÿ êàæäîãî ïðîöåññà ïîñëå ïîëó÷åíèÿ tok îò q0 :begin if lastp 6= udef and lastp 6= q0 then usedp [q0 ] := true(* Ýòî ñòÿãèâàþùåå ðåáðî, èñòîëêîâûâàòü êàê ñîîáùåíèå vis *)else(* Ïîñòóïàòü, êàê â ïðåäûäóùåì àëãîðèòìå *)begin if fatherp = udef thenbegin fatherp := q0 ;forall r ∈ Neighp \{fatherp } do send vis to rend ;if p èíèöèàòîð and ∀q ∈ Neighp : usedp [q]then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin if fatherp 6= q0 ∧ ¬usedp [q0 ]then q := q0else choose q ∈ Neighp \ {fatherp }with ¬usedp [q] ;usedp [q] := true ; lastp := q ; send tok to qendelse beginendusedp [fatherp ] := true ; sendtokto fatherpÀëãîðèòì ÑèäîíàÒåîðåìà î àëãîðèòìå ÑèäîíàÀëãîðèòì Ñèäîíà ñòðîèò DFS äåðåâî çà 2N − 2 åäèíèöûâðåìåíè, èñïîëüçóÿ 4|E | îáìåíîâ ñîîáùåíèÿìè.Çàäà÷è1.
Ïðåäïîëîæèì, ÷òî åñòü æåëàíèå èñïîëüçîâàòü âîëíîâîéàëãîðèòì â ñåòè, â êîòîðîé âîçìîæíî äóáëèðîâàíèåñîîáùåíèé.IIÊàêèå èçìåíåíèÿ íóæíî âíåñòè â àëãîðèòì ýõà?Êàêèå èçìåíåíèÿ íóæíî âíåñòè â àëãîðèòì Ôèííà?2. Àäàïòèðóéòå àëãîðèòì ýõà äëÿ âû÷èñëåíèÿ ñóììû âõîäíûõäàííûõ âñåõ ïðîöåññîâ.ÊÎÍÅÖ ËÅÊÖÈÈ 7..
