Лекция 10. Задача избрания лидера. Нижние оценки. Оптимальные выборы. Алгоритм GHS и Корача-Каттена-Морана, страница 2

Ôîðìèðóåòñÿ òàêîå ñåìåéñòâî ôðàãìåíòîâ, ÷òîîáúåäèíåíèå èõ ñîäåðæèò âñå óçëû ñåòè.2. Ïåðâîíà÷àëüíî ýòî ñåìåéñòâî ñîñòîèò èç âñåõ óçëîâ ñåòè,êàæäûé èç êîòîðûõ ðàññìàòðèâàåòñÿ êàê ãðàô ñ îäíèìóçëîì.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÂñÿêîå âû÷èñëåíèå àëãîðèòìà GHS ñêëàäûâàåòñÿ èçñëåäóþùèõ øàãîâ.1. Ôîðìèðóåòñÿ òàêîå ñåìåéñòâî ôðàãìåíòîâ, ÷òîîáúåäèíåíèå èõ ñîäåðæèò âñå óçëû ñåòè.2. Ïåðâîíà÷àëüíî ýòî ñåìåéñòâî ñîñòîèò èç âñåõ óçëîâ ñåòè,êàæäûé èç êîòîðûõ ðàññìàòðèâàåòñÿ êàê ãðàô ñ îäíèìóçëîì.3. Óçëû âñÿêîãî ôðàãìåíòà âñòóïàþò âî âçàèìîäåéñòâèå ñöåëüþ âûÿâëåíèÿ èñõîäÿùåãî èç ôðàãìåíòà ðåáðà ñíàèìåíüøèì âåñîì.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÂñÿêîå âû÷èñëåíèå àëãîðèòìà GHS ñêëàäûâàåòñÿ èçñëåäóþùèõ øàãîâ.1.

Ôîðìèðóåòñÿ òàêîå ñåìåéñòâî ôðàãìåíòîâ, ÷òîîáúåäèíåíèå èõ ñîäåðæèò âñå óçëû ñåòè.2. Ïåðâîíà÷àëüíî ýòî ñåìåéñòâî ñîñòîèò èç âñåõ óçëîâ ñåòè,êàæäûé èç êîòîðûõ ðàññìàòðèâàåòñÿ êàê ãðàô ñ îäíèìóçëîì.3. Óçëû âñÿêîãî ôðàãìåíòà âñòóïàþò âî âçàèìîäåéñòâèå ñöåëüþ âûÿâëåíèÿ èñõîäÿùåãî èç ôðàãìåíòà ðåáðà ñíàèìåíüøèì âåñîì.4. Êàê òîëüêî áóäåò îïðåäåëåíî èñõîäÿùåå èç ôðàãìåíòàðåáðî ñ íàèìåíüøèì âåñîì, äàííûé ôðàãìåíò ñîåäèíÿåòñÿñ äðóãèì ôðàãìåíòîì ïóòåì äîáàâëåíèÿ ýòîãî èñõîäÿùåãîðåáðà, êîòîðîå ñòðîèòñÿ â ðåçóëüòàòå âçàèìîäåéñòâèÿ ýòèõäâóõ ôðàãìåíòîâ.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÄëÿ ýôôåêòèâíîé ðåàëèçàöèè ýòèõ øàãîâ íóæíû.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà 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 ðàç.Ãëîáàëüíîå îïèñàíèå àëãîðèòìà GHSÓòâåðæäåíèå 9.3.Åñëè ñîáëþäàòü óêàçàííûå âûøå ïðàâèëà ñîåäèíåíèÿôðàãìåíòîâ, òî ñóììàðíî âî âñåõ ïðîöåññàõ ïåðåìåíà èìåíèèëè ðàíãà ñëó÷èòñÿ íå áîëåå N log N ðàç.Äîêàçàòåëüñòâî.Ðàíã âñÿêîãî ïðîöåññà íå ïîíèæàåòñÿ, è ëèøü â òîì ñëó÷àå,êîãäà îí ïîâûøàåòñÿ, ïðîöåññ âûíóæäåí ïåðåìåíèòü èìÿñâîåãî ôðàãìåíòà.

Ôðàãìåíò ðàíãà L ñîäåðæèò íå ìåíåå 2Lïðîöåññîâ, è ïîýòîìó ìàêñèìàëüíî âîçìîæíûé ðàíã ðàâåílog N . Îòñþäà ñëåäóåò, ÷òî â êàæäîì îòäåëüíîì ïðîöåññå ðàíãñîäåðæàùåãî åãî ôðàãìåíòà ïîâûøàåòñÿ íå áîëåå log N ðàç.Çíà÷èò, îáùåå ÷èñëî ïåðåìåí èìåíè è ðàíãà ôðàãìåíòàîãðàíè÷åíî âåëè÷èíîé N log N .Còðàòåãèÿ ñîåäèíåíèÿÏóñòü ôðàãìåíò F = (FN, L) èìååò èìÿ FN è ðàíã L , è eF èñõîäÿùåå èç F ðåáðî íàèìåíüøåãî âåñà.Còðàòåãèÿ ñîåäèíåíèÿÏóñòü ôðàãìåíò F = (FN, L) èìååò èìÿ FN è ðàíã L , è eF èñõîäÿùåå èç F ðåáðî íàèìåíüøåãî âåñà.Ïðàâèëî A.Åñëè eF âåäåò â ôðàãìåíò F 0 = (FN 0 , L0 ) , äëÿêîòîðîãî L < L0 , òî F ïðèñîåäèíÿåòñÿ ê F 0 , èîáðàçîâàâøèéñÿ íîâûé ôðàãìåíò ñîõðàíÿåò èìÿFN 0 è ðàíã L0 .Còðàòåãèÿ ñîåäèíåíèÿÏóñòü ôðàãìåíò F = (FN, L) èìååò èìÿ FN è ðàíã L , è eF èñõîäÿùåå èç F ðåáðî íàèìåíüøåãî âåñà.Ïðàâèëî A.Ïðàâèëî B.Åñëè 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 .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Ïåðåìåííûå.IstatepIstachp [q]InamepIbestwtpIlevelpIfatherpItestchp , bestchpIrecÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.Istatep ðåæèì ðàáîòû ïðîöåññà {sleep, find, found};Istachp [q]InamepIbestwtpIlevelpIfatherpItestchp , bestchpIrecÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.IstatepIstachp [q] ñòàòóñ êàíàëà ñâÿçè {basic, branch, reject};InamepIbestwtpIlevelpIfatherpItestchp , bestchpIrecÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.IstatepIstachp [q]Inamep èìÿ ôðàãìåíòà;IbestwtpIlevelpIfatherpItestchp , bestchpIrecÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.IstatepIstachp [q]InamepIbestwtp íàèìåíüøèé âåñ èñõîäÿùåãî ðåáðà;IlevelpIfatherpItestchp , bestchpIrecÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.IstatepIstachp [q]InamepIbestwtpIlevelp ðàíã ïðîöåññà;IfatherpItestchp , bestchpIrecÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.IstatepIstachp [q]InamepIbestwtpIlevelpIfatherp êàíàë, âåäóùèé â ñòåðæíåâîé óçåë ôðàãìåíòà;Itestchp , bestchpIrecÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.IstatepIstachp [q]InamepIbestwtpIlevelpIfatherpItestchp , bestchp ïåðñïåêòèâíûå êàíàëû ñâÿçè ñ ñîñåäÿìè;IrecÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.IstatepIstachp [q]InamepIbestwtpIlevelpIfatherpItestchp , bestchpIrec ñ÷åò÷èê.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÏåðåìåííûå.Istatep ðåæèì ðàáîòû ïðîöåññà {sleep, find, found};Istachp [q] ñòàòóñ êàíàëà ñâÿçè {basic, branch, reject};Inamep èìÿ ôðàãìåíòà;Ibestwtp íàèìåíüøèé âåñ èñõîäÿùåãî ðåáðà;Ilevelp ðàíã ïðîöåññà;Ifatherp êàíàë, âåäóùèé â ñòåðæíåâîé óçåë ôðàãìåíòà;Itestchp , bestchp ïåðñïåêòèâíûå êàíàëû ñâÿçè ñ ñîñåäÿìè;Irec ñ÷åò÷èê.Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.Ihconnect, leveliIhinitiate, level, name, stateiÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhconnect, leveli ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èç ôðàãìåíòà, ñóêàçàíèåì ðàíãà ýòîãî ôðàãìåíòà;hinitiate, level, name, stateiÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhconnect, levelihinitiate, level, name, statei ñîîáùåíèå, êîòîðîåîòïðàâëÿåòñÿ ïî ðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èçôðàãìåíòà,ïðè âûïîëíåíèè ïðàâèëà À ïðèñîåäèíåíèÿ ôðàãìåíòàìåíüøåãî ðàíãà, à òàêæåïðè âûïîëíåíèè ïðàâèëà B îáúåäèíåíèÿ äâóõôðàãìåíòîâ îäèíàêîâîãî ðàíãà;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhconnect, leveli ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èç ôðàãìåíòà, ñóêàçàíèåì ðàíãà ýòîãî ôðàãìåíòà;hinitiate, level, name, statei ñîîáùåíèå, êîòîðîåîòïðàâëÿåòñÿ ïî ðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èçôðàãìåíòà,ïðè âûïîëíåíèè ïðàâèëà À ïðèñîåäèíåíèÿ ôðàãìåíòàìåíüøåãî ðàíãà, à òàêæåïðè âûïîëíåíèè ïðàâèëà B îáúåäèíåíèÿ äâóõôðàãìåíòîâ îäèíàêîâîãî ðàíãà;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.Ihtest, level, nameiIhrejectiIhacceptiÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.Ihtest, level, namei ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî¾ñâåæåìó¿ ðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èç óçëà, ñóêàçàíèåì èìåíè è ðàíãà ôðàãìåíòà, êîòîðîìóïðèíàäëåæèò óçåë;IhrejectiIhacceptiÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIIhtest, level, nameihrejecti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî ðåáðó âòîì ñëó÷àå, åñëè ýòî ðåáðî ñîåäèíÿåò äâà óçëà,ïðèíàäëåæàùèå îäíîìó è òîìó æå ôðàãìåíòó;hacceptiÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.Ihtest, level, nameiIhrejectiIhaccepti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî ðåáðó âòîì ñëó÷àå, åñëè ýòî ðåáðî ñîåäèíÿåò äâà óçëà,ïðèíàäëåæàùèå ðàçíûì ôðàãìåíòàì;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIIhtest, level, namei ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî¾ñâåæåìó¿ ðåáðó íàèìåíüøåãî âåñà, èñõîäÿùåãî èç óçëà, ñóêàçàíèåì èìåíè è ðàíãà ôðàãìåíòà, êîòîðîìóïðèíàäëåæèò óçåë;hrejecti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî ðåáðó âòîì ñëó÷àå, åñëè ýòî ðåáðî ñîåäèíÿåò äâà óçëà,ïðèíàäëåæàùèå îäíîìó è òîìó æå ôðàãìåíòó;haccepti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïî ðåáðó âòîì ñëó÷àå, åñëè ýòî ðåáðî ñîåäèíÿåò äâà óçëà,ïðèíàäëåæàùèå ðàçíûì ôðàãìåíòàì;Ïîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.Ihreport, bestwtiIhchangerootiÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhreport, bestwti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîíàïðàâëåíèþ ê ñòåðæíåâîìó óçëó ñ óêàçàíèåìíàèìåíüøåãî âåñà ¾ñâåæåãî¿ ðåáðà, èñõîäÿùåãî èç óçëà;hchangerootiÏîäðîáíîå îïèñàíèå àëãîðèòìà GHSÑîîáùåíèÿ.IIhreport, bestwtihchangerooti ñîîáùåíèå, êîòîðîå îòïðàâëÿåòñÿ ïîðåáðàì ïðèñîåäèíÿåìîãî ôðàãìåíòà è óêàçûâàåò òîíàïðàâëåíèå, â êîòîðîì áóäåò ðàñïîëàãàòüñÿ ñòåðæíåâîéóçåë;Ïîäðîáíîå îïèñàíèå àëãîðèòìà 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à èíà÷å (ò.å.