Jo-jo (algoritmus) - Yo-yo (algorithm)

Jo-jo je distribuovaný algoritmus zaměřený na minimální hledání a volbu vůdce v generických připojených neorientovaných graf.^[1][2] Na rozdíl od Mega fúze má triviální ukončení a analýzu nákladů.

Úvod

Yo-yo představil Nicola Santoro.^[3] Postupuje postupnou eliminací a nazývá se technika redukce grafu prořezávání. Algoritmus je rozdělen do fáze předzpracování následované cyklickým opakováním dopředné fáze, zvané „Yo-“ a zpětné, zvané „-Yo“.

Předpoklady

Jo-jo staví volí a minimální vůdce v následujících prostorách:

• Celková spolehlivost: Při přenosu není ztracena žádná zpráva.
• Počáteční odlišné hodnoty (ID): Každý uzel má jedinečný identifikátor.
• Obousměrné komunikační kanály: Každá hrana je obousměrná, komunikace může cestovat oběma směry.

Nejsou nutná žádná další omezení.

Algoritmus

Předběžné zpracování

Fáze předzpracování je zahájena vysíláním. V bdělém stavu každý uzel odesílá své id všem svým sousedům a orientuje hranu směrem k uzlu vyššího stupně. Všimněte si, že se jedná pouze o logický krok, obousměrný kanál se v postupu neztratí. Convergecast je iniciátor informován o ukončení předzpracování. Tento proces vytváří tři kategorie uzlů:

• Zdroje: uzly s odchozími uzly, ale žádné příchozí uzly. Jedná se o nejméně uzlů v každém sousedství.
• Mezilehlé uzly: uzly s odchozími i příchozími hranami. Nejsou to ani nejmenší ani největší uzly v každé čtvrti.
• Dřezy: uzly s příchozími hranami, ale bez odchozích hran. Jedná se o největší uzly v každém sousedství.

Yo

Yo fáze jsou hodnoty zdrojů tlačeny dolů směrem k jímce.

Fáze „Yo-“ je iniciována zdroji. Zdroj odešle své id prostřednictvím příchozích hran a čeká. Mezilehlé uzly čekají na přijetí příslušných ID z každé ze svých příchozích hran. Jakmile se shromáždí všechny očekávané hodnoty, provede se minimální výpočet a minimální id se předá přes odchozí okraje. Dřezy jsou v této fázi pasivní.

Zprávy se odesílají přes orientované okraje a dostanou se k výlevkám, které spouští fázi „-Yo“.

- Ano

The - Ano fáze vytahuje pozitivní / negativní odpovědi.

Dřezy iniciují fázi „-Yo“ výpočtem přijatého minimálního ID a odesláním kladného čísla ANO nebo negativní NE skrz jejich příchozí hrany. A ANO je odeslán přes okraje nesoucí minimální vypočítané ID, a NE skrz zbývající hrany. Zprávy procházejí strukturou ke zdrojům: ke zdrojům s alespoň jedním příchozím NE stát se mrtvý a ztratí status kandidáta.

Fáze „-Yo“ také zahrnuje fázi restrukturalizace, kde jsou zdroje-meziprodukty-jímky umístěny pro zdroje, které nejsou kandidáty. Okraje nesoucí a NE jsou obráceni a kandidáti, kteří porazí aktuální fázi, se stanou buď propady nebo mezilehlými uzly.

Prořezávání

Prořezávání je optimalizační technika používaná ve fázi „-Yo“ a její poselství je obvykle začleněno do pozitivní / negativní odezvy. Odstraní zbytečné hrany a uzly. První jsou hrany, které dostávají stejnou hodnotu ${ displaystyle u> 1}$ příchozí hrany: triviálně ${ displaystyle u}$ jsou k ničemu a uzlem ořezány. Takové hrany se stávají mrtvý a jsou v následujících iteracích ignorovány. Ten místo toho snižuje počet uzlů odstraněním unárních jímek, tedy jímek s ${ displaystyle v = 1}$ příchozí hrana. Tyto hrany budou nuceny poslat zpět (pouze) přijaté minimum s a ANO odpověď, proto neprovádějí žádné výpočty užitečné pro minimální zjištění.

Struktura před a po prořezávání. Nejprve se uzel zcela vpravo nahoře stane jímkou ​​od přijetí NE. Jelikož se jedná o dřez s pouze jednou příchozí hranou, je oříznut. Totéž platí pro jeho rodiče a centrální větev.

Náklady

Fáze předzpracování se skládá z výměny skrz každý okraj dvou uzlů dopadajících na okraj. Máme tedy cenu ${ displaystyle sum _ {v ve V} deg (v) = 2m}$. The Jo-jo fáze se tedy skládají ze skenování struktury dopředu a dozadu ${ displaystyle 2m_ {i}}$ zprávy, kde ${ displaystyle m_ {i}}$ je počet aktuálních aktivních hran. Počet iterací je dán počtem iterací užitečných k odstranění každého počátečního zdroje. Podle hypotézy je každý zdroj propojen s alespoň dalším prostředním uzlem: pokud tomu tak není, pak je odpojena součást grafu, ale podle definice je graf připojen. V nejhorším případě střední ${ displaystyle n_ {i}}$ uzly jsou spojeny v párech a při každé iteraci je eliminována maximálně polovina zdrojů. Restrukturalizací každého z přeživších ${ displaystyle n_ {i + 1}}$ zdroje budou nyní připojeny ve dvojicích. Stejně jako v předchozím případě přežije maximálně polovina. Je zřejmé, že ukončení je splněno, když zůstane pouze jeden zdroj. Polovina ukládá a ${ displaystyle log_ {2} n}$ počet iterací během posledního výpočtu, tj. mezi dvěma nejvzdálenějšími přežívajícími zdroji, umístěnými na ${ displaystyle diam (G)}$. Celkové náklady činí ${ displaystyle 2m log {n}}$.

Ukončení

Ukončení je zaručeno přepínačem ve směrech prováděných v ANO/NE sem. Snížení zdrojů ve fázi „-Yo“ je monotónní: podle předchozího pozorování je každý zdroj srovnáván s alespoň jedním dalším zdrojem a díky jedinečnosti zdrojů jeden z nich převládá, zatímco ostatní zemřou. Protože počet počátečních zdrojů je konečný, monotónní redukce povede ke zbývajícímu jednomu zdroji.

Reference