Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- mgr-szz:in-pos:4-pos [2019/06/19 10:07]
lachmanfrantisek
+++ mgr-szz:in-pos:4-pos [2020/04/12 16:56]
@@ Řádek 1: / Řádek 1: @@
-====== 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ů.
-  - Odeč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
-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

mgr-szz/in-pos/4-pos.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru