Algoritmus Chang a Roberts - Chang and Roberts algorithm
The Algoritmus Chang a Roberts[1] je na základě prstenu volební algoritmus koordinátora, zaměstnaný v distribuované výpočty.
Algoritmus
Algoritmus předpokládá, že každý proces má jedinečnou identifikaci (UID) a že se procesy mohou uspořádat do a jednosměrný prsten s komunikačním kanálem vedoucím z každého procesu k sousedovi ve směru hodinových ručiček. Dvoudílný algoritmus lze popsat takto:
- Zpočátku je každý proces v kruhu označen jako neúčastník.
- Proces, který si všimne nedostatku vůdce, zahajuje volby. Vytváří volební zpráva obsahující jeho UID. Poté odešle tuto zprávu ve směru hodinových ručiček svému sousedovi.
- Pokaždé, když proces odešle nebo přepošle volební zpráva, proces se také označuje jako účastník.
- Když proces obdrží volební zpráva porovnává UID ve zprávě s vlastním UID.
- Pokud je UID ve volební zprávě větší, proces bezpodmínečně předá volební zpráva ve směru hodinových ručiček.
- Pokud je UID ve volební zprávě menší a proces ještě není účastníkem, proces nahradí UID ve zprávě vlastním UID, odešle aktualizovaný volební zpráva ve směru hodinových ručiček.
- Pokud je UID ve volební zprávě menší a proces je již a účastník (tj. proces již odeslal volební zprávu s UID minimálně stejně velkým jako jeho vlastní UID), proces zahodí volební zprávu.
- Pokud je UID v příchozí volební zprávě stejný jako UID procesu, začne tento proces fungovat jako vůdce.
Když proces začne fungovat jako vedoucí, zahájí druhou fázi algoritmu.
- Vedoucí proces se označuje jako neúčastník a pošle zvolená zpráva sousedovi, který oznámil své volby a UID.
- Když proces obdrží zvolená zpráva, označuje se jako neúčastník, zaznamená zvolené UID a přepošle zvolená zpráva beze změny.
- Když zvolená zpráva dosáhne nově zvoleného vůdce, vůdce tuto zprávu zahodí a volby skončily.
Za předpokladu, že nedojde k žádným poruchám, které tento algoritmus dokončí. Algoritmus pracuje pro libovolný počet procesů N a nevyžaduje žádný proces, aby věděl, kolik procesů je v kruhu.
Vlastnosti
Algoritmus respektuje bezpečnost: proces obdrží zvolenou zprávu s vlastním UID, pouze pokud je jeho UID větší než ostatní ', a pouze tehdy, když se všechny procesy shodují na stejném UID. Algoritmus také respektuje živost. Státy „účastník“ a „neúčastník“ se používají tak, že když více voleb zahájí zhruba ve stejnou dobu, bude vyhlášen pouze jeden vítěz.
Když je tu jeden proces zahajující volby, algoritmus vyžaduje v nejhorším případě sekvenční zprávy 3N-1. Nejhorší případ je, když proces zahájení voleb bezprostředně navazuje na proces s největším UID: trvá mu N-1 zpráv, aby se k nim volební zpráva dostala, pak N zpráv, aby získala zpět své vlastní UID, pak další N zprávy poslat každému v kruhu zvolenou zprávu.
Tento algoritmus není příliš odolný vůči chybám. Lze zvýšit odolnost proti chybám Pokud každý proces zná celou topologii, zavedením zpráv ACK a přeskočením vadných uzlů při odesílání zpráv.
Viz také
Reference
- ^ Ernest Chang; Rosemary Roberts (1979), „Vylepšený algoritmus pro decentralizované hledání extrémů v kruhových konfiguracích procesů“, Komunikace ACM, ACM, 22 (5): 281–283, doi:10.1145/359104.359108CS1 maint: více jmen: seznam autorů (odkaz)