Лекция 7. Волновые алгоритмы - определения_ свойства. Кольцевой алгоритм. Древесный алгоритм. Алгоритм эха, страница 3

Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÂîëíîâûå àëãîðèòìû íåîáõîäèìû äëÿ ãëîáàëüíîéñèíõðîíèçàöèè (Synchronization, SYN) ìåæäó ïðîöåññàìè.Òðåáîâàíèå ñèíõðîíèçàöèè òàêîâû: â êàæäîì ïðîöåññå qäîëæíî áûòü âûïîëíåíî ñîáûòèå aq , è â íåêîòîðûõ ïðîöåññàõñîáûòèå bp äîëæíî áûòü âûïîëíåíî òàê, ÷òîáû âûïîëíåíèå aqïðîèçîøëî ïî âðåìåíè ðàíåå, íåæåëè âûïîëíåíèå ëþáîãî èçñîáûòèé bp . SYN-àëãîðèòìå ñîáûòèÿ bp ðàññìàòðèâàþòñÿ êàê ñîáûòèÿdecide .Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÂîëíîâûå àëãîðèòìû íåîáõîäèìû äëÿ ãëîáàëüíîéñèíõðîíèçàöèè (Synchronization, SYN) ìåæäó ïðîöåññàìè.Òðåáîâàíèå ñèíõðîíèçàöèè òàêîâû: â êàæäîì ïðîöåññå qäîëæíî áûòü âûïîëíåíî ñîáûòèå aq , è â íåêîòîðûõ ïðîöåññàõñîáûòèå bp äîëæíî áûòü âûïîëíåíî òàê, ÷òîáû âûïîëíåíèå aqïðîèçîøëî ïî âðåìåíè ðàíåå, íåæåëè âûïîëíåíèå ëþáîãî èçñîáûòèé bp . SYN-àëãîðèòìå ñîáûòèÿ bp ðàññìàòðèâàþòñÿ êàê ñîáûòèÿdecide .Óòâåðæäåíèå 8.Êàæäûé âîëíîâîé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí âêà÷åñòâå SYN-àëãîðèòìà.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÂîëíîâûå àëãîðèòìû íåîáõîäèìû äëÿ ãëîáàëüíîéñèíõðîíèçàöèè (Synchronization, SYN) ìåæäó ïðîöåññàìè.Òðåáîâàíèå ñèíõðîíèçàöèè òàêîâû: â êàæäîì ïðîöåññå qäîëæíî áûòü âûïîëíåíî ñîáûòèå aq , è â íåêîòîðûõ ïðîöåññàõñîáûòèå bp äîëæíî áûòü âûïîëíåíî òàê, ÷òîáû âûïîëíåíèå aqïðîèçîøëî ïî âðåìåíè ðàíåå, íåæåëè âûïîëíåíèå ëþáîãî èçñîáûòèé bp . SYN-àëãîðèòìå ñîáûòèÿ bp ðàññìàòðèâàþòñÿ êàê ñîáûòèÿdecide .Óòâåðæäåíèå 8.Êàæäûé âîëíîâîé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí âêà÷åñòâå SYN-àëãîðèòìà.Óòâåðæäåíèå 9.Êàæäûé SYN-àëãîðèòì ìîæåò áûòü èñïîëüçîâàí â êà÷åñòâåâîëíîâîãî àëãîðèòìà.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÇàäà÷à 1.Äîêàçàòü Óòâåðæäåíèå 8.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÇàäà÷à 1.Äîêàçàòü Óòâåðæäåíèå 8.Çàäà÷à 2.Äîêàçàòü Óòâåðæäåíèå 9.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: INFÂîëíîâûå àëãîðèòìû íåîáõîäèìû äëÿ âû÷èñëåíèÿ íåêîòîðûõôóíêöèè, çàâèñÿùèõ îò âõîäíûõ äàííûõ êàæäîãî ïðîöåññà.Ïðèìåðîì òàêèìè ôóíêöèÿìè ìîãóò ñëóæèòü ôóíêöèè òî÷íîéíèæíåé ãðàíè ïî âñåì âõîäàì.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: 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 .Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: 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-àëãîðèòìå.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: INFÏðîáëåìà âû÷èñëåíèÿ òî÷íîé íèæíåé ãðàíè (InmumComputation, INF) òàêîâà. Âñå ïðîöåññû q íàäåëåíû âõîäíûìèäàííûìè dq , êîòîðûå ÿâëÿþòñÿ ýëåìåíòàìè ÷àñòè÷íîóïîðÿäî÷åííîãî ìíîæåñòâà X .

Òðåáóåòñÿ, ÷òîáû íåêîòîðûåâûäåëåííûå ïðîöåññû âû÷èñëèëè çíà÷åíèå ↓ {dp : q ∈ P} è÷òîáû ýòè ïðîöåññû áûëè îñâåäîìëåíû î çàâåðøåíèèâû÷èñëåíèÿ. Îíè çàïèñûâàþò ðåçóëüòàò âû÷èñëåíèÿ âïåðåìåííîé out , è èì íå ðàçðåøàåòñÿ âïîñëåäñòâèè èçìåíÿòüçíà÷åíèå ýòîé ïåðåìåííîé.Çàïèñü çíà÷åíèÿ â ïåðåìåííóþ out , ðàññìàòðèâàåòñÿ êàêñîáûòèå decide â INF-àëãîðèòìå.Óòâåðæäåíèå 10.Êàæäûé âîëíîâîé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí âêà÷åñòâå INF-àëãîðèòìà.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: INFÏðîáëåìà âû÷èñëåíèÿ òî÷íîé íèæíåé ãðàíè (InmumComputation, INF) òàêîâà. Âñå ïðîöåññû q íàäåëåíû âõîäíûìèäàííûìè dq , êîòîðûå ÿâëÿþòñÿ ýëåìåíòàìè ÷àñòè÷íîóïîðÿäî÷åííîãî ìíîæåñòâà X .

Òðåáóåòñÿ, ÷òîáû íåêîòîðûåâûäåëåííûå ïðîöåññû âû÷èñëèëè çíà÷åíèå ↓ {dp : q ∈ P} è÷òîáû ýòè ïðîöåññû áûëè îñâåäîìëåíû î çàâåðøåíèèâû÷èñëåíèÿ. Îíè çàïèñûâàþò ðåçóëüòàò âû÷èñëåíèÿ âïåðåìåííîé out , è èì íå ðàçðåøàåòñÿ âïîñëåäñòâèè èçìåíÿòüçíà÷åíèå ýòîé ïåðåìåííîé.Çàïèñü çíà÷åíèÿ â ïåðåìåííóþ out , ðàññìàòðèâàåòñÿ êàêñîáûòèå decide â INF-àëãîðèòìå.Óòâåðæäåíèå 10.Êàæäûé âîëíîâîé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí âêà÷åñòâå INF-àëãîðèòìà.Óòâåðæäåíèå 11.Êàæäûé INF-àëãîðèòì ìîæåò áûòü èñïîëüçîâàí â êà÷åñòâåâîëíîâîãî àëãîðèòìà.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: SYNÇàäà÷à 3.Äîêàçàòü Óòâåðæäåíèå 10.Ïðèìåíåíèå âîëíîâûõ àëãîðèòìîâ: 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.Êîëüöåâîé àëãîðèòì ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì.Êîëüöåâîé àëãîðèòìÓòâåðæäåíèå 12.Êîëüöåâîé àëãîðèòì ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì.Çàäà÷à 5.Äîêàçàòü Óòâåðæäåíèå 12.Êîëüöåâîé àëãîðèòìÓòâåðæäåíèå 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 .Äðåâåñíûé àëãîðèòìÁóäåì èñïîëüçîâàòü çàïèñü fpq äëÿ îáîçíà÷åíèÿ ñîáûòèÿîòïðàâëåíèÿ ñîîáùåíèÿ ïðîöåññîì p ïðîöåññó q , à gpq äëÿîáîçíà÷åíèÿ ñîáûòèÿ ïðèåìà ïðîöåññîì q ñîîáùåíèÿ îòïðîöåññà p .Îáîçíà÷èì ñèìâîëîì Tpq ìíîæåñòâî ïðîöåññîâ, êîòîðûåäîñòèæèìû èç p áåç ïðîõîæäåíèÿ ïî ðåáðó pq (ïðîöåññû,ëåæàùèå â äåðåâå ¾ïî òó æå ñòîðîíó¿ ýòîãî ðåáðà, ÷òî èâåðøèíà p ) .Äðåâåñíûé àëãîðèòìÁóäåì èñïîëüçîâàòü çàïèñü 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 ;option: receive tok from q0 ; recp [q0 ] := true ;begin whiledecide(* Îïîâåñòèòü äðóãèå ïðîöåññû î ðåøåíèè:forall q ∈ Neighp , q 6= q0 do send tok to q *)endend;Äðåâåñíûé àëãîðèòìÓòâåðæäåíèå 13.Äðåâåñíûé àëãîðèòì ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì.Äðåâåñíûé àëãîðèòìÓòâåðæäåíèå 13.Äðåâåñíûé àëãîðèòì ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì.Äîêàçàòåëüñòâî.1) Êàæäûé ïðîöåññ îòïðàâëÿåò íå áîëåå îäíîãî ñîîáùåíèÿ.Çíà÷èò, â àëãîðèòìå èñïîëüçóåòñÿ íå áîëåå N ñîîáùåíèé.Îòñþäà ñëåäóåò, ÷òî àëãîðèòì äîñòèãàåò çàêëþ÷èòåëüíîéêîíôèãóðàöèè γ ñïóñòÿ êîíå÷íîå ÷èñëî øàãîâ.Ïîêàæåì, ÷òî â γ õîòÿ áû â îäíîì èç ïðîöåññîâ óæå ïðîèçîøëîñîáûòèå decide.Äðåâåñíûé àëãîðèòìÄîêàçàòåëüñòâî.2) Ñóììàðíîå ÷èñëî áèòîâ âî âñåõ ìàññèâàõ rec ðàâíîóäâîåííîìó ÷èñëó êàíàëîâ ñâÿçè, ò.å.