Лекция 9. Задача избрания лидера. Выборы лидера на дереве_ в кольцах. Алгоритм Ле-Ланна_ ... Эффект угасания

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 8.Çàäà÷à èçáðàíèÿ ëèäåðà.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿ.Âîëíîâûå àëãîðèòìû èçáðàíèÿ ëèäåðà.Âûáîðû ëèäåðà íà äåðåâå.Âûáîðû â êîëüöàõ.Àëãîðèòì Ëå-Ëàííà.Àëãîðèòì ×åíÿ Ðîáåðòñà.Àëãîðèòì Ïåòåðñîíà/ÄîëåâàÊëåéâàÐîäå.Ýôôåêò óãàñàíèÿ.Çàäà÷à èçáðàíèÿ ëèäåðàÇàäà÷à èçáðàíèÿ ëèäåðà ñîñòîèò â òîì, ÷òîáû, èçêîíôèãóðàöèè, â êîòîðîé âñå ïðîöåññû ïðåáûâàþò â îäíîì èòîì æå ñîñòîÿíèè, äîñòè÷ü òàêîé êîíôèãóðàöèè, â êîòîðîéðîâíî îäèí ïðîöåññ áóäåò íàõîäèòüñÿ â ñîñòîÿíèè leader , à âñåîñòàëüíûå ïðîöåññû â ñîñòîÿíèè lost .Âûáîðû ëèäåðà ñðåäè ïðîöåññîâ ïðîâîäÿòñÿ, êîãäà íóæíîâûïîëíèòü êàêîé-íèáóäü öåíòðàëèçîâàííûé àëãîðèòì, è íåòçàðàíåå çàäàííîãî êàíäèäàòà, êîòîðûé ìîã áû âûñòóïèòüèíèöèàòîðîì ýòîãî àëãîðèòìà.Òàêîå ïðîèñõîäèò, êîãäà èíèöèàëèçàöèÿ âûïîëíÿåòñÿ â íà÷àëåðàáîòû èëè ïîñëå âûõîäà ñèñòåìû èç ñòðîÿ.Ïîñêîëüêó ìíîæåñòâî àêòèâíûõ ïðîöåññîâ ìîæåò áûòü çàðàíååíåèçâåñòíî, íåëüçÿ íàçíà÷èòü ðàç è íàâñåãäà îäèí èç ïðîöåññîâíà ðîëü ëèäåðà.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿÎïðåäåëåíèåíàçûâàåòñÿ àëãîðèòì,êîòîðûé îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè.Àëãîðèòìîì èçáðàíèÿ ëèäåðà1.

Êàæäûé ïðîöåññ íàäåëåí îäíèì è òåì æå ëîêàëüíûìàëãîðèòìîì.2. Àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì, ò.å. âû÷èñëåíèåìîæåò áûòü èíèöèèðîâàíî ïðîèçâîëüíûì íåïóñòûìïîäìíîæåñòâîì ïðîöåññîâ.3. Àëãîðèòì äîñòèãàåò çàêëþ÷èòåëüíîé êîíôèãóðàöèè âêàæäîì âû÷èñëåíèè, è â êàæäîé çàêëþ÷èòåëüíîéêîíôèãóðàöèè ñóùåñòâóåò ðîâíî îäèí ïðîöåññ, êîòîðûéíàõîäèòñÿ â ñîñòîÿíèè leader à âñå îñòàëüíûå ïðîöåññûïðè ýòîì ïðåáûâàþò â ñîñòîÿíèè lost.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿÏîñëåäíåå ñâîéñòâî èíîãäà áûâàåò îãðàíè÷åíî ëèøüòðåáîâàíèåì òîãî, ÷òîáû ðîâíî îäèí ïðîöåññ íàõîäèëñÿ âñîñòîÿíèè leader.

Åñëè çàäàí àëãîðèòì, óäîâëåòâîðÿþùèéýòîìó îñëàáëåííîìó òðåáîâàíèþ, òî åãî ìîæíî ëåãêîäîïîëíèòü ïîòîêîì ñîîáùåíèé, èíèöèèðîâàííûì ëèäåðîì,áëàãîäàðÿ êîòîðîìó âñå ïðîöåññû áóäóò îïîâåùåíû îðåçóëüòàòàõ âûáîðîâ.Âî âñåõ àëãîðèòìàõ ïðîöåññ p íàäåëåí ïåðåìåííîé statep ,ìíîæåñòâî çíà÷åíèé êîòîðîé âêëþ÷àåò â ñåáÿ leader è lost.Èíîãäà ïðåäïîëàãàåòñÿ, ÷òî çíà÷åíèåì statep ÿâëÿåòñÿ sleep äîòîãî, êàê p âûïîëíèë õîòü îäèí øàã íàøåãî àëãîðèòìà, è candêàê òîëüêî p ïðèñîåäèíèëñÿ ê âû÷èñëåíèþ, íî åùå íå áûëîñâåäîìëåí î òîì, âûèãðàë èëè ïðîèãðàë îí ýòè âûáîðû.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿÇàäà÷à î âûáîðàõ èçó÷àåòñÿ â ðàìêàõ ñëåäóþùèõ äîïóùåíèé.1Ïðîöåññû íå èìåþòäîñòóïà ê îáùèì ÷àñàì, è ïåðåäà÷à ñîîáùåíèé ìîæåòäëèòüñÿ ñêîëü óãîäíî äîëãî èëè êîðîòêî.Ñèñòåìà âïîëíå àñèíõðîííà.Äîïóùåíèå î ñèíõðîííîé ïåðåäà÷å ñîîáùåíèé ïî÷òè íåâëèÿåò íà ðåçóëüòàòû, îòíîñÿùèåñÿ ê çàäà÷å î âûáîðàõ:âñå ðàññìîòðåííûå àëãîðèòìû ìîæíî ïðèìåíÿòü âñèñòåìàõ ñ ñèíõðîííîé ïåðåäà÷åé ñîîáùåíèé.Äîïóùåíèå î ãëîáàëüíîì îòñ÷åòå âðåìåíè (ïðîöåññû ìîãóòîòñëåæèâàòü ðåàëüíîå âðåìÿ, çàäåðæêà ïåðåäà÷èñîîáùåíèÿ îãðàíè÷åíà è ïð.) äåéñòâèòåëüíî îêàçûâàåòâàæíîå âëèÿíèå íà ðåøåíèå çàäà÷è î âûáîðàõ.Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿ2Êàæäûé ïðîöåññ îïîçíàåòñÿ ïî óíèêàëüíîìó èìåíè,è ýòî èìÿ èçíà÷àëüíî èçâåñòíî ñàìîìó ïðîöåññó.Èìåíà ïðîöåññîâ (îòëè÷èòåëüíûå ïðèçíàêè ) îáðàçóþòëèíåéíî óïîðÿäî÷åííîå ìíîæåñòâà P .Ïðè ïðîåêòèðîâàíèè àëãîðèòìà èçáðàíèÿ ìîæíîïîñòóëèðîâàòü, ÷òî íà âûáîðàõ ïîáåäèò ïðîöåññ ñíàèìåíüøèì (íàèáîëüøèì) ïî ïîðÿäêó îòëè÷èòåëüíûìïðèçíàêîì.Òàê âîçíèêàåò çàäà÷à îòûñêàíèÿ íàèìåíüøåãîîòëè÷èòåëüíîãî ïðèçíàêà ïîñðåäñòâîìäåöåíòðàëèçîâàííîãî àëãîðèòìà çàäà÷à îòûñêàíèÿýêñòðåìóìîâ .Îñíîâíûå îïðåäåëåíèÿ è äîïóùåíèÿ3Êàæäîå ñîîáùåíèå ìîæåò ñîäåðæàòüO(w )áèò. êàæäîì ñîîáùåíèè ìîæåò ñîäåðæàòüñÿ ëèøüêîíñòàíòíîå ÷èñëî îòëè÷èòåëüíûõ ïðèçíàêîâ ïðîöåññîâ.Ýòî äîïóùåíèå ñäåëàíî äëÿ òîãî, ÷òîáû ñïðàâåäëèâîñîïîñòàâëÿòü ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìèäëÿ ðàçëè÷íûõ àëãîðèòìîâ.Âîëíîâûå àëãîðèòìû èçáðàíèÿ ëèäåðàÎòëè÷èòåëüíûå ïðèçíàêè ïðîöåññîâ ìîæíî èñïîëüçîâàòü äëÿíàðóøåíèÿ ñèììåòðèè ìåæäó ïðîöåññàìè, è àëãîðèòìèçáðàíèÿ ìîæíî ñïðîåêòèðîâàòü òàê, ÷òîáû âûäåëÿòü ïðîöåñññ íàèìåíüøèì îòëè÷èòåëüíûì ïðèçíàêîì.

Íàèìåíüøèéîòëè÷èòåëüíûé ïðèçíàê ìîæåò áûòü âû÷èñëåí ïðîöåññàìè ïîõîäó îäíîé âîëíû (ïî÷åìó? ).Âîëíîâûå àëãîðèòìû èçáðàíèÿ ëèäåðàÎòëè÷èòåëüíûå ïðèçíàêè ïðîöåññîâ ìîæíî èñïîëüçîâàòü äëÿíàðóøåíèÿ ñèììåòðèè ìåæäó ïðîöåññàìè, è àëãîðèòìèçáðàíèÿ ìîæíî ñïðîåêòèðîâàòü òàê, ÷òîáû âûäåëÿòü ïðîöåñññ íàèìåíüøèì îòëè÷èòåëüíûì ïðèçíàêîì. Íàèìåíüøèéîòëè÷èòåëüíûé ïðèçíàê ìîæåò áûòü âû÷èñëåí ïðîöåññàìè ïîõîäó îäíîé âîëíû (ïî÷åìó? ).Çíà÷èò, âûáîðû ìîæíî ïðîâåñòè, çàïóñòèâ âîëíó âû÷èñëåíèÿíàèìåíüøåãî îòëè÷èòåëüíîãî ïðèçíàêà, ïîñëå ÷åãî ïðîöåññ ñíàèìåíüøèì ïðèçíàêîì ñòàíîâèòñÿ ëèäåðîì. Òàê êàê àëãîðèòìèçáðàíèÿ äîëæåí áûòü äåöåíòðàëèçîâàííûì, ýòîò ïðèíöèïìîæíî ïðèìåíÿòü òîëüêî ê äåöåíòðàëèçîâàííûì âîëíîâûìàëãîðèòìàì.Âûáîðû ëèäåðà íà äåðåâåÇàäà÷à.Äîêàçàòü, ÷òî àëãîðèòì èçáðàíèÿ ëèäåðà íà îñíîâå çàäà÷èîòûñêàíèÿ ýêñòðåìóìîâ ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì, åñëèñîáûòèå èçáðàíèÿ ïðîöåññà ëèäåðîì ðàññìàòðèâàòü êàêñîáûòèå ðåøåíèÿ.Âûáîðû ëèäåðà íà äåðåâåÅñëè òîïîëîãèÿ ñåòè èìååò âèä äåðåâà, èëè â ñåòè åñòüîñòîâíîå äåðåâî, òî äëÿ âûáîðîâ ìîæíî âîñïîëüçîâàâàòüñÿäðåâåñíûì âîëíîâûì àëãîðèòìîì.

Íî çäåñü òðåáóåòñÿ, ÷òîáûèíèöèàòîðàìè áûëè âñå ëèñòîâûå âåðøèíû.Âûáîðû ëèäåðà íà äåðåâåÅñëè òîïîëîãèÿ ñåòè èìååò âèä äåðåâà, èëè â ñåòè åñòüîñòîâíîå äåðåâî, òî äëÿ âûáîðîâ ìîæíî âîñïîëüçîâàâàòüñÿäðåâåñíûì âîëíîâûì àëãîðèòìîì. Íî çäåñü òðåáóåòñÿ, ÷òîáûèíèöèàòîðàìè áûëè âñå ëèñòîâûå âåðøèíû.×òîáû çàïóñòèòü àëãîðèòì, êîãäà ëèøü ÷àñòü ïðîöåññîâÿâëÿþòñÿ èíèöèàòîðàìè, ê íåìó äîáàâëåí ýòàï ïîáóäêè .Ïðîöåññû, çàòåâàþùèå âûáîðû, íàâîäíÿþò ñåòü ñîîáùåíèÿìèwakeup. Ïîñëå ïîëó÷åíèÿ ñîîáùåíèå wakeup ïî âñåì êàíàëàì,ïðîöåññ çàïóñêàåò äðåâåñíûé âîëíîâîé àëãîðèòì, êîòîðûéñíàáæåí ïðèñòàâêîé äëÿ âû÷èñëåíèÿ íàèìåíüøåãîîòëè÷èòåëüíîãî ïðèçíàêà.Âûáîðû ëèäåðà íà äåðåâåÅñëè òîïîëîãèÿ ñåòè èìååò âèä äåðåâà, èëè â ñåòè åñòüîñòîâíîå äåðåâî, òî äëÿ âûáîðîâ ìîæíî âîñïîëüçîâàâàòüñÿäðåâåñíûì âîëíîâûì àëãîðèòìîì. Íî çäåñü òðåáóåòñÿ, ÷òîáûèíèöèàòîðàìè áûëè âñå ëèñòîâûå âåðøèíû.×òîáû çàïóñòèòü àëãîðèòì, êîãäà ëèøü ÷àñòü ïðîöåññîâÿâëÿþòñÿ èíèöèàòîðàìè, ê íåìó äîáàâëåí ýòàï ïîáóäêè .Ïðîöåññû, çàòåâàþùèå âûáîðû, íàâîäíÿþò ñåòü ñîîáùåíèÿìèwakeup.

Ïîñëå ïîëó÷åíèÿ ñîîáùåíèå wakeup ïî âñåì êàíàëàì,ïðîöåññ çàïóñêàåò äðåâåñíûé âîëíîâîé àëãîðèòì, êîòîðûéñíàáæåí ïðèñòàâêîé äëÿ âû÷èñëåíèÿ íàèìåíüøåãîîòëè÷èòåëüíîãî ïðèçíàêà.Êîãäà ïðîöåññ ïðèíèìàåò ðåøåíèå, îí çíàåò èìÿ ëèäåðà; åñëèýòî èìÿ ñîâïàäàåò ñ îòëè÷èòåëüíûì ïðèçíàêîì ñàìîãîïðîöåññà, òî îí ñòàíîâèòñÿ ëèäåðîì, à â ïðîòèâíîì ñëó÷àå îíïîëó÷àåò ñòàòóñ lost.Âûáîðû ëèäåðà íà äåðåâåwsp: boolinit false ;wrp: integerinit 0 ;recp [q] : bool äëÿ êàæäîãî q ∈ Neighp init false ;vp:Pinit p ;statep : (sleep, leader , lost)init sleep ;(* Ïîáóäêà *)begin if p is initiator thenbegin wsp := true ;forall q ∈ Neighp do send hwakeupi to qend;while wrp < #Neighp dobegin receive hwakeupi ; wrp := wrp + 1 ;if not wsp thenbegin wsp := true ;forall q ∈ Neighp do send hwakeupi to qvarendend;Âûáîðû ëèäåðà íà äåðåâå(* Çäåñü íà÷èíàåò ðàáîòàòü äðåâåñíûé àëãîðèòì *)while #{q : ¬recp [q]} > 1 dobeginreceive htok, r i from q ; recp [q] := true ; vp := min(vp , r );send htok, vp i to q0 with ¬recp [q0 ] ;receive htok, r i from q0 ;vp := min(vp , r ); (* ïðèíÿòü ðåøåíèå ñ îòâåòîì vp *)if vp = p then statep := leader else statep := lost ;forall q ∈ Neighp , q 6= q0 do send htok, vp i to qendendÂûáîðû ëèäåðà íà äåðåâåÒåîðåìà 8.1.Ïðåäëîæåííûé àëãîðèòì ðåøàåò çàäà÷ó î âûáîðàõ íàäðåâåñíûõ ñåòÿõ ñ èñïîëüçîâàíèåì O(N) îáìåíîâñîîáùåíèÿìè, çàòðà÷èâàÿ ïðè ýòîì O(D) åäèíèö âðåìåíè.Âûáîðû ëèäåðà íà äåðåâåÒåîðåìà 8.1.Ïðåäëîæåííûé àëãîðèòì ðåøàåò çàäà÷ó î âûáîðàõ íàäðåâåñíûõ ñåòÿõ ñ èñïîëüçîâàíèåì O(N) îáìåíîâñîîáùåíèÿìè, çàòðà÷èâàÿ ïðè ýòîì O(D) åäèíèö âðåìåíè.Äîêàçàòåëüñòâî.Êîãäà õîòü îäèí ïðîöåññ çàïóñêàåò äàííûé àëãîðèòì, âñåïðîöåññû îòïðàâÿò ñîîáùåíèå hwakeupi âñåì ñâîèì ñîñåäÿì, èêàæäûé ïðîöåññ çàïóñòèò âûïîëíåíèå äðåâåñíîãî àëãîðèòìàïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ hwakeupi îò êàæäîãî ñîñåäà.

Âñåïðîöåññû çàâåðøàò âûïîëíåíèå äðåâåñíîãî àëãîðèòìà ñ îäíèìè òåì æå çíà÷åíèåì ïåðåìåííîé v , à èìåííî, íàèìåíüøèìîòëè÷èòåëüíûì ïðèçíàêîì ñðåäè âñåõ ïðîöåññîâ (ïî÷åìó? ). Èåäèíñòâåííûé ïðîöåññ ñ òàêèì ïðèçíàêîì çàâåðøèò ðàáîòó âñîñòîÿíèè leader, à âñå ïðî÷èå ïðîöåññû â ñîñòîÿíèè lost.Âûáîðû ëèäåðà íà äåðåâåÄîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó ïåðåäàþòñÿ äâà ñîîáùåíèÿ hwakeupi è äâàñîîáùåíèÿ htok, r i, è ïîýòîìó ñëîæíîñòü ïî ÷èñëó îáìåíîâñîîáùåíèÿìè ñòàíîâèòñÿ ðàâíîé 4N − 4 .Âûáîðû ëèäåðà íà äåðåâåÄîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó ïåðåäàþòñÿ äâà ñîîáùåíèÿ hwakeupi è äâàñîîáùåíèÿ htok, r i, è ïîýòîìó ñëîæíîñòü ïî ÷èñëó îáìåíîâñîîáùåíèÿìè ñòàíîâèòñÿ ðàâíîé 4N − 4 .Ïî èñòå÷åíèè D åäèíèö âðåìåíè ïîñëå òîãî, êàê ïåðâûéïðîöåññ çàïóñòèë íàø àëãîðèòì, êàæäûé ïðîöåññ óæå îòïðàâèòñîîáùåíèÿ hwakeupi è, ñëåäîâàòåëüíî, ñïóñòÿ D + 1 åäèíèöâðåìåíè êàæäûé ïðîöåññ óæå çàïóñòèò âîëíó.Âûáîðû ëèäåðà íà äåðåâåÄîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó ïåðåäàþòñÿ äâà ñîîáùåíèÿ hwakeupi è äâàñîîáùåíèÿ htok, r i, è ïîýòîìó ñëîæíîñòü ïî ÷èñëó îáìåíîâñîîáùåíèÿìè ñòàíîâèòñÿ ðàâíîé 4N − 4 .Ïî èñòå÷åíèè D åäèíèö âðåìåíè ïîñëå òîãî, êàê ïåðâûéïðîöåññ çàïóñòèë íàø àëãîðèòì, êàæäûé ïðîöåññ óæå îòïðàâèòñîîáùåíèÿ hwakeupi è, ñëåäîâàòåëüíî, ñïóñòÿ D + 1 åäèíèöâðåìåíè êàæäûé ïðîöåññ óæå çàïóñòèò âîëíó.Ïåðâîå ðåøåíèå áóäåò ïðèíÿòî ñïóñòÿ D åäèíèö âðåìåíè ïîñëåíà÷àëà äâèæåíèÿ âîëíû, à ïîñëåäíåå ðåøåíèå áóäåò ïðèíÿòîñïóñòÿ D åäèíèö âðåìåíè ïîñëå ïåðâîãî, è ïîýòîìó îáùååçàòðà÷åííîå âðåìÿ ñòàíîâèòñÿ ðàâíûì 3D + 1 .

Âîëíîâûå àëãîðèòìû èçáðàíèÿ ëèäåðàÇàäà÷è.1. Ïîêàçàòü, ÷òî ñëîæíîñòü ïî âðåìåíè àëãîðèòìà èçáðàíèÿëèäåðà íà äåðåâå ñîñòàâëÿåò 2D .2. Êàêèì îáðàçîì ìîæíî ìîäèôèöèðîâàòü àëãîðèòìèçáðàíèÿ ëèäåðà íà äåðåâå, ÷òîáû ÷èñëî îáìåíîâñîîáùåíèÿìè ñóùåñòâåííî óìåíüøèëîñü?3. Êàê ìîæíî ëè ïðîâåñòè âûáîðû ëèäåðà â ïðîèçâîëüíîéñåòè ïðè ïîìîùè ôàçîâîãî àëãîðèòìà? Êàêîâà áóäåòñëîæíîñòü òàêîãî àëãîðèòìà èçáðàíèÿ ëèäåðà ïî ÷èñëóîáìåíîâ ñîîáùåíèÿìè?4. Êàê ìîæíî ëè ïðîâåñòè âûáîðû ëèäåðà â ïðîèçâîëüíîéñåòè ïðè ïîìîùè àëãîðèòìà Ôèííà? Êàêîâà áóäåòñëîæíîñòü òàêîãî àëãîðèòìà èçáðàíèÿ ëèäåðà ïî ÷èñëóîáìåíîâ ñîîáùåíèÿìè?Âûáîðû ëèäåðà â êîëüöàõÇàäà÷à î âûáîðàõ â êîëüöåâûõ ñåòÿõ áûëà âïåðâûå ïîñòàâëåíàËå-Ëàííîì â 1977; åìó óäàëîñü íàéòè åå ðåøåíèå ñîñëîæíîñòüþ O(N 2 ) ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè.Âûáîðû ëèäåðà â êîëüöàõÇàäà÷à î âûáîðàõ â êîëüöåâûõ ñåòÿõ áûëà âïåðâûå ïîñòàâëåíàËå-Ëàííîì â 1977; åìó óäàëîñü íàéòè åå ðåøåíèå ñîñëîæíîñòüþ O(N 2 ) ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè.Ýòî ðåøåíèå áûëî óëó÷øåíî ×åíåì è Ðîáåðòñîì â 1979; îíèïðåäëîæèëè àëãîðèòì, êîòîðûé èìååò ñëîæíîñòü O(N 2 ) âíàèõóäøåì ñëó÷àå, è ñëîæíîñòü O(N log N) â ñðåäíåì.Âûáîðû ëèäåðà â êîëüöàõÇàäà÷à î âûáîðàõ â êîëüöåâûõ ñåòÿõ áûëà âïåðâûå ïîñòàâëåíàËå-Ëàííîì â 1977; åìó óäàëîñü íàéòè åå ðåøåíèå ñîñëîæíîñòüþ O(N 2 ) ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè.Ýòî ðåøåíèå áûëî óëó÷øåíî ×åíåì è Ðîáåðòñîì â 1979; îíèïðåäëîæèëè àëãîðèòì, êîòîðûé èìååò ñëîæíîñòü O(N 2 ) âíàèõóäøåì ñëó÷àå, è ñëîæíîñòü O(N log N) â ñðåäíåì.Âîïðîñ î ñóùåñòâîâàíèè àëãîðèòìà ñî ñëîæíîñòüþ O(N log N)â íàèõóäøåì ñëó÷àå îñòàâàëñÿ îòêðûòûì äî 1980, êîãäà òàêîéàëãîðèòì áûë ïðåäëîæåí Õèðøáåðãîì è Ñèíêëåéðîìäâóíàïðàâëåííûõ êîëåö.Âûáîðû ëèäåðà â êîëüöàõÇàäà÷à î âûáîðàõ â êîëüöåâûõ ñåòÿõ áûëà âïåðâûå ïîñòàâëåíàËå-Ëàííîì â 1977; åìó óäàëîñü íàéòè åå ðåøåíèå ñîñëîæíîñòüþ O(N 2 ) ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè.Ýòî ðåøåíèå áûëî óëó÷øåíî ×åíåì è Ðîáåðòñîì â 1979; îíèïðåäëîæèëè àëãîðèòì, êîòîðûé èìååò ñëîæíîñòü O(N 2 ) âíàèõóäøåì ñëó÷àå, è ñëîæíîñòü O(N log N) â ñðåäíåì.Âîïðîñ î ñóùåñòâîâàíèè àëãîðèòìà ñî ñëîæíîñòüþ O(N log N)â íàèõóäøåì ñëó÷àå îñòàâàëñÿ îòêðûòûì äî 1980, êîãäà òàêîéàëãîðèòì áûë ïðåäëîæåí Õèðøáåðãîì è Ñèíêëåéðîìäâóíàïðàâëåííûõ êîëåö.

Êàêîå-òî âðåìÿ ïðåäïîëàãàëîñü, ÷òîΩ(N 2 ) îáìåíîâ ñîîáùåíèÿìè ñîñòàâëÿþò íèæíþþ îöåíêó äëÿîäíîíàïðàâëåííûõ êîëåö, íî Ïåòåðñîí, à òàêæå Äîëåâ, Êëåéâ èÐîäå â 1982 íåçàâèñèìî ïðåäëîæèëè ðåøåíèå ñëîæíîñòèO(N log N) äëÿ îäíîíàïðàâëåííîãî êîëüöà.Âûáîðû ëèäåðà â êîëüöàõÇàäà÷à î âûáîðàõ â êîëüöåâûõ ñåòÿõ áûëà âïåðâûå ïîñòàâëåíàËå-Ëàííîì â 1977; åìó óäàëîñü íàéòè åå ðåøåíèå ñîñëîæíîñòüþ O(N 2 ) ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè.Ýòî ðåøåíèå áûëî óëó÷øåíî ×åíåì è Ðîáåðòñîì â 1979; îíèïðåäëîæèëè àëãîðèòì, êîòîðûé èìååò ñëîæíîñòü O(N 2 ) âíàèõóäøåì ñëó÷àå, è ñëîæíîñòü O(N log N) â ñðåäíåì.Âîïðîñ î ñóùåñòâîâàíèè àëãîðèòìà ñî ñëîæíîñòüþ O(N log N)â íàèõóäøåì ñëó÷àå îñòàâàëñÿ îòêðûòûì äî 1980, êîãäà òàêîéàëãîðèòì áûë ïðåäëîæåí Õèðøáåðãîì è Ñèíêëåéðîìäâóíàïðàâëåííûõ êîëåö.