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

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 9.Çàäà÷à èçáðàíèÿ ëèäåðà.Íèæíèå îöåíêè ñëîæíîñòè.Îïòèìàëüíûå âûáîðû.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS).Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHS.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíà.Çàäà÷à èçáðàíèÿ ëèäåðàÇàäà÷à èçáðàíèÿ ëèäåðà ñîñòîèò â òîì, ÷òîáû, èñõîäÿ èçêîíôèãóðàöèè, â êîòîðîé âñå ïðîöåññû ïðåáûâàþò â îäíîì èòîì æå ñîñòîÿíèè, äîñòè÷ü òàêîé êîíôèãóðàöèè, â êîòîðîéðîâíî îäèí ïðîöåññ áóäåò íàõîäèòüñÿ â ñîñòîÿíèè leader , òîãäàêàê âñå îñòàëüíûå ïðîöåññû áóäóò ïðåáûâàòü â ñîñòîÿíèè lost .ÎïðåäåëåíèåÀëãîðèòìîì èçáðàíèÿ ëèäåðà íàçûâàåòñÿ àëãîðèòì,êîòîðûé îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè.1. Êàæäûé ïðîöåññ íàäåëåí îäíèì è òåì æå ëîêàëüíûìàëãîðèòìîì.2. Àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì.3.

Àëãîðèòì äîñòèãàåò çàêëþ÷èòåëüíîé êîíôèãóðàöèè âêàæäîì âû÷èñëåíèè, è â êàæäîé çàêëþ÷èòåëüíîéêîíôèãóðàöèè ñóùåñòâóåò ðîâíî îäèí ïðîöåññ, êîòîðûéíàõîäèòñÿ â ñîñòîÿíèè leader à âñå îñòàëüíûå ïðîöåññûïðè ýòîì ïðåáûâàþò â ñîñòîÿíèè lost.Íèæíèå îöåíêè ñëîæíîñòè àëãîðèòìîâèçáðàíèÿ ëèäåðàÒåîðåìà.Âñÿêèé àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå ñðàâíåíèÿ äëÿïðîèçâîëüíûõ ñåòåé èìååò ñëîæíîñòü (è â ñðåäíåì, è âíàèõóäøåì ñëó÷àå) íå ìåíüøóþ, ÷åì Ω(|E | + N log N) .Ñëåäñòâèå.Âñÿêèé äåöåíòðàëèçîâàííûé âîëíîâîé àëãîðèòì äëÿïðîèçâîëüíûõ ñåòåé áåç ïðåäâàðèòåëüíîé îñâåäîìëåííîñòè îñîñåäÿõ èìååò ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè, íåìåíüøóþ ÷åì Ω(|E | + N log N) .Íèæíèå îöåíêè ñëîæíîñòè àëãîðèòìîâèçáðàíèÿ ëèäåðà'$Ñåòü Sïðîöåññ p1~~ïðîöåññ p2&%Íèæíèå îöåíêè ñëîæíîñòè àëãîðèòìîâèçáðàíèÿ ëèäåðà''$Ñåòü SÑåòü Sïðîöåññ p1&ïðîöåññ p10~~~~ïðîöåññ p2$0ïðîöåññ p20%&%Íèæíèå îöåíêè ñëîæíîñòè àëãîðèòìîâèçáðàíèÿ ëèäåðà'$'Ñåòü SÑåòü Sïðîöåññ p1$0ïðîöåññ p10~@@~@@~ïðîöåññ p2&@@~ïðîöåññ p20%&%Îïòèìàëüíûå âûáîðûÂÎÏÐÎÑ.Ìîæíî ëè ïðîâåñòè âûáîðû ëèäåðà âïðîèçâîëüíûõ ñåòÿõ ñ èñïîëüçîâàíèåìO(|E | + N log N)îáìåíîâ ñîîáùåíèÿìè?Çàäà÷è èçáðàíèÿ ëèäåðà è ïîñòðîåíèÿ îñòîâíîãî äåðåâà òåñíîñâÿçàíû äðóã ñ äðóãîì.ÏóñòüCE ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè çàäà÷è îâûáîðàõ,à CT äëÿ ñëîæíîñòü ïîñòðîåíèÿ îñòîâíîãî äåðåâà.Îïòèìàëüíûå âûáîðûÀëãîðèòì èçáðàíèÿ ëèäåðà íà äåðåâå ðåøàåò çàäà÷ó î âûáîðàõíà äðåâåñíûõ ñåòÿõ ñ èñïîëüçîâàíèåì O(N) îáìåíîâñîîáùåíèÿìè.Èç ýòîé òåîðåìû ñëåäóåò, ÷òî CE ≤ CT + O(N) .Åñëè â íàøåì ðàñïîðÿæåíèè åñòü ëèäåð, òî îñòîâíîå äåðåâîìîæíî ïîñòðîèòü ñ èñïîëüçîâàíèåì 2|E | îáìåíîâ ñîîáùåíèÿìèïðè ïîìîùè öåíòðàëèçîâàííîãî àëãîðèòìà îáõîäà ñåòè.Ïîýòîìó ñïðàâåäëèâî íåðàâåíñòâî CT ≤ CE + 2|E | .Òàêèì îáðàçîì, äëÿ îïòèìàëüíîãî âûáîðà ëèäåðà íåîáõîäèìîè äîñòàòî÷íî óìåòü îïòèìàëüíî ñòðîèòü îñòîâíîå äåðåâî.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS) ñòðîèò îñòîâíîåäåðåâî ñ èñïîëüçîâàíèåì 2|E | + 5N log N îáìåíîâ ñîîáùåíèÿìè.Àëãîðèòì ÃàëëàäæåðàÕàìáëåòàÑïèðû (GHS)Àëãîðèòì GHS îïèðàåòñÿ íà ñëåäóþùèå äîïóùåíèÿ.1.

Êàæäîìó ðåáðó ïðèïèñàí óíèêàëüíûé âåñ ω(e) . Âñå âåñàðåáåð ëèíåéíî óïîðÿäî÷åíû.2. Âñå óçëû ïðåáûâàþò ïåðâîíà÷àëüíî â ñîñòîÿíèèîöåïåíåíèÿ è ïðîáóæäàþòñÿ ïåðåä íà÷àëîì âûïîëíåíèÿàëãîðèòìà.Íåêîòîðûå óçëû ïðîáóæäàþòñÿ ñàìîïðîèçâîëüíî, äðóãèåìîãóò ïîëó÷èòü ñîîáùåíèå ïî õîäó ðàáîòû àëãîðèòìà, åùåïðåáûâàÿ â îöåïåíåíèè.Ïðè ýòîì óçåë, ïîëó÷èâøèé ñîîáùåíèå, âíà÷àëå âûïîëíÿåòïðîöåäóðó ëîêàëüíîé èíèöèàëèçàöèè, à çàòåì ïðèñòóïàåò êîáðàáîòêå ýòîãî ñîîáùåíèÿ.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÐàññìîòðèì âçâåøåííûé ãðàô G = (V , E ) , è äëÿ îáîçíà÷åíèÿâåñà ðåáðà e áóäåì èñïîëüçîâàòü çàïèñü ω(e) .Ìû áóäåì ïîëàãàòü, ÷òî êàæäîå ðåáðî èìååò óíèêàëüíûé âåñ.Âåñ îñòîâíîãî äåðåâà T â ãðàôå G ïîëàãàåòñÿ ðàâíûì ñóììåâåñîâ âñåõ N − 1 ðåáåð, âõîäÿùèõ â ñîñòàâ T .Ïðè ýòîì T íàçûâàåòñÿ ìèíèìàëüíûì îñòîâíûì äåðåâîì , èëèñîêðàùåííî MST, åñëè íè îäíî îñòîâíîå äåðåâî íå èìååò âåñìåíüøèé, ÷åì T .Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÓòâåðæäåíèå 9.1.Åñëè âñå âåñà ðåáåð ïîïàðíî ðàçëè÷íû, òî ñóùåñòâóåò òîëüêîîäíî MST.Äîêàçàòåëüñòâî.Äîïóñòèì, ÷òî åñòü äâà MST T1 è T2 , ïðè÷åì T1 6= T2 .Ðàññìîòðèì ðåáðî e íàèìåíüøåãî âåñà, êîòîðîå ñîäåðæèòñÿ âîäíîì èç ýòèõ äåðåâüåâ, íî íå ñîäåðæèòñÿ â äðóãîì.Ïðåäïîëîæèì, ÷òî e ∈ T1 .

Òîãäà T2 ∪ {e} ñîäåðæèò öèêë, è,ïîñêîëüêó â äåðåâå T1 íåò öèêëîâ, õîòÿ áû îäíî ðåáðî ýòîãîöèêëà, ñêàæåì, ðåáðî e 0 , íå ñîäåðæèòñÿ â T1 . Ñîãëàñíîâûáîðó ðåáðà e , ñïðàâåäëèâî íåðàâåíñòâî ω(e) < ω(e 0 ) .Íî òîãäà äåðåâî T2 ∪ {e} \ {e 0 } èìååò âåñ ìåíüøèé, ÷åì T2 ,âîïðåêè òîìó, ÷òî T2 ÿâëÿåòñÿ MST.Ìèíèìàëüíûå îñòîâíûå äåðåâüÿÔðàãìåíò ïðîèçâîëüíîå ïîääåðåâî MST.

Ðåáðî e íàçûâàåòñÿèñõîäÿùèì ðåáðîì ôðàãìåíòà F , åñëè îäèí èç êîíöîâ eïðèíàäëåæèò F , à äðóãîé íåò.Óòâåðæäåíèå 9.2.Åñëè F ÿâëÿåòñÿ ôðàãìåíòîì, è e ðåáðî íàèìåíüøåãî âåñà,èñõîäÿùåå èç F , òî F ∪ {e} òàêæå ÿâëÿåòñÿ ôðàãìåíòîì.Äîêàçàòåëüñòâî.ÑÀÌÎÑÒÎßÒÅËÜÍÎ (ðóêîâîäñòâóÿñü äîêàçàòåëüñòâîìïðåäûäóùåãî óòâåðæäåíèÿ).Àëãîðèòìû íà÷èíàþò ðàáîòó, ðàñïîëàãàÿ ôðàãìåíòàìè,ñîñòîÿùèìè èç åäèíñòâåííîãî óçëà, è ïîñëåäîâàòåëüíîíàðàùèâàþò ôðàãìåíòû, äî òåõ ïîð ïîêà íå áóäåò çàâåðøåíîïîñòðîåíèå MST.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÂñÿêîå âû÷èñëåíèå àëãîðèòìà GHS ñêëàäûâàåòñÿ èçñëåäóþùèõ øàãîâ.1. Ôîðìèðóåòñÿ òàêîå ñåìåéñòâî ôðàãìåíòîâ, ÷òîîáúåäèíåíèå èõ ñîäåðæèò âñå óçëû ñåòè.2. Ïåðâîíà÷àëüíî ýòî ñåìåéñòâî ñîñòîèò èç âñåõ óçëîâ ñåòè,êàæäûé èç êîòîðûõ ðàññìàòðèâàåòñÿ êàê ãðàô ñ îäíèìóçëîì.3.

Óçëû âñÿêîãî ôðàãìåíòà âñòóïàþò âî âçàèìîäåéñòâèå ñöåëüþ âûÿâëåíèÿ èñõîäÿùåãî èç ôðàãìåíòà ðåáðà ñíàèìåíüøèì âåñîì.4. Êàê òîëüêî áóäåò îïðåäåëåíî èñõîäÿùåå èç ôðàãìåíòàðåáðî ñ íàèìåíüøèì âåñîì, äàííûé ôðàãìåíò ñîåäèíÿåòñÿñ äðóãèì ôðàãìåíòîì ïóòåì äîáàâëåíèÿ ýòîãî èñõîäÿùåãîðåáðà, êîòîðîå ñòðîèòñÿ â ðåçóëüòàòå âçàèìîäåéñòâèÿ ýòèõäâóõ ôðàãìåíòîâ.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÄëÿ ýôôåêòèâíîé ðåàëèçàöèè ýòèõ øàãîâ íóæíû.1. Èìÿ ôðàãìåíòà.×òîáû îïðåäåëèòü èñõîäÿùåå ðåáðî íàèìåíüøåãî âåñà,íåîáõîäèìî ñóìåòü ïðîâåðèòü, âûâîäèò ëè íåêîòîðîå ðåáðî çàïðåäåëû ôðàãìåíòà èëè îíî âåäåò â óçåë òîãî æå ñàìîãîôðàãìåíòà.

Äëÿ ýòîãî êàæäûé ôðàãìåíò áóäåò íàäåëåíèìåíåì, êîòîðîå áóäåò èçâåñòíî âñåì ïðîöåññàì, âõîäÿùèì âýòîò ôðàãìåíò. Ïðîöåññû áóäóò ïðîâåðÿòü, ÿâëÿåòñÿ ëè ðåáðîâíóòðåííèì èëè âíåøíèì ðåáðîì, ñðàâíåíèâàÿ èìåíàôðàãìåíòîâ, ê êîòîðûì îíè îòíîñÿòñÿ.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHS2. Ñîåäèíåíèå ñòàðøåãî è ìëàäøåãî ôðàãìåíòîâ.Êîãäà äâà ôðàãìåíòà ñîåäèíÿþòñÿ, â ïðîöåññàõ õîòÿ áû îäíîãîèç ýòèõ ôðàãìåíòîâ ïðîèñõîäèò ïåðåìåíà èìåíè ôðàãìåíòà;äëÿ ýòîãî òðåáóåòñÿ, ÷òîáû èçìåíåíèå èìåíè ïðîèçîøëî âêàæäîé òî÷êå õîòÿ áû îäíîãî èç óêàçàííûõ ôðàãìåíòîâ. ×òîáûîñóùåñòâèòü ýòî èçìåíåíèå ýôôåêòèâíî, â îñíîâó ñòðàòåãèèñîåäèíåíèÿ ôðàãìåíòîâ ïîëîæåí ñëåäóþùèé ïðèíöèï:ìëàäøèé ôðàãìåíò ïðèñîåäèíÿåòñÿ ê ñòàðøåìó ôðàãìåíòó èïðèíèìàåò èìÿ ñòàðøåãî ôðàãìåíòà.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHS3.

Ðàíãè ôðàãìåíòîâ.Êàæäîìó ôðàãìåíòó ñîïîñòàâëÿåòñÿ ðàíã , êîòîðûéïåðâîíà÷àëüíî ïîëàãàåòñÿ ðàâíûì 0 äëÿ ëþáîãî ôðàãìåíòà,ñîñòîÿùåãî èç îäíîãî óçëà.Ôðàãìåíò F1 ìîæåò ñîåäèíèòüñÿ ñ ôðàãìåíòîì F2 áîëååâûñîêîãî ðàíãà, ïîñëå ÷åãî íîâûé ôðàãìåíò F1 ∪ F2 áóäåòèìåòü òàêîé æå ðàíã, êàê è ôðàãìåíò F2 , è óíàñëåäóåò èìÿôðàãìåíòà F2 .Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÔðàãìåíò F2'$Èìÿ: name2ðàíã: rank2piÔðàãìåíò F1'$pj&%Èìÿ: name1&%rank2 > rank1ðàíã: rank1Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÔðàãìåíò F2Ôðàãìåíò F2'$Èìÿ: name2ðàíã: rank2pihmessagei-&%'$pjÈìÿ: name2&%rank2 > rank1ðàíã: rank2Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHS3.

Ðàíãè ôðàãìåíòîâ.Ïðè ñîåäèíåíèå äâóõ ôðàãìåíòîâ îäíîãî è òîãî æå ðàíãà íîâûéôðàãìåíò áóäåò íîñèòü íîâîå èìÿ è åãî ðàíã áóäåò íà åäèíèöóïðåâîñõîäèòü ðàíã ñîåäèíåííûõ ôðàãìåíòîâ. Èìåíåìîáðàçîâàâøåãîñÿ ôðàãìåíòà áóäåò âåñ òîãî ðåáðà, êîòîðîåñîåäèíèëî äâà èñõîäíûõ ôðàãìåíòà; óêàçàííîå ðåáðî íàçîâåìñòåðæíåì íîâîãî ôðàãìåíòà. Òå äâà óçëà, êîòîðûå ñîåäèíåíûðåáðîì-ñòåðæíåì, áóäóò íàçûâàòüñÿ ñòåðæíåâûìè óçëàìè .Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÔðàãìåíò F2Èìÿ: name2ðàíã: rank'$piÔðàãìåíò F1'$pj&%Èìÿ: name1&%îäèíàêîâûé ðàíãðàíã: rankÃëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÔðàãìåíò FÔðàãìåíò F'$Èìÿ: ωijpi'$hmessage1 i-pjÈìÿ: ωijhmessage2 i&%&%ðàíã: rank + 1ðàíã: rank + 1îäèíàêîâûé ðàíãÃëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÓòâåðæäåíèå 9.3.Åñëè ñîáëþäàòü óêàçàííûå âûøå ïðàâèëà ñîåäèíåíèÿôðàãìåíòîâ, òî ñóììàðíî âî âñåõ ïðîöåññàõ ïåðåìåíà èìåíèèëè ðàíãà ñëó÷èòñÿ íå áîëåå N log N ðàç.Äîêàçàòåëüñòâî.Ðàíã âñÿêîãî ïðîöåññà íå ïîíèæàåòñÿ, è ëèøü â òîì ñëó÷àå,êîãäà îí ïîâûøàåòñÿ, ïðîöåññ âûíóæäåí ïåðåìåíèòü èìÿñâîåãî ôðàãìåíòà.Èíäóêöèåé ïî L ìîæíî óáåäèòüñÿ, ÷òî êàæäûé ôðàãìåíò ðàíãàL ñîäåðæèò íå ìåíåå 2L ïðîöåññîâ, è ïîýòîìó ìàêñèìàëüíîâîçìîæíûé ðàíã ðàâåí log N .Îòñþäà ñëåäóåò, ÷òî â êàæäîì îòäåëüíîì ïðîöåññå ðàíãñîäåðæàùåãî åãî ôðàãìåíòà ïîâûøàåòñÿ íå áîëåå log N ðàç.Çíà÷èò, îáùåå ÷èñëî ïåðåìåí èìåíè è ðàíãà ôðàãìåíòàîãðàíè÷åíî âåëè÷èíîé N log N .Còðàòåãèÿ ñîåäèíåíèÿÏóñòü ôðàãìåíò F = (FN, L) èìååò èìÿ FN è ðàíã L , è eF èñõîäÿùåå èç F ðåáðî íàèìåíüøåãî âåñà.Ïðàâèëî A.Ïðàâèëî B.Ïðàâèëî C.Åñëè eF âåäåò â ôðàãìåíò F 0 = (FN 0 , L0 ) , äëÿêîòîðîãî L < L0 , òî F ïðèñîåäèíÿåòñÿ ê F 0 , èîáðàçîâàâøèéñÿ íîâûé ôðàãìåíò ñîõðàíÿåò èìÿFN 0 è ðàíã L0 .Åñëè eF âåäåò â ôðàãìåíò F 0 = (FN 0 , L0 ) , äëÿêîòîðîãî L = L0 è eF 0 = eF , òî ýòè ôðàãìåíòàñîåäèíÿþòñÿ è îáðàçóþò îäèí íîâûé ôðàãìåíò,êîòîðûé áóäåò íîñèòü èìÿ ω(eF ) è èìåòü ðàíãL+1 . îñòàëüíûõ ñëó÷àÿõ (êîãäà L > L0 èëè L = L0 èeF 0 6= eF ) ôðàãìåíò F äîëæåí îæèäàòü, êîãäàîòêðîåòñÿ âîçìîæíîñòü ïðèìåíåíèÿ ïðàâèëà Aèëè B.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.Istatep ðåæèì ðàáîòû ïðîöåññà {sleep, find, found};Istachp [q] ñòàòóñ êàíàëà ñâÿçè {basic, branch, reject};Inamep èìÿ ôðàãìåíòà;Ibestwtp íàèìåíüøèé âåñ èñõîäÿùåãî ðåáðà;Ilevelp ðàíã ïðîöåññà;Ifatherp êàíàë, âåäóùèé â ñòåðæíåâîé óçåë ôðàãìåíòà;Itestchp , bestchp ïåðñïåêòèâíûå êàíàëû ñâÿçè ñ ñîñåäÿìè;Irec ñ÷åò÷èê.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhconnect, leveli ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èç ôðàãìåíòà, ñóêàçàíèåì ðàíãà ýòîãî ôðàãìåíòà;hinitiate, level, name, statei ñîîáùåíèå, êîòîðîåîòïðàâëÿåòñÿ ïî ðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èçôðàãìåíòà,ïðè âûïîëíåíèè ïðàâèëà À ïðèñîåäèíåíèÿ ôðàãìåíòàìåíüøåãî ðàíãà, à òàêæåïðè âûïîëíåíèè ïðàâèëà B îáúåäèíåíèÿ äâóõôðàãìåíòîâ îäèíàêîâîãî ðàíãà;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIIhtest, level, namei ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî¾ñâåæåìó¿ ðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èç óçëà, ñóêàçàíèåì èìåíè è ðàíãà ôðàãìåíòà, êîòîðîìóïðèíàäëåæèò óçåë;hrejecti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî ðåáðó âòîì ñëó÷àå, åñëè ýòî ðåáðî ñîåäèíÿåò äâà óçëà,ïðèíàäëåæàùèå îäíîìó è òîìó æå ôðàãìåíòó;haccepti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî ðåáðó âòîì ñëó÷àå, åñëè ýòî ðåáðî ñîåäèíÿåò äâà óçëà,ïðèíàäëåæàùèå ðàçíûì ôðàãìåíòàì;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhreport, bestwti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîíàïðàâëåíèþ ê ñòåðæíåâîìó óçëó ñ óêàçàíèåìíàèìåíüøåãî âåñà ¾ñâåæåãî¿ ðåáðà, èñõîäÿùåãî èç óçëà;hchangerooti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîðåáðàì ïðèñîåäèíÿåìîãî ôðàãìåíòà è óêàçûâàåò òîíàïðàâëåíèå, â êîòîðîì áóäåò ðàñïîëàãàòüñÿ ñòåðæíåâîéóçåë;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(1) Ïåðâûì äåéñòâèåì êàæäîãî ïðîöåññàÿâëÿåòñÿ èíèöèàëèçàöèÿ äàííîãî àëãîðèòìà:begin ïóñòü pq ýòî êàíàë ñâÿçè ïðîöåññà p ,èìåþùèé íàèìåíüøèé âåñ ;stachp [q] := branch ; level p := 0 ;statep := found ; recp := 0 ;send hconnect, 0i to qendÊàæäûé ïðîöåññ íà÷èíàåò ðàáîòó ñ òîãî, ÷òîïðèñâèâàåò ñåáå ñàìûé íèçêèé ðàíã,íàõîäèò èñõîäÿùåå ðåáðî íàèìåíüøåãî âåñà, èîáúÿâëÿåò î ñâîåé ãîòîâíîñòè ïðèñîåäèíèòüñÿ ê ñîñåäíåìóôðàãìåíòó.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > levelpthen (* Ïðàâèëî C *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååendelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qÏîñëå ïðåäëîæåíèÿ îá îáúåäèíåíèè ôðàãìåíòîâ òîò óçåë,êîòîðûé ïîëó÷èë ýòî ïðåäëîæåíèå, ïðîâåðÿåò ðàíã ñîñåäíåãîôðàãìåíòà,...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > level pthen (* Ïðàâèëî C *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååendelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qè åñëè ðàíã ñîñåäíåãî ôðàãìåíòà ìåíüøå ðàíãà òîãîôðàãìåíòà, êîòîðîìó ïðèíàäëåæèò óçåë p , òî óçåë pîòïðàâëÿåò ñîñåäíåìó ôðàãìåíòó ïðèêàç ïðèñîåäèíèòüñÿ ¾âêà÷åñòâå ïîä÷èíåííîãî¿, ïðèíÿâ èìÿ è ðàíã ñòàðøåãîôðàãìåíòà,...Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > level pthen (* Ïðàâèëî C *)endîáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qà â ïðîòèâíîì ñëó÷àå ïðîöåññ p ïðîâåðÿåò, íå áûëî ëè ðåáðîpq óæå ¾îïðîáîâàíî¿ ïðîöåññîì p ðàíåå.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > level pthen (* Ïðàâèëî C *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååendelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qÅñëè ýòî ðåáðî íå áûëî åùå ¾îïðîáîâàíî¿ ïðîöåññîì p , òîîáðàáîòêà ïðåäëîæåíèÿ îáúåäèíèòüñÿ îòêëàäûâàåòñÿ äî òåõïîð, ïîêà ïðîöåññ p íå ïðèñòóïèò ê îöåíêå ðåáðà pq ,....Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHS(2) Ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hconnect, Li îò q :begin if L < level p then (* Ñîåäèíèòü ïî ïðàâèëó A *)begin stachp [q] := branch ;send hinitiate, level p , name p , statep i to qendelse if stachp [q] = basic or L > level pthen (* Ïðàâèëî C *)îáðàáîòàòü ýòî ñîîáùåíèå ïîçäíååendelse (* Ïðàâèëî B *)send hinitiate, level p + 1, ω(pq), findi to qà èíà÷å (ò.å.