Volba v udce, Leader Election PA 150 Principy operacnch syst em u Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/ Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý Verze: podzim 2020 Volebn probl em { Kdy a proc se vol vedouc uzel ? 2 Existuje potreba spustit novy centraln proces napr. koordinatora vzajemneho vyloucen ci transakc, resp. novy centraln casovy server, resp. ztratil se token a jediny uzel mus vygenerovat novy token, resp. hleda se kostra grafu, ve ktere ma byt vudce koren (stromu) 2 Programovan distribuovanych aplikac je typicky jednoduss v prostred typu master/slave, (tj. 1/n procesu), napr. { rozeslan zprav ke vsem uzlum po kostre grafu organizovane z korene { koordinace distribuovanych transakc 2 Roli vedoucho objektu vyzaduje rada sprav vyjimek, napr. { odstranen uvaznut, generovan tokenu (peska) 2 Dynamicke urcovan vedoucho uzlu ma radu prednost, napr. { nevad vypadek centralnho uzlu { koordinatora { mnozina cinnych procesu, ze kterych se vol, nemus byt staticka Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 1 Volebn probl em 2 De nice problemu kazdy vypocet podle volebnho algoritmu ve skupine procesu v DS mus v konecnem case koncit kon gurac, ve ktere je jeden jediny uzel v roli vudce (leader, master, ...) 2 Kazdy proces ve skupine procesu se dobe sve existence nachaz v jednom ze tr stavu: nerozhodnuty, ve skupine procesu bez volba vudce, volba ve skupine procesu skoncila nen vudce, volba ve skupine procesu skoncila Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 2 Volebn probl em 2 Skupina procesu v DS je skupinou anonymnch procesu pokud procesy ve skupine nemaj jedinecne id 2 Skupina procesu v DS je skupinou neanonymnch procesu pokud procesy ve skupine maj jedinecne id Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 3 Volebn probl em 2 Algoritmus volby je { uniformn pokud procesy neznaj pocet procesu ve skupine procesu { neuniformn pokud procesy znaj pocet procesu ve skupine procesu 2 Uniformn algoritmus stejny algoritmus pro jakykoliv rozmer skupiny kazdy proces v kazdem rozmeru skupiny je modelovany stejnym stavovym strojem 2 Neuniformn algoritmus algoritmy pro ruzne rozmery skupiny se lis pro kazde n kazdy proces ve skupine rozmeru n je modelovany stejnym stavovym strojem An Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 4 Volebn probl em 2 Resen volby vudce ve skupine anonymnch procesu neexistuje nelze splnit podmnku bezpecnosti v kazdem kroku volby vsichni dostavaj shodne zpravy, kazdy se muze prohlasit za vudce 2 Speci kace algoritmu pro skupinu neanonymnch procesu procesy maj jedinecny id z totalne usporadane mnoziny vsechny uzly res stejny lokaln algoritmus algoritmus volby vudce je decentralizovany algoritmus, iniciatorem muze byt kterykoliv proces DS, algoritmus muze iniciovat vce iniciatoru soubezne algoritmus v kazdem proveden dosahne terminaln kon guraci, ve ktere je ve skupine procesu DS jediny proces (uzel, komponenta) ve stavu vudce Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 5 Volba, volebn b eh, ucastnk volby 2 Mejme skupinu neanonymnch procesu, ve ktere je jeden proces vudce, ostatn procesy nejsou vudci 2 Roli vudce prebral proces, ktery byl vtez proveden volby 2 Proces, ktery spoust jeden konkretn beh volebnho algoritmu, vyvolava volebn beh, je inici´atorem 2 Kazdy proces muze najednou vyvolat pouze jeden volebn beh ⇒ v prostred N procesu se muze soucasne odehravat v ramci jedne volby az N volebnch behu 2 Kazdy proces ma pravo i povinnost volit 2 Volba konc ukoncenm vsech volebnch behu aktivovanych v aktivovane volbe Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 6 Volba, volebn b eh, ucastnk volby 2 Kazdy proces muze byt v dobe resen algoritmu ucastnk volby (participant), pak participuje alespon v jednom volebnm behu, do ukoncen volby je ve stavu nerozhodnuty ,,neucastnk" volby (non-participant), pak neparticipuje v zadnem volebnm behu jeho stav nen de novany 2 Po ukoncen volby se kazdy uzel nachaz v jednom ze 2 stavu vudce, vedouc uzel, vtez volby (master, elected, winner) nebo nen vudce, je podrzeny uzel (not-elected, slave, loser) 2 roli vudce (master) zska po ukoncen volebnho behu jediny uzel Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 7 Volebn algoritmus, vlastnosti 2 vyber zvoleneho procesu (master) mus byt jednoznacny, i kdyz se realizuje vce volebnch behu soubezne Bez omezen obecnosti lze zavest podmnku vtezne volby { vol se proces s nejvyss prioritou, s nejvetsm id, ... priorita muze byt i strukturovana { napr. chceme-li zvolit pro roli master proces bezc na procesoru s nejmens prumernou vypocetn zatez, jako id procesoru zavedeme hodnotu {1/load, i}, kde load>0 je % doby procesoru venovane aplikacnm procesum a i je jedinecny index procesoru pro odlisen procesoru se stejnou zatez Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 8 Volebn algoritmus, vlastnosti 2 Kazdy proces Pi si udrzuje promennou electedi inicialne obsahuje prazdnou hodnotu (⊥) po ukoncen volebnho algoritmu obsahuje id zvoleneho procesu 2 Vsechny procesy maj de novanou prioritu procesy znaj skalu hodnot priorit kazdy proces zna svoji prioritu 2 Ilustrace akcentu spusten volebnho behu proces Pi posle koordinatorovi zpravu a nedostane do doby T odpoved' (napr. nedostane casove raztko od casoveho serveru) proces Pi nedostane do doby T token, ... Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 9 Volebn algoritmus, podmnky resen 2 bezpecnostn podmnka resen volebnho algoritmu rozhodnut uzlu byt vedoucm (zvolenym) procesem je zvolenym procesem nezmenitelne vedoucm procesem je nejvyse jeden proces, je jm bezc proces s nejvyss prioritou, Pmax (s nejvetsm id, ...) kazdy ucastnk volby ma electedi = ⊥ nebo electedi = id s Pmax 2 podmnka zivosti resen volebnho algoritmu na volbe participuj vsechny uzly a nakonec vsechny uzly nastav electedi = ⊥ jeden z uzlu se nakonec stane vedouc uzel 2 dokud se proces nestane ucastnkem volby, muze mt electedi nastaveno na id procesu zvoleneho v predesle volbe Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 10 Studovan e volebn algoritmy 2 Ring algorithm { volba smerovana po komunikacnm kruhu (LeLann, 1977) 2 Ring algorithm { volba smerovana po komunikacnm kruhu (Chang, Roberts, 1979) 2 Ring algorithm { volba smerovana po komunikacnm kruhu (Hirschberg-Sinclair, 1980) 2 Bully algorithm { volba v obecne topologii (Garcia-Molina, 1982) Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 11 Volebn algoritmus, Ring algorithm { LeLann, 1977 2 Iniciator posla svuj ID po kruhu, spoust volebn beh 2 Kruh je jednosmerny, kazdy proces ma jednoho souseda, komunikace je ve FIFO rezimu 2 Pokud volebn beh dosahne uzel dosud neparticipujc na volbe, spoust volebn beh tohoto uzlu 2 Z prichazejcch zprav si kazdy uzel postupne zapamatovava ID ostatnch procesu a tyto zpravy preposla dal po kruhu. 2 Jakmile zska zpravu se svym ID, zna ID vsech procesu na kruhu a ze seznamu ID zjist'uje kdo bude vudce (nejmens/nejvets ID, ...) Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 12 Volebn algoritmus, Ring algorithm { LeLann, 1977 2 Kazdy proces si v prubehu algoritmu volby vypracovava seznam aktivnch procesu s jejich prioritami 2 Po ukoncen volby kazdy proces v seznamu rozpozna sefa 2 Necht' proces Pi detekuje vypadek sefa, pak jeho dals kroky inicializuj volebn beh: Pi si vytvor novy, pocatecne prazdny, seznam aktivnch procesu, Pi posla svemu (pravemu) sousedovi volc zpravu elect(i) a do sveho seznamu aktivnch procesu zapisuje i ... Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 13 Volebn algoritmus, Ring algorithm { LeLann, 1977 2 Necht' proces Pi dostane zpravu elect(j) od leveho souseda Pj, pak reaguje jednm z nasledujc postupu: Zprava elect(j) je prvn ze zprav elect, ktere Pi dostal: Proces Pi se stava ucastnkem volby a i) vytvor si novy seznamu aktivnch procesu, pocatecne prazdny, a zapse do nej i a j ii) a posle zpravy elect(j) a elect(i) svemu pravemu sousedovi Zprava elect(j) nen prvn ze zprav elect, a pritom plat i = j: Proces Pi je jiz ucastnkem volby a i) do sveho seznamu aktivnch procesu prida j a ii) preposle elect(j) svemu pravemu sousedovi Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 14 Volebn algoritmus, Ring algorithm { LeLann, 1977 Zprava elect(j) nen prvn ze zprav elect, a pritom plat i = j: proces Pi drz seznam aktivnch procesu, ktery obsahuje priority vsech procesu v systemu a Pi si muze zjistit kdo bude v dalsm obdob koordinator a zadnou zpravu dal neposla Nastav si svoji promennou electedi = id na Pmax Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 15 Volebn algoritmus, Ring algorithm { LeLann, 1977 2 Algoritmus ma kvadratickou komunikacn slozitost, kazdy proces z N procesu zpusob generovan N zprav 2 Algoritmus je uniformn,decentralizovany, asynchronn 2 Obnoveny proces po vypadku nemus spoustet volebn beh, muze id koordinatora zjistit napr. dotazem poslanym po kruhu 2 Nasledujc algoritmus, Chang, Roberts, vylepsuje LeLanuv algoritmus tm, ze odstranuje z kruhu volebn behy procesu o kterych je jasne, ze nebudou zvoleni Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 16 Volebn algoritmus, Ring algorithm { volba po kruhu 2 Chang, Roberts, 1979 2 N procesu, kazdy proces Pi ma de novany komunikacn kanal ke svemu naslednkovi P(i+1)mod N 2 kazdy proces si uchovava id master v electedi electedi obsahuje id procesu s maximaln prioritou nebo ⊥ 2 kazdy proces je ve stavu participant (ucastnk) nebo non-participant volby 2 inicialne nen zadny proces ucastnkem volby 2 proces Pi zahajujc svuj volebn beh se oznac za ucastnka volby a posle volc zpravu election(Pi) svemu (levemu) sousedovi Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 17 Volebn algoritmus, Ring algorithm { Chang, Roberts 2 Uzel Pj po zskan zpravy election(Pi) od sveho praveho souseda reaguje nasledovne Pi > Pj: Pj preposle election(Pi) svemu levemu sousedovi, bez volebn beh Pi Pi < Pj a Pj dosud nen ucastnk volby: Pj posle election(Pj) svemu levemu sousedovi, startuje svuj volebn beh, oznac se za ucastnka volby Pi < Pj a Pj je ucastnk volby: Pj prijatou zpravu nepreposla, jeho volebn beh jiz bez volebn beh Pi rus Pi = Pj: Pj zskal volc zpravu, kterou on vyslal, prepne se do stavu vedouc uzel a oznac se za neucastnka volby a posle po kruhu ukoncovac zpravu elected(Pi) oznamujc identitu vedoucho uzlu Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 18 Volebn algoritmus, Ring algorithm { Chang, Roberts 2 Uzel Pi po zskan zpravy elected(Pj) od sveho praveho souseda reaguje nasledovne oznac se za ne-ucastnka volby poznac si identi kaci noveho vedoucho uzlu a pokud nen novym koordinatorem, zpravu elected(Pj) preposle svemu levemu sousedovi 2 sledovan stavu ucastnk / ne-ucastnk co nejdrve likviduje zbytecne nasobne volc behy, vzdy drve nez se oznam vysledek vtezne volby 2 vypadek uzlu znamena vypadek cele ulohy, v praxi by se musela vyvolavat rekonstrukce kruhu 2 Komunikacn kanaly mus dodrzovat FIFO porad prenosu zprav Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 19 Volebn algoritmus, Ring algorithm { Chang, Roberts Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 20 Volebn algoritmus, Ring algorithm { Chang, Roberts 2 spravnost algoritmu, splnen podmnky bezpecnosti pouze uzel Pj s maximaln hodnotou Pj zska od sveho praveho souseda ukoncovac zpravu a vstoup do stavu vedouc uzel uzly Pi = Pj, kde Pj je maximaln hodnota identi kace, nikdy nevstoup do stavu vedouc uzel 2 Jestlize volbu spust jediny proces, pak v nejhorsm prpade (proces s nejvyss id je jeho pravy soused), algoritmus generuje 3N − 1 zprav beh volebnho algoritmu se spoust dvakrat, druhy se ukonc volbou druhy beh se spoust po predan prvnch N − 1 zprav election druhy beh zpusob predan dalsch N zprav election zvoleny uzel zpusob vyslan N zprav elected Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 21 Volebn algoritmus, Ring algorithm { Chang, Roberts 2 Komunikacn slozitost algoritmu spusteneho soubezne vsemi potencialnmi iniciatory je O(N2 ), casova slozitost je O(N) 2 Algoritmus je asynchronn a uniformn a decentralizovany Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 22 Volebn algoritmus, Ring algorithm { Chang, Roberts Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 23 Volebn algoritmus, Ring algorithm { Chang, Roberts Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 24 Volebn algoritmus, Ring algorithm { Chang, Roberts Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 25 Volebn algoritmus, Ring algorithm { Chang, Roberts Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 26 Volebn algoritmus, Ring algorithm { Chang, Roberts plus 5 zprav oznamujcch cslo zvoleneho uzlu, 5, takze 20 zprav (n + (n − 1) + . . . + 1) + n = n(n + 1)/2 + n, slozitost O(n2 ) 5(5 + 1)/2 + 5 = 30/2 + 5 = 20 Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 27 Volba v udce, Ring algorithm, snzen komunikacn slozitosti 2 Lze snzit komunikacn slozitost pod O(n2 )? 2 Zkusme srit zpravy s mensm ID na mens vzdalenost po kruhu Ukazeme, ze lze dosahnout komunikacn slozitost O(n. log n) v nejhorsm prpade usporadan uzlu na kruhu Za cenu pouzit komplikovanejsho algoritmu Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 28 Volba v udce, Ring algorithm, snzen komunikacn slozitosti 2 Kazdy proces bude postupne zkoumat vzdalenejs a vzdalenejs sousedy v obou smerech na kruhu 2 V kazde fazi zkouman zdvojnasob vzdalenost zkouman 2 Jestlize jeho sonda dosahne proces s vetsm ID, zkouman se zastav 2 Jakmile sonda dosahne cleneho souseda, vrac se odpoved' iniciatorovi 2 Jestlize iniciator dostane odpoved' z obou smeru, prejde do dals faze 2 Jakmile proces zska sondu se svym ID, vol se za vudce Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 29 Volba v udce, Ring algorithm, snzen komunikacn slozitosti kazda zprava nalez konkretn fazi a ma sveho iniciatora Delka pruzkumu ve fazi k je 2k v kazde fazi se prenese az 4 × 2k zprav Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 30 Volba v udce, Ring algorithm, snzen komunikacn slozitosti 2 Ve fazi k = 0 muze zahajit zkouman kazdy proces 2 Ve fazi k > 0 muze zahajit zkouman kazdy vtez faze faze k − 1 vtez ma nejvets ID pri zkouman do vzdalenosti 2k−1 2 Maximaln pocet vtezu faze k − 1 nastane pokud jsou naskladan tak huste, jak je to mozne ve fazi k − 1 bude nejvyse n/(2k−1 + 1) vtezu v kazde fazi se mozny pocet vtezu snizuje cca na polovinu od n/(2k−1 + 1) do n/(2k + 1) Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 31 Volba v udce, Ring algorithm, snzen komunikacn slozitosti 2 Celkovy pocet zprav je sumou pres vsechny faze poctu vtezu v techto fazch krat pocty zprav zahajovanych temito vtezi Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 32 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair 2 r. 1980, topologie { obousmerny (neorientovany) kruh 2 Iniciator v jednotlivych fazch r = 0, 1, 2, . . . posla svoji identitu obema smery do vzdalenosti 2r vlnou nesouc pruzkumnou zpravu (jsem pi, mam nejvyss prioritu ?) ocekava jej pozitivn potvrzen po odrazu v poslednm z vlnou oslovenych uzlu 2 Identity cestujc po kruhu jsou likvidovane stejne jako v algoritmu Chang-Roberts 2 Proces pi je vtez ve fazi r = 0, 1, . . . pokud ma nejvyss id ze vsech procesu, ktere jsou od neho vzdalene az 2r skoku 2 Do faze r + 1 vstupuj pouze vtezove faze r 2 Ostatn procesy pouze prenasej zpravy mezi sousedy Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 33 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 34 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 35 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 36 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 37 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 38 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 39 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 40 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 41 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 42 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 43 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 44 Volebn algoritmus, Ring algorithm { Hirschberg-Sinclair 2 n uzlu, O(log n) faz 2 Delka zkouman ve fazi k je 2k 2 Pocet zprav souvisejcch s jednm docasne vedoucm procesem ve fazi k je nejvyse 4 × 2k ve fazch 0, 1, . . . , i, . . . , log n to jsou pocty zprav 4, 8, . . . , 2i+1 , . . . 2log n+1 a pocty docasnych vtezu n, n/2, . . . , n/2i , . . . , n/2log n−1 zatmco ve fazi 0 kazdy z n iniciatoru generuje vyslan 4 zprav ve fazi 1 kazdy z n/2 iniciatoru generuje po 8 zpravach atd 2 Slozitost z hlediska poctu zprav je tudz O(n.log n) Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 45 Volebn algoritmus, Bully algorithm 2 Bully { tyran, osoba, ktera obvykle otravuje a zastrasuje mens nebo slabs lidi { proces s nejvyss prioritou vynucujc si vudcovskou roli 2 Pouzitelny v prpadech, ve kterych { proces muze poslat zpravu kazdemu z ostatnch procesu v de novane mnozine procesu { se mohou vyskytovat vypadky uzlu (procesu) { komunikacn system je spolehlivy, zpravy se neztrac 2 Vypadek uzlu se pozna uplynutm casoveho intervalu (timeout) Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 46 Volebn algoritmus, Bully algorithm 2 Kdyz se proces rozhodne volit, zvol sebe a zasle o tom zpravu vsem procesum s vyss prioritou, spoust svuj volebn beh 2 Kdyz proces prijme zpravu o volebnm behu jineho procesu, ma urcite vyss prioritu,vrat mu zpet zamtavou odpoved' a sam spoust svuj volebn beh { vysle zadosti vsem prioritnejsm procesum 2 Kdyz procesu dostane zamtavou odpoved', existuje proces s vyss prioritou a proces se svuj volebn beh konc 2 Kdyz proces nedostane zamtavou odpoved', volbu vyhral, je novym master procesem a posle o tom zpravu vsem ostatnm procesum Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 47 Volebn algoritmus, Bully algorithm 2 Proces Pi, ktery rozpozna vypadek sefa { tyrana, se pokous prohlasit za noveho sefa sebe spustenm volebnho behu zjist'uje, zda on ma ze vsech prave cinnych procesu nejvyss prioritu, (mus tudz vsechny kooperujc procesy znat) nema-li nejvyss prioritu, da spustenm volebnho behu podnet k volebn aktivite prave cinnym procesum s vyss prioritou 2 Pokud obnov svuj beh vypadly proces, spoust okamzite svuj volebn beh Pokud nen aktivn zadny proces s vyss prioritou nez je jeho priorita, prebere tak roli sefa a vsichni se o tom dozv nebo se dozv, kdo je sefem Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 48 Volebn algoritmus, Bully algorithm Algoritmus 2 Pi zjistil necinnost dosavadnho sefa Pi posle volc zpravu { election(Pi) vsem procesum s vyssm prioritnm cslem nez ma on, kterou spoust novy volebn beh Pi se pokous prohlasit sebe za sefa Pi ceka dobu T na obdrzen odpoved s odmtnutm teto volby od procesu s vyss prioritou, reject Pokud iniciator volby Pi nedostane do doby T zadne odmtnut volby { nen aktivn zadny proces s vyss prioritou nez je priorita Pi a { Pi se zpravou coordinator(Pi), zaslanou vsem procesum, prohlasuje za sefa ... Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 49 Volebn algoritmus, Bully algorithm Pokud iniciator volby Pi dostane do doby T odmtnut volby, reject { je aktivn proces s vyss prioritou nez i, napr. j a { Pi ceka dobu T1 na obdrzen zpravy od Pj, ze pro dals obdob bude roli sefa vykonavat Pj, coordinator(Pj) Pokud iniciator Pi nedostane do doby T1 zpravu od Pj, ze Pj prebra roli sefa, { Pi startuje svuj volebn beh znovu (Pj mezitm vypadl) Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 50 Volebn algoritmus, Bully algorithm 2 Pokud Pi nen sef, muze kdykoliv dostat od jineho procesu Pj jednu ze dvou zprav coordinator(Pj) nebo election(Pj) coordinator(Pj) a j > i, pak plat, ze { Pj je novy koordinator, Pi si to zapamatuje v promenne elected coordinator(Pj) a j < i, pak plat, ze { Pi byl v dobe volby vypadly a uz obnovil svoji cinnost, ale jeste nespustil volebn beh a proto spoust volebn beh election(Pj) a j < i , pak Pj startoval volebn beh nepravem, Pi posle Pj odpoved' reject a zahajuje algoritmus sve vlastn volby, pokud tak dosud neucinil election(Pj) a j > i , pak ceka na zpravu coordinator(Pj) a pokud ji do timeoutu nezska, spoust volebn beh Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 51 Volebn algoritmus, Bully algorithm 2 Slozitost Bully algoritmu O(N2 ) zprav v nejhorsm prpade tj. kdyz volbu zahaj proces s nejnizs identi kac, pak postupne zahajuje volbu N − 1 procesu rozeslanm az N − 1 zprav Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 52 Volebn algoritmus, Bully algorithm 2 Slozitost Bully algoritmu O(N2 ) zprav v nejhorsm prpade tj. kdyz volbu zahaj proces s nejnizs identi kac, pak postupne zahajuje volbu N − 1 procesu rozeslanm az N − 1 zprav Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 53 Volebn algoritmus, Bully algorithm 1. 4 aktivn procesy, P1,...,4, P4 je koordinator 2. P1 a P4 vypadnou. P2 nedostane do doby T odpoved' od P4 a posle proto P3 svou volc zpravu 3. P3 odpov P2 odmtnutm a zasle svou volc zpravu P4 4. P2 dostane odmtnut sve volby od P3 a po dobu T1 ceka na potvrzen, ze P3 je koordinator 5. P4 mlc, je stale vypadly, do doby T neodmtne P3 a P3 se prohlas za koordinatora a vsem to sdel 6. Pozdeji, kdyz se P1 obnov, zasle svou volc zpravu P2, P3 a P4 7. P2 a P3 odpov odmtnutm P1 a spust svoje volby a P3 se opet stejnym postupem zvol za koordinatora 8. Az se obnov P4 sdel to P1, P2 a P3, volbu nezahajuje, nezna proces vyss prority Jan Staudek, FI MU Brno | PA150 { Koordinace a dosazen shody v distribuovan em prostred 54