7 Волновые алгоритмы - определение, основные свойства, область применения. Древесный алгоритм. Алгоритм эха

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 7.Âîëíîâûå àëãîðèòìû: îïðåäåëåíèÿ,îñíîâíûå ñâîéñòâà, îáëàñòü ïðèìåíåíèÿ.Äðåâåñíûé àëãîðèòì.Àëãîðèòì ýõà.Çà÷åì íóæíû âîëíîâûå àëãîðèòìûÏðè ïðîåêòèðîâàíèè ðàñïðåäåëåííûõ àëãîðèòìîâ äëÿ ðàçíûõïðèëîæåíèé íåêîòîðûå îáùèå ïðîáëåìû, êîòîðûå íóæíî óìåòüðåøàòü êàê ïðîìåæóòî÷íûå çàäà÷è. Ê íèì îòíîñÿòñÿIøèðîêîâåùàòåëüíîå ðàñïðîñòðàíåíèå èíôîðìàöèÿ(íàïðèìåð, ñîîáùåíèÿ î íà÷àëå èëè çàâåðøåíèèâû÷èñëåíèÿ),Ióñòàíîâëåíèå ãëîáàëüíîé ñèíõðîíèçàöèè ìåæäóïðîöåññàìè,Içàïóñê âûïîëíåíèÿ íåêîòîðîãî äåéñòâèÿ â êàæäîìïðîöåññå,Iâû÷èñëåíèå ôóíêöèè ïðè óñëîâèè, ÷òî êàæäûé èçïðîöåññîâ ñîäåðæèò òîëüêî ÷àñòü âõîäíûõ äàííûõ,Iè ìíîãèå äðóãèå.Ýòè çàäà÷è ìîæíî ðåøàòü ïóòåì îáìåíà ñîîáùåíèÿìè ñîãëàñíîíåêîòîðîé ïðåäïèñàííîé ñõåìå, êîòîðàÿ çàâèñèò îò òîïîëîãèèñåòè è ïîçâîëÿåò çàäåéñòâîâàòü âñå ïðîöåññû.Ñîãëàøåíèå î ñåòåâîé ìîäåëèÄàëåå â ýòîé ãëàâå ìû áóäåì ïîëàãàòü, ÷òî ñåòüIèìååò ôèêñèðîâàííóþ òîïîëîãèþ (íèêàêèõ èçìåíåíèéòîïîëîãèè íå ïðîèñõîäèò);Iÿâëÿåòñÿ íåîðèåíòèðîâàííîé (ïî êàæäîìó êàíàëóñîîáùåíèÿ ìîãóò ïåðåäàâàòüñÿ â îáîèõ íàïðàâëåíèÿõ);Iÿâëÿåòñÿ ñâÿçíîé (ìåæäó ëþáûìè äâóìÿ ïðîöåññàìèïðîëåãàåò ïóòü),Iÿâëÿåòñÿ àñèíõðîííîé,Iíå èìååò äîñòóïà ê ïîêàçàíèÿì âåùåñòâåííûõ ÷àñîâãëîáàëüíîãî âðåìåíè.Îáîçíà÷åíèÿIP ìíîæåñòâî âñåõ ïðîöåññîâ ñèñòåìû;IE ìíîæåñòâî âñåõ êàíàëîâ ñèñòåìû;IC âû÷èñëåíèå ñèñòåìû;I îòíîøåíèå ïðè÷èííî-ñëåäñòâåííîãî ïðåäøåñòâîâàíèÿ;ICp ìíîæåñòâî ñîáûòèé ïðîöåññà p â âû÷èñëåíèè C ;I|C | êîëè÷åñòâî ñîáûòèé â âû÷èñëåíèè C .Ïðåäïîëàãàåòñÿ, ÷òî ñóùåñòâóþò âíóòðåííèå ñîáûòèÿñïåöèàëüíîãî òèïà, êîòîðûå íàçûâàþòñÿ ñîáûòèÿìè ðåøåíèÿ ;òàêèå ñîáûòèÿ ïðîñòî ïðåäñòàâëåíû îïåðàòîðîì decide . âîëíîâîì àëãîðèòìå ïðîâîäèòñÿ îáìåí êîíå÷íûì ÷èñëîìñîîáùåíèé, à çàòåì ïðèíèìàåòñÿ ðåøåíèå, êîòîðîå äîëæíîèìåòü ïðè÷èííî-ñëåäñòâåííóþ çàâèñèìîñòü õîòÿ áû îò îäíîãîñîáûòèÿ â êàæäîì èç ïðîöåññîâ ñèñòåìû.Îïðåäåëåíèå âîëíîâîãî àëãîðèòìàÂîëíîâûì àëãîðèòìîì íàçûâàåòñÿ ðàñïðåäåëåííûé àëãîðèòì,êîòîðûé óäîâëåòâîðÿåò ñëåäóþùèì òðåì òðåáîâàíèÿì.1.

Çàâåðøåíèå. Êàæäîå âû÷èñëåíèå êîíå÷íî:∀C : |C | < ∞.2. Ðåøåíèå. Êàæäîå âû÷èñëåíèå ñîäåðæèò õîòÿ áû îäíîñîáûòèå ðåøåíèÿ:∀C : ∃e ∈ C : e ÿâëÿåòñÿ ñîáûòèåì ðåøåíèÿ.3. Çàâèñèìîñòü.  ëþáîì âû÷èñëåíèè âñÿêîìó ñîáûòèþðåøåíèÿ ïðåäøåñòâóåò â ïðè÷èííî-ñëåäñòâåííîìîòíîøåíèè õîòÿ áû îäíî ñîáûòèå â êàæäîì èç ïðîöåññîâ:∀C : ∀e ∈ C : (e ñîáûòèå ðåøåíèÿ ⇒ ∀q ∈ P : (∃f ∈ Cq : f e).Îïðåäåëåíèå âîëíîâîãî àëãîðèòìàÂû÷èñëåíèå âîëíîâîãî àëãîðèòìà íàçûâàåòñÿ âîëíîé .Ïðè âûïîëíåíèè âîëíîâîãî àëãîðèòìà ïðîöåññûïîäðàçäåëÿþòñÿ íà äâå ãðóïïû:1.

èíèöèàòîðû (èëè èíà÷å, ñòàðòîâûå ïðîöåññû ) çàïóñêàþòâûïîëíåíèå ñâîåãî ëîêàëüíîãî àëãîðèòìàñàìîïðîèçâîëüíî, ò. å. àëãîðèòì çàïóñêàåòñÿ ïîíåêîòîðîìó óñëîâèþ âíóòðè ïðîöåññà.2. íåèíèöèàòîðû (èëè èíà÷å, ïîñëåäîâàòåëè ) âîâëåêàþòñÿ âðàñïðåäåëåííûé àëãîðèòì, òîëüêî êîãäà ïî õîäóâû÷èñëåíèÿ ïîñòóïàåò ñîîáùåíèå, êîòîðîå çàïóñêàåòâûïîëíåíèå àëãîðèòìà ïðîöåññà.Òàêèì îáðàçîì, ïåðâîå ñîáûòèå èíèöèàòîðà ýòî âíóòðåííååñîáûòèå èëè îòïðàâëåíèå ñîîáùåíèÿ, à ïåðâîå ñîáûòèåíåèíèöèàòîðà ýòî ñîáûòèå ïðèåìà ñîîáùåíèÿ.Îïðåäåëåíèå âîëíîâîãî àëãîðèòìàÏàðàìåòðû âîëíîâûõ àëãîðèòìîâ.1.

Öåíòðàëèçàöèÿ . Àëãîðèòì íàçûâàåòñÿ öåíòðàëèçîâàííûì ,åñëè ó êàæäîãî âû÷èñëåíèÿ åñòü â òî÷íîñòè îäèíèíèöèàòîð, è äåöåíòðàëèçîâàííûì , åñëè àëãîðèòì ìîæåòáûòü çàïóùåí ñïîíòàííî íåêîòîðûì ïðîèçâîëüíûìïîäìíîæåñòâîì ïðîöåññîâ.2. Òîïîëîãèÿ . Àëãîðèòì ìîæåò áûòü ñïðîåêòèðîâàí âðàñ÷åòå íà ñïåöèàëüíóþ òîïîëîãèþ, íàïîäîáèå êîëüöà,äåðåâà, êëèêè è ò.ï.3. Ïåðâîíà÷àëüíûå ñâåäåíèÿ .

Êàæäûé ïðîöåññ ìîæåò çíàòüñâîå ñîáñòâåííîå óíèêàëüíîå èìÿ èëè èìåíà ñâîèõ ñîñåäåé;4. ×èñëî ðåøåíèé . Ðåøåíèå ïðèíèìàåò òîëüêî îäèí ïðîöåññèëè âñå ïðîöåññû.5. Ñëîæíîñòü . Ìåðîé ñëîæíîñòè ìîæåò ñëóæèòü êîëè÷åñòâîîáìåíîâ ñîîáùåíèÿìè, ÷èñëî áèòîâ èíôîðìàöèè,îòïðàâëåííûõ ïðè îáìåíå ñîîáùåíèÿìè, è âðåìÿ,çàòðà÷èâàåìîå îäíèì âû÷èñëåíèåì.Ñâîéñòâà âîëíîâûõ àëãîðèòìîâÓòâåðæäåíèå 1.Äëÿ êàæäîãî ñîáûòèÿ e ∈ C ñóùåñòâóþò òàêîé èíèöèàòîð p èòàêîå ñîáûòèå f ∈ Cp , ÷òî f e .Äîêàçàòåëüñòâî.Âûáåðåì â êà÷åñòâå f ìèíèìàëüíûé ýëåìåíò â èñòîðèèñîáûòèÿ e . Òàêîé ýëåìåíò f ñóùåñòâóåò, ïîñêîëüêó èñòîðèÿêàæäîãî ñîáûòèÿ êîíå÷íà.

Ïîêàæåì, ÷òî ïðîöåññ p , â êîòîðîìïðîèñõîäèò ñîáûòèå f , ÿâëÿåòñÿ èíèöèàòîðîì.Çàòìåòèì, ÷òî f ýòî ïåðâîå ñîáûòèå ïðîöåññà p . Ïåðâîåñîáûòèå íåèíèöèàòîðà ýòî ñîáûòèå ïðèåìà, êîòîðîìó äîëæíîïðåäøåñòâîâàòü ñîîòâåòñòâóþùåå ñîáûòèå îòïðàâëåíèÿ, ÷òîïðîòèâîðå÷èò ìèíèìàëüíîñòè f . Çíà÷èò, p èíèöèàòîð.Ñâîéñòâà âîëíîâûõ àëãîðèòìîâÏóñòü C öåíòðàëèçîâàííàÿ âîëíà ñ èíèöèàòîðîì p . Äëÿêàæäîãî íåèíèöèàòîðà q îáîçíà÷èì ñèìâîëîì fatherq òîãîñîñåäà ïðîöåññà q , îò êîòîðîãî q ïîëó÷èë ïåðâîå ñîîáùåíèå.Óòâåðæäåíèå 2.Ãðàô T = (P, ET ) , ãäå ET = {hq, r i : q 6= p ∧ r = fatherq } ,ÿâëÿåòñÿ îñòîâíûì äåðåâîì, íàïðàâëåííûì ê p .Äîêàçàòåëüñòâî.×èñëî âåðøèí â T ïðåâîñõîäèò ÷èñëî äóã íà åäèíèöó.Ïîýòîìó äîñòàòî÷íî ïîêàçàòü, ÷òî T íå ñîäåðæèò öèêëîâ.È ýòî äåéñòâèòåëüíî òàê, ïîñêîëüêó äëÿ eq , ïåðâîãî ñîáûòèÿ âq , íàëè÷èå äóãè qr ∈ ET âëå÷åò er eq , à îòíîøåíèå ÿâëÿåòñÿ ÷àñòè÷íûì ïîðÿäêîì.Ñâîéñòâà âîëíîâûõ àëãîðèòìîâÓòâåðæäåíèå 3.Ïóñòü C âîëíà è decide ∈ Cp .

Òîãäà∀q 6= p : ∃f ∈ Cq : (f decide ∧ f îòïðàâëåíèå ñîîáùåíèÿ).Äîêàçàòåëüñòâî.Òàê êàê C âîëíà, ñóùåñòâóþò òàêèå ñîáûòèÿ f ∈ Cq , ÷òîf decide . Âûáåðåì â êà÷åñòâå f ïîñëåäíåå ñîáûòèå â Cq ,ïðåäøåñòâóþùåå decide .Ïîêàæåì, ÷òî f ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ.Èç îïðåäåëåíèÿ âûòåêàåò ñóùåñòâîâàíèå òàêîé ïðè÷èííîñëåäñòâåííîé öåïî÷êè f = e0 , e1 , . . .

, ek = decide, ÷òî äëÿêàæäîãî i < k ñîáûòèÿ ei è ei+1 ÿâëÿþòñÿ ëèáîïîñëåäîâàòåëüíûìè ñîáûòèÿìè â îäíîì ïðîöåññå, ëèáî ïàðîéñîîòâåòñòâóþùèõ ñîáûòèé îòïðàâëåíèÿ-ïðèåìà ñîîáùåíèÿ.Ò.ê. f ïîñëåäíåå ñîáûòèå â ïðîöåññå q , ïðåäøåñòâóþùååñîáûòèþ decide , ñîáûòèå e1 ïðîèñõîäèò â ïðîöåññå, îòëè÷íîìîò q .

Çíà÷èò, f ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ.Ñëîæíîñòü âîëíîâûõ àëãîðèòìîâÓòâåðæäåíèå 4.Ïóñòü C òàêàÿ âîëíà ñ îäíèì èíèöèàòîðîì p âðàñïðåäåëåííîé ñèñòåìå, ñîñòîÿùåé èç N ïðîöåññîâ, ÷òî â pïðîèñõîäèò ñîáûòèå ðåøåíèÿ decide . Òîãäà â âû÷èñëåíèè Cïðîèñõîäèò îáìåí ïî êðàéíåé ìåðå N ñîîáùåíèÿìè.Äîêàçàòåëüñòâî.Ïî óòâåðæäåíèþ 1 êàæäîìó ñîáûòèþ â C ïðåäøåñòâóåòíåêîòîðîå ñîáûòèå â ïðîöåññå p . Ïîýòîìó â p ïðîèçîéäåò õîòÿáû îäíî ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ. Ïî óòâåðæäåíèþ 3ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ òàêæå ïðîèçîéäåò è â êàæäîìäðóãîì ïðîöåññå, à ýòî îçíà÷àåò, ÷òî ïðîèçîéäåò êàê ìèíèìóìN îáìåíîâ ñîîáùåíèÿìè.Ñëîæíîñòü âîëíîâûõ àëãîðèòìîâÓòâåðæäåíèå 5.Ïóñòü A âîëíîâîé àëãîðèòì äëÿ ïðîèçâîëüíîé ñåòè, âêîòîðîì íå èñïîëüçóþòñÿ ïåðâîíà÷àëüíûå ñâåäåíèÿ îáîòëè÷èòåëüíûõ ïðèçíàêàõ ñîñåäåé.

Òîãäà A â êàæäîìâû÷èñëåíèè ïðîâîäèò íå ìåíåå |E | îáìåíîâ ñîîáùåíèÿìè.Äîêàçàòåëüñòâî.Ïðåäïîëîæèì, ÷òî A èìååò âû÷èñëåíèå C , â êîòîðîìïðîâîäèòñÿ ìåíåå |E | îáìåíîâ ñîîáùåíèÿìè, ò. å. ïîíåêîòîðîìó êàíàëó xy íå ïåðåäàþòñÿ ñîîáùåíèÿ.Ðàññìîòðèì ñåòü G 0 , ïîëó÷åííóþ çà ñ÷åò äîáàâëåíèÿ îäíîéòî÷êè z â êàíàëå ìåæäó x è y .Ïîñêîëüêó òî÷êè íå èäåíòèôèöèðóþò ñâîèõ ñîñåäåé, íà÷àëüíîåñîñòîÿíèå x è y â G 0 áóäåò òåì æå ñàìûì, ÷òî è â ñåòè G . Ýòîñïðàâåäëèâî è äëÿ âñåõ îñòàëüíûõ òî÷åê G .Ñëåäîâàòåëüíî, âñå ñîáûòèÿ â C ïðîèçîéäóò â òîì æå ñàìîìïîðÿäêå íà÷èíàÿ ñ èñõîäíîé êîíôèãóðàöèè G 0 , íî òåïåðüñîáûòèþ decide íå ïðåäøåñòâóåò íèêàêîå ñîáûòèå â z . Çàäà÷à ìàðøðóòèçàöèè@@yx@@yyHH@H@HGAAAA@@yzyx@@yyHH@H@HG0Ðèñ.: Âñòàâêà ïðîöåññà â íåèñïîëüçóåìûé êàíàëÏðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: PIFÂîëíîâûå àëãîðèòìû íåîáõîäèìû äëÿ øèðîêîâåùàòåëüíîãîðàñïðîñòðàíåíèÿ èíôîðìàöèè ñ ïîäòâåðæäåíèåì î çàâåðøåíèèâûïîëíåíèÿ (øèðîêîâåùàòåëüíîé ñâÿçè Propagation ofInformation with Feedback, PIF).Ïóñòü èìååòñÿ ïîäìíîæåñòâî ïðîöåññîâ, îáëàäàþùèõíåêîòîðûì ñîîáùåíèåì M .

Íóæíî, ÷òîáû âñå ïðîöåññûïðèíÿëè M . Íåêîòîðûå âûäåëåííûå ïðîöåññû äîëæíû áûòüóâåäîìëåíû î çàâåðøåíèè øèðîêîâåùàòåëüíîé ñâÿçè; ýòîîçíà÷àåò, ÷òî â íèõ äîëæíî áûòü âûðàáîòàíî ñïåöèàëüíîåñîáûòèå notify ñ òåì óñëîâèåì, ÷òî ñîáûòèå notify ïðîèçîéäåòòîëüêî ïîñëå òîãî, êàê âñå ïðîöåññû óæå ïîëó÷àò ñîîáùåíèå M.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: PIFÓòâåðæäåíèå 6.Êàæäûé PIF-àëãîðèòì ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ïóñòü P ýòî íåêîòîðûé PIF-àëãîðèòì. Òîãäà êàæäîåâû÷èñëåíèå àëãîðèòìà P êîíå÷íî è â êàæäîì âû÷èñëåíèèïðîèñõîäèò óâåäîìëÿþùåå ñîáûòèå (notify ).Åñëè â íåêîòîðîì âû÷èñëåíèè àëãîðèòìà P ïðîèñõîäèòóâåäîìëåíèå dP , êîòîðîìó íå ïðåäøåñòâóåò íèêàêîå ñîáûòèå âïðîöåññå q , òî ïî òåîðåìå î ïåðåñòàíîâêå íåçàâèñèìûõñîáûòèé ñóùåñòâóåò òàêîå âûïîëíåíèå àëãîðèòìà P , â êîòîðîìóâåäîìëåíèå ïðîèñõîäèò, äî òîãî êàê q ïîëó÷èò êàêîå-ëèáîñîîáùåíèå, ÷òî ïðîòèâîðå÷èò íàøèì òðåáîâàíèÿì.Ýòî óòâåðæäåíèå ñïðàâåäëèâî òîëüêî äëÿ ñèñòåì ñ àñèíõðîííîéïåðåäà÷åé ñîîáùåíèé (Ïî÷åìó? ).Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: PIFÓòâåðæäåíèå 7.Êàæäûé âîëíîâîé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí âêà÷åñòâå PIF-àëãîðèòìà.Äîêàçàòåëüñòâî.Ïóñòü A âîëíîâîé àëãîðèòì.

×òîáû ïðåäñòàâèòü A êàêPIF-àëãîðèòì, ïðîöåññû, ïåðâîíà÷àëüíî õðàíÿùèå M , ñëåäóåòñ÷èòàòü èíèöèàòîðàìè. Èíôîðìàöèþ M íóæíî äîáàâèòü êêàæäîìó ñîîáùåíèþ, ïåðåäàâàåìîìó â àëãîðèòìå A .Íå-èíèöèàòîðû ïàññèâíû, äî òåõ ïîð ïîêà ñàìè îíè íå ïîëó÷àòõîòü îäíî ñîîáùåíèå, à çíà÷èò òàê æå ñòàíóò îñâåäîìëåíû î M .Ñîáûòèþ decide â âîëíå ïðåäøåñòâóåò ïî êðàéíåé ìåðå îäíîñîáûòèå â êàæäîì ïðîöåññå. Ñëåäîâàòåëüíî, êîãäà ñîáûòèåðåøåíèÿ ïðîèçîéäåò, êàæäûé ïðîöåññ áóäåò óæå îñâåäîìëåí îM , è ýòî ìîæíî ðàñöåíèâàòü êàê òðåáóåìîå PIF-àëãîðèòìîìóâåäîìëåíèå notify . Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÂîëíîâûå àëãîðèòìû íåîáõîäèìû äëÿ ãëîáàëüíîéñèíõðîíèçàöèè (Synchronization, SYN) ìåæäó ïðîöåññàìè.Òðåáîâàíèå ñèíõðîíèçàöèè òàêîâû: â êàæäîì ïðîöåññå qäîëæíî áûòü âûïîëíåíî ñîáûòèå aq , è â íåêîòîðûõ ïðîöåññàõñîáûòèå bp äîëæíî áûòü âûïîëíåíî òàê, ÷òîáû âûïîëíåíèå aqïðîèçîøëî ïî âðåìåíè ðàíåå, íåæåëè âûïîëíåíèå ëþáîãî èçñîáûòèé bp . SYN-àëãîðèòìå ñîáûòèÿ bp ðàññìàòðèâàþòñÿ êàê ñîáûòèÿdecide .Óòâåðæäåíèå 8.Êàæäûé âîëíîâîé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí âêà÷åñòâå SYN-àëãîðèòìà.Óòâåðæäåíèå 9.Êàæäûé SYN-àëãîðèòì ìîæåò áûòü èñïîëüçîâàí â êà÷åñòâåâîëíîâîãî àëãîðèòìà.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÇàäà÷à 1.Äîêàçàòü Óòâåðæäåíèå 8.Çàäà÷à 2.Äîêàçàòü Óòâåðæäåíèå 9.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: INFÂîëíîâûå àëãîðèòìû íåîáõîäèìû äëÿ âû÷èñëåíèÿ íåêîòîðûõôóíêöèè, çàâèñÿùèõ îò âõîäíûõ äàííûõ êàæäîãî ïðîöåññà.Ïðèìåðîì òàêèìè ôóíêöèÿìè ìîãóò ñëóæèòü ôóíêöèè òî÷íîéíèæíåé ãðàíè ïî âñåì âõîäàì.Ïóñòü (X , 6) ÷àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî.

Òîãäàýëåìåíò c íàçûâàåòñÿ òî÷íîé íèæíåé ãðàíüþ ýëåìåíòîâ a è b ,åñëè c 6 a , c 6 b è ∀d : (d 6 a ∧ d 6 b =⇒ d 6 c) .Åñëè â (X , 6) òî÷íàÿ íèæíÿÿ ãðàíü âñåãäà ñóùåñòâóåò, òî îíàîïðåäåëÿåòñÿ îäíîçíà÷íî è îáîçíà÷àåòñÿ a ↓ b . Äâóìåñòíàÿîïåðàöèÿ ↓ ÿâëÿåòñÿ êîììóòàòèâíîé (a ↓ b = b ↓ a) èàññîöèàòèâíîé (a ↓ (b ↓ c) = (a ↓ b) ↓ c ) , è ïîýòîìó åå ìîæíîðàñïðîñòðàíèòü íà êîíå÷íûå ìíîæåñòâà:inf{j1 , . . . , jk } = j1 ↓ · · · ↓ jk .Ïðèìåðàìè ôóíêöèè ↓ ìîãóò ñëóæèòü îïåðàöèèmin, max, ∧, ∨, ∩, ∪ .Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: INFÏðîáëåìà âû÷èñëåíèÿ òî÷íîé íèæíåé ãðàíè (InmumComputation, INF) òàêîâà. Âñå ïðîöåññû q íàäåëåíû âõîäíûìèäàííûìè dq , êîòîðûå ÿâëÿþòñÿ ýëåìåíòàìè ÷àñòè÷íîóïîðÿäî÷åííîãî ìíîæåñòâà X . Òðåáóåòñÿ, ÷òîáû íåêîòîðûåâûäåëåííûå ïðîöåññû âû÷èñëèëè çíà÷åíèå ↓ {dp : q ∈ P} è÷òîáû ýòè ïðîöåññû áûëè îñâåäîìëåíû î çàâåðøåíèèâû÷èñëåíèÿ. Îíè çàïèñûâàþò ðåçóëüòàò âû÷èñëåíèÿ âïåðåìåííîé out , è èì íå ðàçðåøàåòñÿ âïîñëåäñòâèè èçìåíÿòüçíà÷åíèå ýòîé ïåðåìåííîé.Çàïèñü çíà÷åíèÿ â ïåðåìåííóþ out , ðàññìàòðèâàåòñÿ êàêñîáûòèå decide â INF-àëãîðèòìå.Óòâåðæäåíèå 10.Êàæäûé âîëíîâîé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí âêà÷åñòâå INF-àëãîðèòìà.Óòâåðæäåíèå 11.Êàæäûé INF-àëãîðèòì ìîæåò áûòü èñïîëüçîâàí â êà÷åñòâåâîëíîâîãî àëãîðèòìà.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÇàäà÷à 3.Äîêàçàòü Óòâåðæäåíèå 10.Çàäà÷à 4.Äîêàçàòü Óòâåðæäåíèå 11.Ïðèìåðû âîëíîâûõ àëãîðèòìîâÊîëüöåâîé àëãîðèòìÏðåäíàçíà÷åí äëÿ êîëüöåâîé ñåòè è äëÿ ãàìèëüòîíîâîé ñåòè, âêîòîðîé èíôîðìàöèÿ î íåêîòîðîì ôèêñèðîâàííîìãàìèëüòîíîâîì öèêëå çàëîæåíà âî âñåõ ïðîöåññàõ.Ïðåäïîëàãàåòñÿ, ÷òî êàæäîìó ïðîöåññó p ïðåäïèñàí ñîñåäNextp òàê, ÷òîáû êàíàëû ñâÿçè ìåæäó âûäåëåííûìè òàêèìîáðàçîì ñîñåäÿìè îáðàçîâûâàëè ãàìèëüòîíîâ öèêë.Êîëüöåâîé àëãîðèòìÀëãîðèòì ÿâëÿåòñÿ öåíòðàëèçîâàííûì: èíèöèàòîð îòïðàâëÿåòñîîáùåíèå tok (îíî íàçûâàåòñÿ ìàðêåðîì ) ïî öèêëó, êàæäûéïðîöåññ ïåðåäàåò åãî äàëåå, è, êîãäà îíî âîçâðàùàåòñÿèíèöèàòîðó, òîò ïðèíèìàåò ðåøåíèåÄëÿ èíèöèàòîðà:begin send tok to Nextp ; receive tok ; decideÄëÿ íåèíèöèàòîðà:begin receive tok; send tok to Nextp endendÊîëüöåâîé àëãîðèòìPP1 PPPPMBBBBBBBBBBBBPPPPqÊîëüöåâîé àëãîðèòìPP1 PPPPtok MBBBBBBBBBBBBPPPPqÊîëüöåâîé àëãîðèòìPP1 PPPPtokMBBBBBBBBBBBBPPPPqÊîëüöåâîé àëãîðèòìtok PP1 PPPPMBBBBBBBBBBBBPPPPqÊîëüöåâîé àëãîðèòìPP1 PPPtokPMBBBBBBBBBBBBPPPPqÊîëüöåâîé àëãîðèòìPP1 PPPPMBBBBBBBBBBBBPPPPq tokÊîëüöåâîé àëãîðèòìPP1 PPPPMBBBBBBBBBBBBPPPPqtokÊîëüöåâîé àëãîðèòìPP1 PPPPMBBBBBBBBBBBBPPPPqtokÊîëüöåâîé àëãîðèòìPP1 PPPPMBBBBBBBBBBBBPPPPqtokÊîëüöåâîé àëãîðèòìPP1 PPPPMBBBBBBBBBBBBtok PPPPqÊîëüöåâîé àëãîðèòìPP1 PPPPMBBBBBBtokBBBBBBPPPPqÊîëüöåâîé àëãîðèòìPP1 PPPPtok MBBBBBBBBBBBBPPPPqÊîëüöåâîé àëãîðèòìPP1 PPPPtok MBdecideBBBBBBBBBBBPPPPqÊîëüöåâîé àëãîðèòìÓòâåðæäåíèå 12.Êîëüöåâîé àëãîðèòì ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì.Çàäà÷à 5.Äîêàçàòü Óòâåðæäåíèå 12.Çàäà÷à 6.À ìîãóò ëè âîëíîâûå àëãîðèòìû âû÷èñëÿòü ñóììû?Ïðèìåðû âîëíîâûõ àëãîðèòìîâÄðåâåñíûé àëãîðèòìÏðåäíàçíà÷åí äëÿ äðåâåñíîé ñåòè, íî ìîæåò áûòü èñïîëüçîâàíè äëÿ ïðîèçâîëüíîé ñåòè, èìåþùåé äîñòóï ê îñòîâíîìó äåðåâóýòîé ñåòè.Èíèöèàòîðû âñå ëèñòîâûå âåðøèíû äåðåâà.Èäåÿ.Âñå ëèñòüÿ ñåòè çàïóñêàþò àëãîðèòì.Êàæäûé ïðîöåññ îòïðàâëÿåò â òî÷íîñòè îäíî ñîîáùåíèå íàïðîòÿæåíèè ðàáîòû àëãîðèòìà.Åñëè ïðîöåññ óæå ïîëó÷èë ñîîáùåíèå ïî êàæäîìó èçèíöèäåíòíûõ åìó êàíàëîâ, êðîìå îäíîãî (ýòî óñëîâèåïåðâîíà÷àëüíî âåðíî äëÿ ëèñòüåâ), òî îí îòïðàâëÿåò ñîîáùåíèåïî îñòàâøåìóñÿ êàíàëó.Åñëè ïðîöåññ óæå ïîëó÷èë ñîîáùåíèå ïî âñåì èíöèäåíòíûìåìó êàíàëàì, òî îí ïðèíèìàåò ðåøåíèå.Äðåâåñíûé àëãîðèòìHHHHHHHH@@@@@ @@@@@ Äðåâåñíûé àëãîðèòìHHHH@@@@@ ~~~ HHHH@@@@@~~Äðåâåñíûé àëãîðèòìHHHH∗@@tok@@@ ~~~ HHHH@@@@@~~Äðåâåñíûé àëãîðèòìHHHH∗@@@@@ ~~~ HHHH@@@@ tok@~~∗Äðåâåñíûé àëãîðèòìHHHH∗∗@@@@ tok@ ~~~ HHHH@@@@@~~∗Äðåâåñíûé àëãîðèòìHHHH∗∗@@∗ @@tok@ ~~~ HHHH@@@@@~~∗Äðåâåñíûé àëãîðèòìHHHHHHHH~@@@@@@@@@@ ~~~~~ ∗∗∗∗Äðåâåñíûé àëãîðèòìHHHHHHtokHH~@@@@@@@@@@ ~~~~~ ∗∗∗∗∗Äðåâåñíûé àëãîðèòì~HHH∗~@@@@@ ~~~ ∗∗∗HHHHH@@@@@~~∗Äðåâåñíûé àëãîðèòì~HHH∗~@@@@@ ~~~ ∗∗HHHHH∗∗ @@∗@tok~@@~Äðåâåñíûé àëãîðèòì~HHH∗~@@@@@ ~~~ ∗∗∗HHHHH~@@@@@~~∗∗Äðåâåñíûé àëãîðèòì~HHH∗ ∗~@@@@@ ~~~ ∗∗∗HHHHHtok ~@@@@@~~∗∗Äðåâåñíûé àëãîðèòì~decideHHHHHHHH~~@@@@@@@@@@ ~~~~~ ∗ ∗∗∗∗∗∗Äðåâåñíûé àëãîðèòìÁóäåì èñïîëüçîâàòü çàïèñü fpq äëÿ îáîçíà÷åíèÿ ñîáûòèÿîòïðàâëåíèÿ ñîîáùåíèÿ ïðîöåññîì p ïðîöåññó q , à gpq äëÿîáîçíà÷åíèÿ ñîáûòèÿ ïðèåìà ïðîöåññîì q ñîîáùåíèÿ îòïðîöåññà p .Îáîçíà÷èì ñèìâîëîì Tpq ìíîæåñòâî ïðîöåññîâ, êîòîðûåäîñòèæèìû èç p áåç ïðîõîæäåíèÿ ïî ðåáðó pq (ïðîöåññû,ëåæàùèå â äåðåâå ¾ïî òó æå ñòîðîíó¿ ýòîãî ðåáðà, ÷òî èâåðøèíà p ) .Èç ñâÿçíîñòè ñåòè ñëåäóþò ñîîòíîøåíèÿ[Tpq =Trp ∪ {p}èP = {p} ∪r ∈Neighp \{q}[r ∈NeighpTrp .Äðåâåñíûé àëãîðèòìvarrecp [q] for each q ∈ Neighp : boolean init false ;(* recp [q] ïðèíèìàåò çíà÷åíèå true,åñëè p óæå ïîëó÷èë ñîîáùåíèå îò q *)#{q : recp [q] = false} > 1 dobegin receive tok from q ; recp [q] := true(* Òåïåðü åñòü åäèíñòâåííûé q0 ,äëÿ êîòîðîãî recp [q0 ] èìååò çíà÷åíèå false *)send tok to q0 with recp [q0 ] = false ;receive tok from q0 ; recp [q0 ] := true ;begin whiledecideoption: (* Îïîâåñòèòü äðóãèå ïðîöåññû î ðåøåíèè:forall q ∈ Neighp , q 6= q0 do send tok to q *)endend;Äðåâåñíûé àëãîðèòìÓòâåðæäåíèå 13.Äðåâåñíûé àëãîðèòì ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì.Äîêàçàòåëüñòâî.1) Êàæäûé ïðîöåññ îòïðàâëÿåò íå áîëåå îäíîãî ñîîáùåíèÿ.Çíà÷èò, â àëãîðèòìå èñïîëüçóåòñÿ íå áîëåå N ñîîáùåíèé.Îòñþäà ñëåäóåò, ÷òî àëãîðèòì äîñòèãàåò çàêëþ÷èòåëüíîéêîíôèãóðàöèè γ ñïóñòÿ êîíå÷íîå ÷èñëî øàãîâ.Ïîêàæåì, ÷òî â γ õîòÿ áû â îäíîì èç ïðîöåññîâ óæå ïðîèçîøëîñîáûòèå decide.Äðåâåñíûé àëãîðèòìÄîêàçàòåëüñòâî.2) Ñóììàðíîå ÷èñëî áèòîâ âî âñåõ ìàññèâàõ rec ðàâíîóäâîåííîìó ÷èñëó êàíàëîâ ñâÿçè, ò.å.