====== IN-POS . Modely distribuovaných systémů ======

===== Zadání =====

  * Základní pojmy a principy, synchronní a asynchronní komunikace.
  * Synchronizace.
  * Detekce ukončení.
  * Problém vzájemného vyloučení a problém uváznutí a jejich řešení.
  * Problém volby vedoucího prvku.
  * Vliv topologie a její znalosti/neznalosti na složitost řešení problému.


  * PA150, IV100

===== Vypracování =====

==== Základní pojmy a principy, synchronní a asynchronní komunikace. ====

<box 90% red|Distribuovaný systém>
Systém jehož hardwarové nebo softwarové komponenty počítačů mohou komunikovat a koordinovat svou činnost pouze předáváním zpráv.
</box>

DS:
  * umožňují souběžné řešení programů
  * každá komponenta (včetně propojovací sítě) může selhávat a obnovovat činnost nezávisle na okolí.
    * ostatní se o stavu nedozvídají 

<box 90% red|Middleware>
Softwarová vrstva ležící mezi aplikacemi a OS poskytující aplikacím aplikacím programovací abstrakci a maskování heterogenity podpůrných sítí, počítačů, operačních systému, programovacích jazyků,...
</box>


  * Režimy DS
    * **Synchronní výměna zpráv**
      * výpočty probíhají v synchronních krocích (řízených globálními hodinami)
      * v každém běhu komponenty vyšlou a přijmou zprávy a provedou výpočet
      * přenos zprávy je kratší než jeden tik globálních hodin
    * **Asynchronní výměna zpráv**
      * globální čas neexistuje
      * komponenty řízeny lokálními hodinami
      * délka přenosu zpráv je neomezena

==== Synchronizace ====

<box 90% blue|Cristianův algoritmus synchronizace hodin>
Klient pošle dotaz **časovému serveru** a od získaného času přičte polovinu obrátky dotazu.
</box>

<box 90% blue|Berkeley algoritmus synchronizace hodin>
  - MASTER uzel se periodicky ptá na čas SLAVE uzlů.
  - Přičte polovinu obrátky.
  - Zprůměruje a odešle aktuální hodnotu SLAVE uzlům.
</box>

<box 90% blue|Network Time Protocol>
  * Možnost přesné synchronizace s UTC v Internetu.
  * Časové servery tvoří hierarchickou strukturu.
  * Módy synchronizace:
    * Multicast: jeden server odesílá informace o čase skupině.
    * Procedure-call: server vrací časové razítko na žádost (de facto Cristianův alg.)
    * Symmetric: mezi 2 servery v různých úrovních; servery si opakovaně posílají časová razítka a opravují chyby
</box>


  * příčinné pořadí = "stalo-se-před"


  * **Lokální čas**
    * budován na relaci "stalo-se-před"
      * pro události A, B v jednom procesu, kde A nastala před B: A->B
      * je-li A zaslání a B přijetí zprávy: A->B
      * platí transitivita: A->B,B->C => A->C
    * pužíván místo fyzického času

<box 90% blue|Lamportovy hodiny>
  * S každou událostí se sváže časové razítko.
  * Každý proces si udržuje logické (Lamportovy) hodiny. (Mapují částečné uspořádání.)
  * Odeslání zprávy:
    * Odešleme aktuální časové razítko.
    * Lokální čas zvýšíme o jedna.
  * Příjem zprávy:
    * Porovnáme přijaté časové razítko s lokálními hodinami.
    * Vezmeme větší z nich, zvýšíme o jedna a nastavíme jako lokální čas.
  * Vztah událostí:
    * A->B => TS(A) < TS(B)
<note important>Ze vztahu **TS(A)<TS(B)** nevyplývá **A->B**.</note>
</box>

<box 90% blue|Vektorové časové razítko>
  * Řeší problém s opačnou implikací u Lamprotových hodin.
  * Místo jednoho razítka pro lokální čas použijeme vektor časových razítek. (velikost = počet procesů)
    * iniciálně vyplněn nulami
  * Před odesláním proces zvýší "svůj" prvek vektoru o jedna. Pouze toto časové razítko se odesílá se zprávou.
  * Při přijetí zprávy zaktualizujeme odesilatelům prvek vektoru na maximum z lokální a přijaté hodnoty.
  * Vztah vektorových razítek:
    * V = V' iff všechny členy vektoru jsou si rovny
    * V < V' iff V[j] < V'[j] pro j=1,...|V|
</box>


==== Detekce ukončení ====

Algoritmus synchronizace ukončení má za úkol zabezpečit následující:
V případě, že všechny procesy jsou ve stavu ukončen, pak se v konečném čase tuto skutečnost všechny procesy dozví.

<box 90% blue|Dijkstra-Scholten (DS)>
  * Jestliže graf procesů je strom, pak každý listový proces při přechodu do stavu ukončen pošle signál svému otci.
  * Jakmile proces dostane signály od všech svých synů, pošle signál svému otci.
  * Jestliže všechny signály dostane iniciační proces, je distribuovaný výpočet ukončen.
</box>


<box 90% blue|Global State Recording Algorithm Candy & Lamport>
  * **iniciátor** = proces iniciující zjištění globálního stavu
    * zaznamená momentku svého lokálního stavu a odešle MARKER všem sousedům v DS
  * MARKER získal proces, který dosud nevypracoval momentku
    * zaznamená momentku svého lokálního stavu a pošle ji iniciátorovi
    * označí vstupní kanál, ze kterého přijal MARKER", jako prázdný
    * všem ostatním sousedům pošle MARKER
  * MARKER získal proces, který již momentku vypracoval
    * zaznamená události od poslední momentky a pošle iniciátorovi
  * Iniciátor nakonec sestaví globální stav
    * zná lokální momentky všech procesů
    * zná zprávy v "éteru"
    * Kanály jsou FIFO, tedy je globální momentka smysluplná ((ne)zahrnuté zprávy jsou odděleny v kanálech MARKERy).
</box>


=== Commit protokoly ===

Řeší atomicitu distribuované transakce.


<box 90% blue|2-fázový commit protokol>
Distribuovaná dohoda, zda transakci končit řádně, či krachovat v prostředí s výpadky uzlů.

  * ➕ řeší problém atomického ukončení
    * jestli jedna subtransakce krachuje, krachuje celá transakce
    * jestli se ukončí řádně všechny subtransakce, ukončí se řádně i celá transakce

2 fáze:

  * **Hlasovací fáze**
    * koordinátor žádá o závazek k rozhodnutí, že subtransakci řádně ukončí
    * participant ověří subtransakci na konzistenci dat a odpoví
  * **Fáze vydání rozhodnutí**
    * Koordinátor vydává na základě získaných odpovědí rozhodnutí zda řádně ukončit, nebo krachovat.
      * Zprávy commit/abort.
</box>



==== Problém vzájemného vyloučení ====

  * Dva nebo více procesů obsahují **kritické sekce** sdružené s jistým sdíleným objektem, které se musí za běhu procesu **vzájemně vyloučit**.
  * privilegovaný proces = proces v kritické sekci

  * **Podmínka bezpečnosti** = v každé konfiguraci existuje nejvýš jeden privilegovaný proces.
  * **Podmínka živosti** = Jestliže se proces snaží dostat do KS, stane se privilegovaným v konečném čase.
    * zamezuje uváznutí/stárnutí procesů
  * **Podmínka spravedlnosti** (jedna z uvedených)
    * pořadí vstupů do KS = pořadí vydání žádosti o vstup
    * každý ostatní proces DS smí žádající proces předběhnout nejvýše 1x

=== Řešení vzájemného vyloučení ===

  * **Centralizované řešení**
    * klient-server (jeden KOORDINÁTOR řeší vzájemné vylučování libovolného počtu procesů)
    * konstantní složitost
    * request, reply+release zprávy

  * **Distribuované řešení založené na regularitě komunikačních cest**

<box 90% blue|Token ring>
Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolující vstup do kritické sekce.

  * lineární složitost

  * ➕ Splněna podmínka bezpečnosti.
  * ➕ Splněna podmínka živosti.
  * ➕ Podmínka spravedlnosti splněna zajištěním maximálně jednoho předběhnutí od jiného procesu.
  * ➖ Ztrátu příznaku je nutné řešit distribuovanou volbou procesu, který jej vygeneruje.
  * ➖ Výpadek jednoho uzlu nutné řešit rekonstrukcí kruhu.
</box>

<box 90% blue|Raymond (tree)>
Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolujícího vstup do kritické sekce.

Příznak se předává po kostře grafu tak, aby se dodržela podmínka spravedlnosti na bázi časového pořadí vzniků žádostí.

  * Uzel držící příznak je kořenem stromu.
  * Uzel žádá o vstup do KS svého rodiče, ten jej předává po cestě ke kořeni.
  * Při předání příznaku se konfigurace stromu aktualizuje.

  * ➕ Vzájemná výlučnost splněna trvale.
  * ➕ Nemůže dojít ani k uváznutí ani ke stárnutí.

</box>

  * **Distribuované řešení založené na získání souhlasu partnerských procesů**

<box 90% blue|Suzuki-Kasami (token-passing)>
Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolujícího vstup do kritické sekce.

Příznak se předává na bázi cykličnosti uspokojování žádosti procesů.

Přehled nově generovaných a dosud nesplněných žádostí se udržuje distribuovaně v uzlech a v příznaku.

  * Proces pro žádost o vstup do KS odesílá všem uzlům REQUEST zprávu.
  * Uzel držící příznak po výstupu z KS odešle vybranému z procesů příznak.
  * Procesy si drží čísla žádostí od ostatních, token obsahuje pole s vyhověnými žádostmi.
  * Postupuje se cyklicky, přes procesy, které mají zájem.


  * ➖ Procesy se musí navzájem znát.

</box>

<box 90% blue|Ricard-Agrawala (distribuovaná fronta)>
Proces požadující vstoupit do kritické sekce pošle žádost o vstup s časovým razítkem všem ostatním.
  * Jestliže je příjemce v KS, neodpovídá a zařadí požadavek do fronty.
  * Jestliže příjemce není v KS a ani do ní nechce vstoupit, pak pošle zpět potvrzení práva vstupu do KS.
  * Jestliže příjemce není v KS, ale chce do ní vstoupit (sám vyslal žádost), porovná časovou značku své a přijaté žádosti.
    * Pokud byla vlastní žádost odeslána dříve, neodpovídá a uloží žádost do fronty.
    * Pokud byla přijatá žádost odeslána dříve, pošle zpět potvrzení práva vstupu do KS.

  * Až získá proces souhlas od všech, vstupuje do KS.
  * Po opuštění KS proces odešle potvrzení všem procesům, které má ve frontě.

  * ➕ Je splněna podmínka bezpečnosti.
  * ➕ Je splněna podmínka živosti.
  * ➕ Komunikační složitost je lineární.
  * ➖ Proces musí znát ostatní.
  * ➖ Výpadek jednoho procesu způsobí kolaps celého systému. => Vhodné pro malé a stabilní množiny procesů.
</box>

<box 90% blue|Maekawa (hlasovací kvórum)>
Každý proces obdrží jeden příznak (hlas).

Proces požadující vstup do KS žádá o příznak procesy ve svém kvóru.
  * kvůrum = podmnožina procesů, navzájem se protínají
  * Oslovený jej pošlu pokud jej ještě vlastní a sám se v KS nenachází.

Proces s hlasy od procesů v jeho kvóru vstupuje do KS. Po vystoupení hlasy vrací původním majitelům.

Podmínky kvóra:
  * bezpečnost:
    * Každá dvojice volebních okrsků má alespoň jeden společný prvek.
    * Každý má pouze jeden hlas. => Nemohou být současně zvoleny dva procesy.
  * spravedlnost
    * Velikost okrsků je konstantní a každý proces je ve stejném počtu okrsků.
    * Všechny procesy potřebují pro vstup do KS stejný počet hlasů
</box>

==== Uváznutí ====

Množina procesů P uvázla, jestliže každý proces Pi z P čeká na událost (uvolnění prostředků, zaslání zprávy), kterou vyvolá pouze některý z procesů P.

**Stárnutí** = požadavky 1 nebo více procesů z P nebudou splněny v konečném čase
  * z důvodů vyšších priorit jiného procesu
  * z důvodů prevence uváznutí apod.

== Nutná a postačující podmínka uváznutí ==

  * Nutné podmínky uváznutí: 
    - **vzájemné vyloučení** (**//Mutual exclusion//**)
      * se sdíleným zdrojem může v jednom okamžiku pracovat právě jeden proces 
    - **inkrementálnost požadavků** (též postupné uplatňování požadavků, **//Hold-and-Wait//**)
      * proces vlastnící nějaký zdroj potřebuje ke své činnosti zdroj další, který je však držen jiným procesem 
    - **nepředbíhatelnost** (**//No preemption//**)
      * zdroje lze uvolnit pouze procesem, který tyto vlastní a to pouze dobrovolně, až je nebude potřebovat 


  * Postačující podmínka:
    * **cyklické čekání** (též zacyklení pořadí, //Circular Wait//)
      * důsledek prvních tří nutných podmínek
      * existuje množina //n// procesů (//P<sub>0</sub>...P<sub>n</sub>//), kde proces //P<sub>0</sub>// čeká na uvolnění zdroje drženého procesem //P<sub>1</sub>//, //P<sub>1</sub>// čeká na uvolnění zdroje drženého //P<sub>2</sub>// atd. až //P<sub>n</sub>// čeká na uvolnění zdroje drženého //P<sub>0</sub>// 


==Metody ochrany proti uváznutí==

**Ochrana před uváznutím prevencí**

  * zajistíme, že se systém nikdy nedostane do stavu uváznutí
  * zrušíme platnost některé nutné podmínky

  * **nepřímé metody** (zneplatnění nutné podmínky)
    * **Virtualizací prostředků** zrušíme **//Mutual exclusion//**.
    * **Požadováním všech prostředků najednou** zrušíme **//Hold-and-Wait//**.
      * ➕ nemusí se nic odebírat, vhodné pro procesy s jednou nárazovou činností
      * ➖ neefektivní, možná prodleva při zahájení procesu
    * **Odebíráním prostředků** zrušíme **//No preemption//**
      * Proces, jemuž byl odmítnut požadavek, uvolní vše co vlastní a o vše požádá znovu.
      * ➕ vhodné pro prostředky s uchovatelným a obnovitelným stavem (FAP, procesor)
      * ➖ režijní ztráty, možnost cyklického restartu
  * **přímé metody** (nepřipuštění planosti postačující podmínky)
    * **uspořádáním prostředků** zrušíme možnost vzniku zacyklení při čekání: procesy smí požadovat prostředky pouze ve stanoveném pořadí
      * ➕ lze kontrolovat při kompilaci, nic se neřeší za běhu
      * ➖ neefektivní

**Obcházení uváznutí**

  * detekce potenciální možnosti vzniku uváznutí a nepřipuštění takového stavu
  * zamezujeme současné platnosti všech nutných podmínek
  * prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí)


<box 95% round blue|Bankéřův algoritmus >

  * Algoritmus používaný u zdrojů, kterých se přiděluje určité množství.
  * Když vstoupí novy proces do systému, musí deklarovat maximální počet instanci všech tříd, které bude pro svůj běh potřebovat. Tato maxima nesmi přesahovat celkový počet zdrojů v systému. Když uživatel požaduje množinu zdrojů, musí systém zjistit nepřevede-li alokace těchto zdrojů systém do nebezpečného stavu. Pokud by tomu tak bylo, musí proces čekat než jiný proces neuvolní dostatek zdrojů. V případe opačném jsou zdroje procesu alokovány. 
  * Pro zajištěni chodu bankéřova algoritmu je třeba udržovat množství datových struktur. Tyto struktury kódují stav systému alokace zdrojů. Nechť n je celkový počet procesu v systému a m je počet typu zdrojů. Potřebujeme následující datové struktury: 
    *Volny: vektor delky m indikujici pocet volnych instanci kazdeho typu zdroje. Jestlize Volny(j) = k, potom je v systemu k volnych instanci zdroje Rj. 
    *Max: matice typu (n,m) definujici maximalni pozadavek kazdeho procesu na kazdou tridu zdroju. Jestlize Max(i,j) = k, potom proces Pi muze pozadat maximalne o k instanci zdroje Rj. 
    *Alokace: matice typu (n,m) definujici pocet zdroju kazde tridy aktualne alokovany kazdemu procesu. Jestlize Alokace(i,j) = k, potom proces Pi ma momentalne alokovano k instanci zdroje tridy Rj. 
    *Potreba: matice typu (n,m) definujici zbyly pocet instanci zdroje kazde tridy nutny k dokonceni ulohy. Jestlize Potreba(i,j) = k, potom proces Pi potrebuje k dokonceni sve ulohy dalsich k instanci tridy Rj. 
  *Uvedene datove struktury se v case meni jak co do velikosti, tak co do hodnoty. Pro zjednoduseni prezentace Bankerova algoritmu definujme nasledujici vztah: Necht X a Y jsou vektory delky n. Potom X < = Y tehdy a jen tehdy, jestlize X(i) < = Y(i) pro vsechna i = 1, .. ,n. Napriklad jestlize X = (1, 7, 3, 2) a Y = (0, 3, 2, 1), potom Y < = X. Dale X < Y tehdy, jestlize X < = Y a zaroven X < > Y. 
  *Kazdou radku matic Alokace a Potreba muzeme zpracovavat jako vektor a oznacovat jako Alokacei a Potrebai. Vektor Alokacei specifikuje zdroje, ktere jsou aktualne alokovany procesu Pi a vektor Potrebai specifikuje dalsi zdroje, ktere proces Pi potrebuje pro sve dokonceni. 


Uvazujme system s peti procesy P0 az P4 a tri zdroje typu A, B, C. 
  *Zdroj typu A ma 10 instanci
  *zdroj typu B ma 5 instanci
  *zdroj typu C 7 instanci
Necht v case t0 je system v nasledujicim stavu: 
|     ^ Alokace ^^^   Max   ^^^ Volny   ^^^
|     ^ A ^ B ^ C ^ A ^ B ^ C ^ A ^ B ^ C ^
^ P0  | 0 | 1 | 0 | 7 | 5 | 3 | 3 | 3 | 2 |
^ P1  | 2 | 0 | 0 | 3 | 2 | 2 |
^ P2  | 3 | 0 | 2 | 9 | 0 | 2 |
^ P3  | 2 | 1 | 1 | 2 | 2 | 2 |
^ P4  | 0 | 0 | 2 | 4 | 3 | 3 |

  *Obsah matice **Potreba** je definovan rozdilem **Max - Alokace** a je tedy: 

|    ^ Potreba^^^
|    ^ A ^ B ^ C ^
| P0 | 7 | 4 | 3 |
| P1 | 1 | 2 | 2 |
| P2 | 6 | 0 | 0 |
| P3 | 0 | 1 | 1 |
| P4 | 4 | 3 | 1 |

  *V teto situaci je system v bezpecnem stavu. Sekvence < P1, P3, P4, P2, P0,> je bezpecna sekvence. 

</box>


**Detekce a obnova po uváznutí**

  * Uváznutí povolíme, ale jeho vznik detekujeme a řešíme.
  * OS periodicky testuje existenci uváznutí (detekce cyklu v grafu).
  * ➕ žádný prostoj při zahájení
  * ➖ nutnost řešit uváznutí

Způsoby řešení uváznutí:

  * zrušit všechny uváznuté procesy (nejčastěji používaná metoda)
  * návrat uváznutých procesů k poslednímu kontrolnímu bodu (možnost opakování situace)
  * postupně rušit uváznuté procesy (podle spotřebovaného času procesoru, počtu tiskových řádků, času do dokončení procesu, priority, množství vlastněných prostředků)
  * postupně předbíhat uváznuté procesy
  * zamezit současné platnosti nutných podmínek



**Ignorování hrozby uváznutí**

  * uváznutí je věc aplikace ne systému
  * způsob řešení zvolený většinou OS






=== Uváznutí v distribuovaném prostředí ===


<box 90% red|Distribuovaná transakce>
transakce zahrnující operace prováděné ve více uzle DS formou dílčích subtransakcí.

  * **koordinátor**
    * registruje spuštění transakce
    * registruje participanty (příp. dělí transakci na subtransakce)
    * řeší akce při ukončování
  * **správce**
    * udržuje deník pro obnovu transakcí
    * participuje na schématu řízení souběžnosti
  * **participant**
    * může kdykoliv volat koordinátora požadavkem ''abort-transaction'', pokud není schopen pokračovat v řešení subtransakce.
</box>



==== Problém volby vedoucího prvku ====

<box 90% red|Problém volby vůdce>
Každý výpočet podle volebního algoritmu ve skupině procesů DS musí v konečném čase končit konfigurací, ve které je jeden jediný uzel v roli vůdce.

Každý proces se během existence může nacházet ve třech stavech:
  * nerozhodnutý (ve skupině běží volba)
  * vůdce (volba skončila)
  * není vůdce (volba skončila)
</box>

  * **skupina anonymních procesů** = procesy nemají ve skupině jedinečné id
    * nelze řešit problém volby vůdce za splnění podmínky bezpečnosti (v každém kroku všichni dostávají shodné zprávy)
  * **skupina neanonymních procesů** = procesy mají ve skupině jedinečné id

  * **uniformní algoritmus** = procesy neznají počet procesů
    * stejný algoritmus pro jakýkoliv rozměr skupiny
  * **neuniformní algoritmus** = procesy znají počet procesů ve skupině
    * algoritmy pro různé rozměry skupiny se liší

  * volební běh
    * Každý proces může najednou vyvolat pouze jeden běh.
    * Může probíhat několik (N) paralelních běhů.
    * Každý proces má právo i povinnost volit.
    * Volba končí ukončením všech běhů.

  * Podmínka bezpečnosti
    * Rozhodnutí volby je zvoleným procesem nezměnitelné.
    * Vedoucím procesem je nejvýše jeden proces.
    * Každý účastník volby má nastaveno elected na id zvoleného procesu.
  * Podmínka živosti
    * Na volbě participují všechny procesy a nakonec nastaví elected na nějakou hodnotu.
    * Jeden uzel se nakonec stává vůdcem.


<box 90% blue|Ring algorithm (LeLann)>
Každý proces posílá své ID po kruhu.

  * Kruh je jednosměrný, každý proces má jednoho souseda a komunikace probíhá  ve FIFO režimu.
  * Z příchozích zpráv si uzel postupně zapamatovává ID ostatních a zprávy přeposílá dál po kruhu.
  * Po přijetí zprávy s vlastním ID zná proces všechny procesy v kruhu a za vodce zvolí proces s nejmenším/největším ID.
</box>

<box 90% blue|Ring algorithm (Chang, Roberts)>
Využitelnou topologií je obousměrný kruh. Každý proces má jednoho souseda (následníka) a uchovává si id vůdce v elected.

  * Každý proces je ve stavu ''participant'', nebo ''non-participant''.
    * Iniciálně jsou všichni ''non-participant''.
  * Proces zahajující volební běh se označí za ''participant'' a pošle volící zprávu <m>election(P_i)</m> následníkovi.
  * Následník se rozhoduje:
    * <m>P_i > P_{i+1}</m>: přepošle <m>election(P_i)</m>
    * <m>P_i < P_{i+1}</m> a není účastníkem volby: přepošle <m>election(P_{i+1})</m> a označí se za účastníka volby
    * <m>P_i < P_{i+1}</m> a je účastníkem volby: přijatou zprávu nepřeposílá = ruší volební běh <m>P_i</m>; volební běh <m>P_{i+1}</m> běží
    * <m>P_i = P_{i+1}</m>: <m>P_{i+1}</m> získal volící zprávu, kterou vyslal
      * přepne se do stavu vůdce
      * označí se za ''non-participant''
      * pošle po kruhu ukončovací zprávu <m>elected(P_i)</m> (ostatní si označí vůdce a zruší účast)

  * ➕ sledování stavu ''participant''/''non-participant'' umožňujue likvidovat zbytečné násobné běhy.
  * ➖ výpadek uzlu značí výpadek celé úlohy

  * nejhorší případ: O(n*n) zpráv
  * očekávaný počet zpráv: O(n log n) zpráv
</box>

<box 90% blue|Ring algorithm (Hirschberg-Sinclair)>
Využitelnou topologií je obousměrný kruh.

  * Iniciátor v jednotlivých fázích r=0,1,.. posílá svou identitu do vzdálenosti <m>2^r</m> nesoucí průzkumovou zprávu.
  * Identity cestující po kruhu jsou likvidovány jako u algoritmu Chang-Roberts.
  * Do další fáze vstupují pouze vítězové. (vítěz ve fázi = nejvyšší ID do vzdálenosti <m>2^r</m>)
    * Ostatní pouze přeposílají zprávy.

  * složitost: O(n log n)
</box>

<box 90% blue|Bully algorithm (Garcia-Molina)>
Proces s nejvyšším ID si vynucuje svou vůdcovskou roli.

Použitelnost:
  * Proces může poslat zprávu každému z ostatních procesů.
  * Mohou se vyskytovat výpadky uzlů.
    * Poznán na základě timeoutu.
  * Komunikační systém je spolehlivý (neztrácí se zprávy).

Když se proces rozhodne volit, zvolí sebe a zašle o tom zprávu všem procesům s vyšší prioritou.

Pokud proces přijme zprávu o volebním běhu:
  * má určitě vyšší prioritu => vrátí zamítavou odpověď
  * sám spouští volební běh -> zašle zprávu všem procesům s vyšší prioritou

Odpovědi:
  * Když proces dostane zamítavou odpověď, existuje proces s vyšší prioritou => proces ukončí svůj volební běh.
  * Když nedostane zamítavou odpověď, volbu vyhrál.
    * Nastaví se jako nový vůdce a pošle o tom všem ostatním procesům zprávu.

Pokud proces obnoví svůj běh, okamžitě zahajuje volební běh a nastane jedna ze dvou možností:
  * Stane se vůdcem.
  * Dozví se, kdo je vůdcem.
</box>


==== Vliv topologie a její znalosti/neznalosti na složitost řešení problému ====

FIXME: nejsem si 100% jistý, co se zde očekává (resp. z čeho čerpat)

  * Efektivita algoritmu velmi závisí na topologii sítě.
  * Zajímá nás **komunikační složitost**, případně časová složitost.


<box 90% red|Horní odhad pro problém>
Existuje algoritmus, který pro všechny topologie, vstupy, časování,... pracuje správně a vymění nejvíc f(n) zpráv.
</box>
<box 90% red|Dolní odhad pro problém>
Pro každý algoritmus existuje kombinace topologie, vstupu, časování,... že buď nepracuje správně, nebo vymění alespoň f(n) zpráv.
</box>

  * Časté topologie:
    * **úplný graf**
        * každý komunikuje přímo s každým
    * **kruh**
      * každý má levého a pravého souseda
      * všichni jsou uspořádání do kruhu
    * **jednosměrný kruh**
      * každý má jen jednoho souseda
      * po N přeposláních se zpráva dostane zpět k původci
    * **2D/3D mřížka**
    * **strom**

  * Pro tyto topologie existují často efektivnější algoritmy, protože lze spoléhat na jejich vlastnosti.
  * Pro globální algoritmy se může efektivita lišit na základě grafových vlastností:
    * hustota grafu
    * orientovanost
    * poloměr

  * Pro tvorbu paralelních algoritmů je nejprve potřebné zvládnout několik principielních úloh:
    * prohledávání uzlů
      * shout-and-echo (4m zpráv, 2diam(G) čas)
      * DFS (2m zpráv, 2m čas)
      * Awerbuch (4m zpráv, 4n−2 čas)
      * BFS:
        * Cheung’83 (<m>m^3</m> zpráv, m čas)
        * Cheung,Zhu’87 (<m>m^2</m> zpráv, <m>m^2</m> čas)
    * komunikace mezi uzly
    * volba vůdce
      * globální algoritmus (<m>\Omega (n \log n)</m> zpráv)


  * Další důležité parametry:
    * jednosměrnost/obousměrnost hran
    * (ne)znalost sítě/sousedů
    * existuje globální čas
    * očíslování hran
    * identifikace jednotlivých uzlů


===== Zdroje =====

  * slidy pa150 (podzim 2017)
  * http://statnice.dqd.cz/mgr-szz:in-pos:1-pos
  * http://statnice.dqd.cz/mgr-szz:in-tei:8-tei