Лекция 9. Задача избрания лидера. Выборы лидера на дереве_ в кольцах. Алгоритм Ле-Ланна_ ... Эффект угасания, страница 4
Описание файла
PDF-файл из архива "Лекция 9. Задача избрания лидера. Выборы лидера на дереве_ в кольцах. Алгоритм Ле-Ланна_ ... Эффект угасания", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Ïðîöåññ p óáåäèòüñÿ â òîì, ÷òîâûïîëíÿåòñÿ ðàâåíñòâî acnp = cip , è îòïðàâèò ñîîáùåíèåhsmall, acnp i ïî êîëüöó, âûíóäèâ òåì ñàìûì êàæäûé ïðîöåññ qâûéòè èç îñíîâíîãî öèêëà, ïðèñâîèâ ïðè ýòîì ïåðåìåííîé winqçíà÷åíèå acnp .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÄîêàçàòåëüñòâî òåîðåìû.Äàííûé àëãîðèòì çàâåðøàåò ñâîé âûïîëíåíèå â êàæäîì èçïðîöåññîâ, è ïðè ýòîì âñå ïðîöåññû áóäóò ñîãëàñîâàííîîïîâåùåíû îá îòëè÷èòåëüíîì ïðèçíàêå ëèäåðà (ýòîò ïðèçíàêÿâëÿåòñÿ çíà÷åíèåì ïåðåìåííîé winq ) . Ïðîöåññ ñ óêàçàííûìïðèçíàêîì áóäåò ïðåáûâàòü â ñîñòîÿíèè leader , à âñåîñòàëüíûå ïðîöåññû â ñîñòîÿíèè lost.Ïîòðåáóåòñÿ ñàìîå áîëüøåå blog Nc + 1 òóðîâ, â êàæäîì èçêîòîðûõ ïðîèñõîäèò îáìåí ðîâíî 2N ñîîáùåíèÿìè; ýòî èñëóæèò îáîñíîâàíèåì îöåíêè ñëîæíîñòè 2N log N + O(N) ïî÷èñëó îáìåíîâ ñîîáùåíèÿìè.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÇàäà÷è.1.
Ïðèâåäèòå íà÷àëüíóþ êîíôèãóðàöèþ äëÿ àëãîðèòìàÏåòåðñîíà/ÄîëåâàÊëåéâàÐîäå, ïðè êîòîðîé àëãîðèòìóäåéñòâèòåëüíî ïîòðåáóåòñÿ ïðîâåñòè blog Nc + 1 òóðîâ.2. Ïðèâåäèòå òàêæå íà÷àëüíóþ êîíôèãóðàöèþ, ïðè êîòîðîéýòîìó àëãîðèòìó ïîòðåáóåòñÿ âñåãî äâà òóðà, íåçàâèñèìîîò ÷èñëà èíèöèàòîðîâ.3. Ìîæåò ëè àëãîðèòì çàâåðøèòü ðàáîòó çà îäèí òóð?Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.6.ÅñëèIêîëüöî îäíîíàïðàâëåííîå,Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.6.ÅñëèIêîëüöî îäíîíàïðàâëåííîå,Iïðîöåññû íå îñâåäîìëåíû î ðàçìåðàõ êîëüöà,Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.6.ÅñëèIêîëüöî îäíîíàïðàâëåííîå,Iïðîöåññû íå îñâåäîìëåíû î ðàçìåðàõ êîëüöà,Iâ êàíàëàõ ïîääåðæèâàåòñÿ î÷åðåäíîñòü ñîîáùåíèé,Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.6.ÅñëèIêîëüöî îäíîíàïðàâëåííîå,Iïðîöåññû íå îñâåäîìëåíû î ðàçìåðàõ êîëüöà,Iâ êàíàëàõ ïîääåðæèâàåòñÿ î÷åðåäíîñòü ñîîáùåíèé,Iâñå ïðîöåññû ÿâëÿþòñÿ èíèöèàòîðàìè,Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.6.ÅñëèIêîëüöî îäíîíàïðàâëåííîå,Iïðîöåññû íå îñâåäîìëåíû î ðàçìåðàõ êîëüöà,Iâ êàíàëàõ ïîääåðæèâàåòñÿ î÷åðåäíîñòü ñîîáùåíèé,Iâñå ïðîöåññû ÿâëÿþòñÿ èíèöèàòîðàìè,òî ñëîæíîñòü â ñðåäíåì âñÿêîãî àëãîðèòìà èçáðàíèÿ ëèäåðàNPáóäåò íå ìåíüøå, ÷åì N · HN , ãäå HN =1/k .k=1Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.7.Âñÿêèé àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå ñðàâíåíèÿ äëÿïðîèçâîëüíûõ ñåòåé èìååò ñëîæíîñòü (è â ñðåäíåì, è âíàèõóäøåì ñëó÷àå) íå ìåíüøóþ, ÷åì Ω(|E | + N log N) .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.7.Âñÿêèé àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå ñðàâíåíèÿ äëÿïðîèçâîëüíûõ ñåòåé èìååò ñëîæíîñòü (è â ñðåäíåì, è âíàèõóäøåì ñëó÷àå) íå ìåíüøóþ, ÷åì Ω(|E | + N log N) .Äîêàçàòåëüñòâî.ÑàìîñòîÿòåëüíîÀëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.7.Âñÿêèé àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå ñðàâíåíèÿ äëÿïðîèçâîëüíûõ ñåòåé èìååò ñëîæíîñòü (è â ñðåäíåì, è âíàèõóäøåì ñëó÷àå) íå ìåíüøóþ, ÷åì Ω(|E | + N log N) .Äîêàçàòåëüñòâî.ÑàìîñòîÿòåëüíîÑëåäñòâèå.Âñÿêèé äåöåíòðàëèçîâàííûé âîëíîâîé àëãîðèòì äëÿïðîèçâîëüíûõ ñåòåé áåç ïðåäâàðèòåëüíîé îñâåäîìëåííîñòè îñîñåäÿõ èìååò ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè, íåìåíüøóþ ÷åì Ω(|E | + N log N) .Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäåÒåîðåìà 8.7.Âñÿêèé àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå ñðàâíåíèÿ äëÿïðîèçâîëüíûõ ñåòåé èìååò ñëîæíîñòü (è â ñðåäíåì, è âíàèõóäøåì ñëó÷àå) íå ìåíüøóþ, ÷åì Ω(|E | + N log N) .Äîêàçàòåëüñòâî.ÑàìîñòîÿòåëüíîÑëåäñòâèå.Âñÿêèé äåöåíòðàëèçîâàííûé âîëíîâîé àëãîðèòì äëÿïðîèçâîëüíûõ ñåòåé áåç ïðåäâàðèòåëüíîé îñâåäîìëåííîñòè îñîñåäÿõ èìååò ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè, íåìåíüøóþ ÷åì Ω(|E | + N log N) .Äîêàçàòåëüñòâî.ÑàìîñòîÿòåëüíîÝôôåêò óãàñàíèÿÀëãîðèòì èçáðàíèÿ ëèäåðà ìîæíî ïîëó÷èòü èç ïðîèçâîëüíîãîâîëíîâîãî àëãîðèòìà ïðè ïîìîùè êîíñòðóêöèè, êîòîðàÿ íîñèòíàçâàíèå óãàñàíèå .Êàæäûé èíèöèàòîð çàïóñêàåò îòäåëüíóþ âîëíó.
×òîáûîòëè÷àòüñÿ îò ñîîáùåíèé äðóãèõ âîëí, ñîîáùåíèÿ, äâèæóùèåñÿïî âîëíå, çàïóùåííîé ïðîöåññîì p , äîëæíû áûòü ïîìå÷åíûîòëè÷èòåëüíûì ïðèçíàêîì ïðîöåññà p .Äàííûé àëãîðèòì ãàðàíòèðóåò, ÷òî íåçàâèñèìî îò êîëè÷åñòâàçàïóùåííûõ âîëí òîëüêî îäíà âîëíà ïðèâåäåò ê ðåøåíèþ, àèìåííî, òà âîëíà, êîòîðóþ çàïóñòèë èíèöèàòîð ñ ñàìûììëàäøèì îòëè÷èòåëüíûì ïðèçíàêîì.
Âñå îñòàëüíûå âîëíûáóäóò ïðåðâàíû åùå äî òîãî, êàê áóäåò ïðèíÿòî ðåøåíèå.Ýôôåêò óãàñàíèÿÀëãîðèòì èçáðàíèÿ ëèäåðà Ex(A) , ñîîòâåòñòâóþùèéâîëíîâîìó àëãîðèòìó A , óñòðîåí òàê.Ýôôåêò óãàñàíèÿÀëãîðèòì èçáðàíèÿ ëèäåðà Ex(A) , ñîîòâåòñòâóþùèéâîëíîâîìó àëãîðèòìó A , óñòðîåí òàê.Âñÿêèé ïðîöåññ â êàæäûé ìîìåíò âðåìåíè àêòèâåí ïîîòíîøåíèþ íå áîëåå ÷åì ê îäíîé âîëíå; ýòà âîëíà íàçûâàåòñÿåãî òåêóùåé àêòèâíîé âîëíîé , îáîçíà÷àåòñÿ caw è èìååòïåðâîíà÷àëüíîå çíà÷åíèå udef . Èíèöèàòîðû âûáîðîâïîñòóïàþò òàê, êàê áóäòî êàæäûé èç íèõ çàïóñêàåò âîëíó èïðèäàåò caw ñâîé îòëè÷èòåëüíûé ïðèçíàê â êà÷åñòâå çíà÷åíèÿ.Ýôôåêò óãàñàíèÿÊàê òîëüêî ñîîáùåíèå íåêîòîðîé âîëíû, çàïóùåííîéïðîöåññîì q , äîñòèãàåò ïðîöåññà p , òî p ïðîâîäèò ñëåäóþùèéàíàëèç ýòîãî ñîîáùåíèÿ.Ýôôåêò óãàñàíèÿÊàê òîëüêî ñîîáùåíèå íåêîòîðîé âîëíû, çàïóùåííîéïðîöåññîì q , äîñòèãàåò ïðîöåññà p , òî p ïðîâîäèò ñëåäóþùèéàíàëèç ýòîãî ñîîáùåíèÿ.IÅñëè q > cawp , òî ñîîáùåíèå ïðîñòî èãíîðèðóåòñÿ, ÷òîíåìåäëåííî ïðèâîäèò ê òîìó, ÷òî âîëíà, çàïóùåííàÿïðîöåññîì q , óãàñàåò.Ýôôåêò óãàñàíèÿÊàê òîëüêî ñîîáùåíèå íåêîòîðîé âîëíû, çàïóùåííîéïðîöåññîì q , äîñòèãàåò ïðîöåññà p , òî p ïðîâîäèò ñëåäóþùèéàíàëèç ýòîãî ñîîáùåíèÿ.IÅñëè q > cawp , òî ñîîáùåíèå ïðîñòî èãíîðèðóåòñÿ, ÷òîíåìåäëåííî ïðèâîäèò ê òîìó, ÷òî âîëíà, çàïóùåííàÿïðîöåññîì q , óãàñàåò.IÅñëè q = cawp , òî óêàçàííîå ñîîáùåíèå îáðàáàòûâàåòñÿòàê, êàê ýòî ïðåäïèñàíî âîëíîâûì àëãîðèòìîì.Ýôôåêò óãàñàíèÿÊàê òîëüêî ñîîáùåíèå íåêîòîðîé âîëíû, çàïóùåííîéïðîöåññîì q , äîñòèãàåò ïðîöåññà p , òî p ïðîâîäèò ñëåäóþùèéàíàëèç ýòîãî ñîîáùåíèÿ.IÅñëè q > cawp , òî ñîîáùåíèå ïðîñòî èãíîðèðóåòñÿ, ÷òîíåìåäëåííî ïðèâîäèò ê òîìó, ÷òî âîëíà, çàïóùåííàÿïðîöåññîì q , óãàñàåò.IÅñëè q = cawp , òî óêàçàííîå ñîîáùåíèå îáðàáàòûâàåòñÿòàê, êàê ýòî ïðåäïèñàíî âîëíîâûì àëãîðèòìîì.IÅñëè q < cawp èëè cawp èìååò çíà÷åíèå udef , òî pïðèñîåäèíÿåòñÿ ê âîëíå, çàïóùåííîé ïðîöåññîì q ,óñòàíàâëèâàÿ â ñâîèõ ïåðåìåííûõ ïåðâîíà÷àëüíûåçíà÷åíèÿ, à òàêæå âûïîëíÿÿ ïðèñâàèâàíèå cawp := q .Ýôôåêò óãàñàíèÿÊàê òîëüêî ñîîáùåíèå íåêîòîðîé âîëíû, çàïóùåííîéïðîöåññîì q , äîñòèãàåò ïðîöåññà p , òî p ïðîâîäèò ñëåäóþùèéàíàëèç ýòîãî ñîîáùåíèÿ.IÅñëè q > cawp , òî ñîîáùåíèå ïðîñòî èãíîðèðóåòñÿ, ÷òîíåìåäëåííî ïðèâîäèò ê òîìó, ÷òî âîëíà, çàïóùåííàÿïðîöåññîì q , óãàñàåò.IÅñëè q = cawp , òî óêàçàííîå ñîîáùåíèå îáðàáàòûâàåòñÿòàê, êàê ýòî ïðåäïèñàíî âîëíîâûì àëãîðèòìîì.IÅñëè q < cawp èëè cawp èìååò çíà÷åíèå udef , òî pïðèñîåäèíÿåòñÿ ê âîëíå, çàïóùåííîé ïðîöåññîì q ,óñòàíàâëèâàÿ â ñâîèõ ïåðåìåííûõ ïåðâîíà÷àëüíûåçíà÷åíèÿ, à òàêæå âûïîëíÿÿ ïðèñâàèâàíèå cawp := q .Êîãäà âîëíà, çàïóùåííàÿ ïðîöåññîì q , ïðèâîäèò êîñóùåñòâëåíèþ ñîáûòèÿ ðåøåíèÿ (â áîëüøèíñòâå àëãîðèòìîâðåøåíèå âñåãäà ïðèíèìàåò ñàì ïðîöåññ q ), ïðîöåññ q áóäåòñ÷èòàòüñÿ èçáðàííûì.Ýôôåêò óãàñàíèÿÇàäà÷è.1.
Ðàçðàáîòàéòå àëãîðèòì èçáðàíèÿ ëèäåðà â ïðîèçâîëüíîéñåòè íà îñíîâå ýôôåêòà óãàñàíèÿ, ïðèìåíåííîãî êâîëíîâîìó àëãîðèòìó ýõà. Îöåíèòå ñëîæíîñòü ïî ÷èñëóñîîáùåíèé ïîñòðîåííîãî Âàìè àëãîðèòìà. Îáîñíóéòå åãîêîððåêòíîñòü.2. Ðàçðàáîòàéòå àëãîðèòì èçáðàíèÿ ëèäåðà â êîëüöåâîé ñåòèñåòè íà îñíîâå ýôôåêòà óãàñàíèÿ, ïðèìåíåííîãî êâîëíîâîìó àëãîðèòìó â êîëöàõ. Ñðàâíèòå ïîñòðîåííûéÂàìè àëãîðèòì ñ àëãîðèòìîì ×åíÿÐîáåðòñà.  ÷åìñîñòîèò ñõîäñòâî è îòëè÷èå ýòèõ äâóõ àëãîðèòìîâ?ÊÎÍÅÖ ËÅÊÖÈÈ 8..
