10 Избрание лидера в произвольных сетях - алгоритм Галладжера-Хамблета-Спиры, алгоритм Кораха-Каттена-Морана, страница 2

åñëè ðåáðî pq áûëî óæå ó÷òåíî), òî ïðîöåññ pïðèêàçûâàåò ñîñåäíåìó ôðàãìåíòó ðàâíîïðàâíî îáúåäèíèòüñÿ¾íà áîëåå âûñîêîì óðîâíå¿, ïðèíÿâ â êà÷åñòâå íîâîãî èìåíèäëÿ îáúåäèíåííîãî ôðàãìåíòà âåñ ñòåðæíåâîãî ðåáðà pq .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÂîïðîñ.À îòêóäà èçâåñòíî ïðîöåññó p , ÷òî â ïîñëåäíåì ñëó÷àå ðàíãèôðàãìåíòîâ ðàâíû?Âîçìîæåí ëè òàêîé ñëó÷àé, êîãäà ñîñåäíèé ôðàãìåíò(êîòîðîìó ïðèíàäëåæèò óçåë q ) èìååò ðàíã, ïðåâîñõîäÿùèéðàíã òîãî ôðàãìåíòà, êîòîðîìó ïðèíàäëåæèò óçåë p ?È ÷òî â òàêîì ñëó÷àå äåëàåò ïðîöåññ p ?Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(3) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hinitiate, L, F , Si îò q :begin level p := L ; name p := F ; statep := S ; fatherp := q ;bestchp := udef ; bestwtp := ∞ ;forall r ∈ Neighp : stachp [r ] = branch ∧ r 6= q dosend hinitiate, L, F , Si to r ;if statep = find then begin recp := 0 ; test endendÏîñëå ïðèêàçà îá îáúåäèíåíèè, ïðîöåññ p èçìåíÿåò ñâîå èìÿ,ðàíã, ñòàòóñ è íàïðàâëåíèå ê ñòåðæíåâîìó óçëó,...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(3) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hinitiate, L, F , Si îò q :begin level p := L ; name p := F ; statep := S ; fatherp := q ;bestchp := udef ; bestwtp := ∞ ;forall r ∈ Neighp : stachp [r ] = branch ∧ r 6= q dosend hinitiate, L, F , Si to r ;if statep = find then begin recp := 0 ; test endend¾ñáðàñûâàåò¿ ñâîè òåêóùèå ïîêàçàòåëè ïîèñêà èñõîäÿùåãîðåáðà íàèìåíüøåãî âåñà,...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(3) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hinitiate, L, F , Si îò q :begin level p := L ; name p := F ; statep := S ; fatherp := q ;bestchp := udef ; bestwtp := ∞ ;forall r ∈ Neighp : stachp [r ] = branch ∧ r 6= q dosend hinitiate, L, F , Si to r ;if statep = find then begin recp := 0 ; test endendîòïðàâëÿåò ñâîèì ñîñåäÿì ïî ôðàãìåíòó ïðèêàç îïðèñîåäèíåíèè â ñâÿçè ñ îáðàçîâàíèåì íîâîãî ôðàãìåíòà,...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(3) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hinitiate, L, F , Si îò q :begin level p := L ; name p := F ; statep := S ; fatherp := q ;bestchp := udef ; bestwtp := ∞ ;forall r ∈ Neighp : stachp [r ] = branch ∧ r 6= q dosend hinitiate, L, F , Si to r ;if statep = find then begin recp := 0 ; test endendè â òîì ñëó÷àå, åñëè ñòàòóñ óçëà òðåáóåò ïðîäîëæàòü ïîèñêðåáðà íàèìåíüøåãî âåñà, òî ïðèñîåäèíÿåòñÿ ê ýòîìó ïîèñêó,çàïóñòèâ ïðîöåäóðó test .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÂîïðîñ.À çà÷åì ïðîöåññ p ¾ñáðàñûâàåò¿ òåêóùèå ïîêàçàòåëè ïîèñêà(ïåðåìåííûå bestch è bestwt ), à íå ïðîäîëæàåò ïîèñê, ñîõðàíÿÿäîñòèãíóòûå ïîêàçàòåëè?Áóäåò ëè àëãîðèòì ðàáîòàòü êîððåêòíî, åñëè ýòîãî ¾ñáðîñà¿ïîêàçàòåëåé ïîèñêà íå äåëàòü?Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(4) procedure test:begin if ∃q ∈ Neighp : stachp [q] = basic thenbegin testchp := q with stachp [q] = basicand ω(pq) minimal ;send htest, level p , name p i to testchpendendelse begin testchp := udef ; report endÓçåë p , ñòðåìÿñü îòûñêàòü èñõîäÿùåå èç íåãî ðåáðîíàèìåíüøåãî âåñà, ïðîñìàòðèâàåò îäíî çà äðóãèì â ïîðÿäêåâîçðàñòàíèÿ âåñà âñå ïðèìûêàþùèå ê íåìó ðåáðà, èìåþùèåñòàòóñ basic .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(4) procedure test:begin if ∃q ∈ Neighp : stachp [q] = basic thenbegin testchp := q with stachp [q] = basicand ω(pq) minimal ;send htest, level p , name p i to testchpendendelse begin testchp := udef ; report endÅñëè èç óçëà p èñõîäèò õîòÿ áû îäíî ¾ñâåæåå¿ ðåáðî(èìåþùåå ñòàòóñ basic ), òî ïðîöåññ p âûáèðàåò ðåáðîíàèìåíüøåãî âåñà, è îòïðàâëÿåò ïî ýòîìó êàíàëó çàïðîñ îáèìåíè è ðàíãå ôðàãìåíòà, êîòîðîìó ïðèíàäëåæèò óçåë q ,ïðèñîåäèíåííûé ê ýòîìó ðåáðó.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(4) procedure test:begin if ∃q ∈ Neighp : stachp [q] = basic thenbegin testchp := q with stachp [q] = basicand ω(pq) minimal ;send htest, level p , name p i to testchpendendelse begin testchp := udef ; report endÀ åñëè âñå èñõîäÿùèå ðåáðà óæå áûëè îïðîáîâàíû ðàíåå, òîóçåë p çàïóñêàåò ïðîöåäóðó ñîñòàâëåíèÿ äîêëàäà report îðåçóëüòàòàõ ïîèñêà.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(5) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ htest, L, F i îò q :begin if L > level p then(* Ñ îòâåòîì ïðèäåòñÿ ïîäîæäàòü! *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if F = name p then (* âíóòðåííåå ðåáðî *)begin if stachp [q] = basic then stachp [q] := reject ;if q 6= testchpthen send hrejecti to qelse testendendelse send haccepti to qÏðè ïîëó÷åíèè çàïðîñà îá èìåíè è ðàíãå ôðàãìåíòà, êîòîðîìóïðèíàäëåæèò óçåë p , ïðîâîäèòñÿ ïðîâåðêà ðàíãà òîãîôðàãìåíòà, êîòîðîìó ïðèíàäëåæèò óçåë, îòïðàâèâøèé çàïðîñ.Åñëè çàïðîñ ïðèøåë îò ôðàãìåíòà áîëåå âûñîêîãî ðàíãà, òîîòêëèê îòêëàäûâàåòñÿ (ÏÎ×ÅÌÓ??? Óçåë p â ÷åì òî íåóâåðåí? ).Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(5) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ htest, L, F i îò q :begin if L > level p then (* Ñ îòâåòîì ïðèäåòñÿ ïîäîæäàòü! *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if F = name p then (* âíóòðåííåå ðåáðî *)begin if stachp [q] = basic then stachp [q] := reject ;if q 6= testchpthen send hrejecti to qelse testendendelse send haccepti to qÀ åñëè ðàíã ôðàãìåíòà, îò êîòîðîãî ïîñòóïèë çàïðîñ íåïðåâîñõîäèò ðàíãà ôðàãìåíòà, êîòîðîìó ïðèíàäëåæèò óçåë p ,òî óçåë ïðîâåðÿåò èìÿ òîãî ôðàãìåíòà îò êîòîðîãî ïîñòóïèëçàïðîñ.

È åñëè p îáíàðóæèâàåò, ÷òî óçåë q ïðèíàäëåæèò òîìóæå ôðàãìåíòó, òî ...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(5) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ htest, L, F i îò q :begin if L > level p then (* Ñ îòâåòîì ïðèäåòñÿ ïîäîæäàòü! *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if F = name p then (* âíóòðåííåå ðåáðî *)begin if stachp [q] = basic then stachp [q] := reject ;if q 6= testchpthen send hrejecti to qelse testendendelse send haccepti to qýòî îçíà÷àåò, ÷òî ðåáðî pq âíóòðåííåå ðåáðî ôðàãìåíòà, èåìó ïðèñâàèâàåòñÿ ñòàòóñ reject .

Ïîñëå ýòîãî â àäðåñ óçëà qîòïðàâëÿåòñÿ ëèáî ñîîáùåíèå îá ýòîì hrejecti, ëèáî çàïóñêàåòïðîöåäóðó test (åñëè óçåë q áûë óçëîì, â êîòîðûé âåëî ðåáðîíàèìåíüøåãî âåñà èç óçëà p ).Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÂîïðîñ.À ïî÷åìó ïðîöåññ p íå îòïðàâëÿåò ïðîöåññó q ñîîáùåíèÿhrejecti â ïðîòèâíîì ñëó÷àå?Íå ââîäèò ëè îí òåì ñàìûì ïðîöåññ q â çàáëóæäåíèå î ñòàòóñåðåáðà pq ?È çà÷åì åìó íóæíî ñíîâà çàïóñêàòü ïðîöåäóðó test ?Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(5) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ htest, L, F i îò q :begin if L > level p then (* Ñ îòâåòîì ïðèäåòñÿ ïîäîæäàòü! *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if F = name p then (* âíóòðåííåå ðåáðî *)begin if stachp [q] = basic then stachp [q] := reject ;if q 6= testchpthen send hrejecti to qelse testendendelse send haccepti to qÈ, íàêîíåö, åñëè óçëû p è q ïðèíàäëåæàò ðàçíûì ôðàãìåíòàì,òî p ñîîáùàåò îá ýòîì óçëó q .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(6) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ haccepti îò q :begin testchp := udef ;if ω(pq) < bestwtpthen begin bestwtp := ω(pq) ; bestchp := q end;reportendÅñëè ïîëó÷åíî ïîäòâåðæäåíèå î òîì, ÷òî ïðîâåðÿåìîå ðåáðî pqñîåäèíÿåò óçëû, ïðèíàäëåæàùèå ðàçíûì ôðàãìåíòàì, òîïðîöåññ p çàâåðøàåò ïîèñê íàèëó÷øåãî ðåáðà, ñ÷èòàÿ, ÷òî ýòî ðåáðî pq , è ïðèñòóïàåò ê ïîäãîòîâêå îò÷åòà â ¾öåíòð¿,çàïóñêàÿ ïðîöåäóðó report .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÂîïðîñ.À çà÷åì ¾ñáðàñûâàåòñÿ¿ çíà÷åíèå ïåðåìåííîé testchp ?À ñîõðàíèò ëè àëãîðèòì êîððåêòíîñòü, åñëè óäàëèòü îïåðàòîðtestchp := udef ?Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(7) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hrejecti îò q :begin if stachp [q] = basic then stachp [q] := reject ;testendÅñëè ïîëó÷åíî ïîäòâåðæäåíèå î òîì, ÷òî ïðîâåðÿåìîå ðåáðî pqcîåäèíÿåò óçëû, ïðèíàäëåæàùèå îäíîìó è òîìó æå ôðàãìåíòó,òî ïðîöåññ p îòìå÷àåò ýòî, è ïðèñòóïàåò ê âûáîðó äðóãîãîèñõîäÿùåãî ðåáðà, çàïóñêàÿ ïðîöåäóðó test .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(8) procedure report:begin if recp = #{q : stachp [q] = branch ∧ q 6= fatherp }and testchp = udef thenbegin statep := found ; send hreport, bestwtp i to fatherp endendÅñëè ïðîöåññ p ïîëó÷èë îò âñåõ ñîñåäåé ïî ôðàãìåíòó (çàèñêëþ÷åíèåì, òîãî, êîòîðûé ðàñïîëàãàåòñÿ ïî ïóòè âñòåðæíåâîé óçåë) äàííûå î íàèëó÷øèõ ðåáðàõ, è ñàì ïðîöåññ píå ïðîâîäèò áîëåå ïîèñêà íàèëó÷øåãî ðåáðà, òî îí îòïðàâëÿåòïî íàïðàâëåíèþ ê ñòåðæíåâîìó óçëó ñîîáùåíèå ñ óêàçàíèåìâåñà ýòîãî íàèëó÷øåãî ðåáðà.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(9) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hreport, ωi îò q :begin if q 6= fatherpthen (* îòâåòèòü íà ñîîáùåíèå initiate *)begin if ω < bestwtp thenbegin bestwtp := ω ; bestchp := q end;recp := recp + 1 ; reportendendelse (* ðåáðî pq íà ïóòè â ñòåðæåíü *)if statep = findthen îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if ω > bestwtpthen changerootelse if ω = bestwtp = ∞ then stopÅñëè ïðîöåññ p ïîëó÷èë îò ïðîöåññà q (ýòî ìîæåò áûòü òîëüêî åãî ñîñåä ïîôðàãìåíòó (ïî÷åìó? )) äîêëàä î âåñå íàèëó÷øåãî ðåáðà, èñõîäÿùåãî èç óçëîâñîîòâåòñòâóþùåãî ïîääåðåâà, òî p âûÿñíÿåò, êóäó âåäåò ýòî ðåáðî.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(9) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hreport, ωi îò q :begin if q 6= fatherpthen (* îòâåòèòü íà ñîîáùåíèå initiate *)begin if ω < bestwtp thenbegin bestwtp := ω ; bestchp := q end;recp := recp + 1 ; reportendendelse (* ðåáðî pq íà ïóòè â ñòåðæåíü *)if statep = findthen îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if ω > bestwtpthen changerootelse if ω = bestwtp = ∞ then stopÅñëè ðåáðî pq íå ëåæèò íà ïóòè èç p â ñòåðæíåâîé óçåë òîãî ôðàãìåíòà,êîòîðîìó ïðèíàäëåæèò p , òî p óòî÷íÿåò âåñ è íàïðàâëåíèå ê íàèëó÷øåìó ðåáðó,è ïûòàåòñÿ ïðèñòóïèòü ê ïîäãîòîâêå îò÷åòà, âûçûâàÿ ïðîöåäóðó report .Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(9) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hreport, ωi îò q :begin if q 6= fatherpthen (* îòâåòèòü íà ñîîáùåíèå initiate *)begin if ω < bestwtp thenbegin bestwtp := ω ; bestchp := q end;recp := recp + 1 ; reportendendelse (* ðåáðî pq íà ïóòè â ñòåðæåíü *)if statep = findthen îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if ω > bestwtpthen changerootelse if ω = bestwtp = ∞ then stopÅñëè äîêëàä, ïîëó÷åííûé p , ïîñòóïèë îò ïðîöåññà q , êîòîðûé ëåæèò íà ïóòè èçp â ñòåðæåíü, òî â òîì ñëó÷àå, åñëè p åùå íå çàâåðøèë ïîèñê íàèëó÷øåãî ðåáðà,òî p îòêëàäûâàåò îáðàáîòêó ýòîãî ñîîáùåíèÿ, ïîêà íàéäåò íàèëó÷øåå ðåáðî.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(9) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hreport, ωi îò q :begin if q 6= fatherpthen (* îòâåòèòü íà ñîîáùåíèå initiate *)begin if ω < bestwtp thenbegin bestwtp := ω ; bestchp := q end;recp := recp + 1 ; reportendendelse (* ðåáðî pq íà ïóòè â ñòåðæåíü *)if statep = findthen îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse if ω > bestwtpthen changerootelse if ω = bestwtp = ∞ then stopÀ åñëè âåñ ðåáðà, íàéäåííîãî p , ìåíüøå òîãî âåñà, êîòîðûé íàøåë q , òîîáúåäèíåíèå ôðàãìåíòà, ê êîòîðîìó ïðèíàäëåæèò p , áóäåò ïðîâîäèòüñÿ ïî òîìóðåáðó, êîòîðîå ñóìåë îòûñêàòü p .