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

Distribuované systémy II: Synchronní a asynchronní systémy, problém shody. Volba v distribuovaném prostředí. Detekce ukončení.

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

V synchronním systému jsou jednotlivé uzly synchronizovány pomocí absolutního nebo logického času. Logický čas nemusí být shodný s absolutním, ale zajišťuje uspořádání dějů v celém systému. Příkladem je využití Lamportových časových známek (relace "událo se dříve než"): každý proces má vlastní logické hodiny, na událostech vrámci procesu je relace zajištěna triviálně, synchronizace probíhá jako součást zasílání zpráv mezi procesy (každý správa má časovou známku, pokud má příjemce menší čas, nastaví si čas na čas zprávy + 1). Dodatečnou podmínkou je aby dvě události nenastali ve stejný čas.

Jako příklad synchronzace absolutním časem je možné uvážiť NTP protokol.

V asynchronním systému jsou požadavky na časové uspořádání událostí mnohem slabší. Udáslosti probíhající na jednotlivých uzlech mají své uspořádání dle logických hodin uzlu a žádná zpráva nemůže být doručena dřív, než byla odeslána. Pořadí paralelních a na sobě nezávisících událostí nemusí být z pohledu systému vůbec stanoveno a pojem "doba trvání události" nemá prakticky žádný význam.

V asynchronním systému neexistuje horní hranice pro čas potřebný k jednomu kroku procesu nebo doručení zprávy a neexistují synchronizované hodiny.

===== Problém shody =====

Mějme systém o <math>n</math> procesech, každý má stav <math>1</math> nebo <math>0</math>. Každý proces může komunikovat s ostatníma, komunikace je spolehlivá ale může trvat libovolně dlouho. Proces buď funguje správně nebo se zhroutil. Cílem je aby se všechny procesy shodli na <math>1</math> nebo <math>0</math>. Musí existovat případ shody pro obě možnosti.

Silná shoda: výsledný stav musí být výchozím stavem alespoň jednoho procesu, žádné dva procesy se neliší ve výsledním stavu, každý proces se v konečném čase rozhodne pro nějaký stav a toto rozhodnutí je nerevokovatelné.

Slabá shoda: žádné dva procesy se neliší ve stavu, může dojít ke shodě na různých stavech, alespoň některé procesy se v konečném čase rozhodnou pro nějaký stav a toto rozhodnutí je nerevokovatelné.

V asynchronních systémech nelze v konečném čase dosáhnout shody. Není totiž možné rozlišit mezi pomalým a zhrouceným procesem. V praxi je toto překonáváno zavedením timeoutů a ignorováním/zabitím pomalých procesů.

Problém shody je řešitelný pro fault tolerantní broadcast:

==== Základní spolehlivý ====

Je ho možno zkonstruovat pomocí dvoubodových primitiv send a receive.

Vlastnosti:
  * správnost: pokud korektní proces <math>p</math> pošle zprávu <math>m</math>, tak ji také eventuálně doručí
  * shoda: pokud korektní proces <math>p</math> pošle zprávu <math>m</math>, tak ji eventuálně doručí všechny korektní procesy
  * integrita: zprávu <math>m</math> proces doručí tehdy a pouze tehdy, pokud byla dříve poslána nějakým procesem <math>p</math>

==== FIFO broadcast ====

Zprávy od jednoho vysílajícího musí být doručeny ve stejném pořadí, v jakém byly vyslány.

==== Příčínný (causal) broadcast ====

Jestliže odeslání zprávy <math>m</math> příčinně předchází zprávu <math>m'</math>, pak žádný správný proces nedoručí zprávu <math>m'</math> dříve než <math>m</math>.

==== Atomický broadcast ====

Zajišťuje úplné uspořádání na všech zprávách. Neexistuje v asynchronních systémech.

Praktickou realizací je Time Reliable Broadcast, který zavádí horní limit pro na čas do ktorého se zpráva musí doručit (dosažitelné v synchronních sítích).

==== Failure detectors ====

Zavádějí částečnou synchronizaci, aplikace se od nich dozví které procesy nekomunikují.

Vlasnosti failure detectoru:
  * každý proces má lokální failure detector modul
  * každý modul má seznam potenciálně zhroucených uzlů
  * lokální proces se ptá pouze lokálního modulu
  * moduly si mezi sebou vyměňují informaci
  * jsou nespolehlivé - potenciálně zhroucený uzl může být ze seznamu odstraněn
  * aplikace pracuje se specifikací, nikoliv implementací

Perfektní failure detector:
  * přesnost: žádný správný proces se nikdy nedostane do seznamu potenciálně zhroucených žádného FD
  * úplnost: každý zhroucený proces se jednou dostane do seznamu potenciálně zhroucených každého FD
  * vhodná abstrakce, ale těžce implementovatelné

Zeslabení perfektního detektoru:
  * úplnost: každý zhroucený proces je eventuálně zařazen do seznamu některých správných uzlů
  * přenost: některé správné procesy nejsou nikdy zařazeny do žádného seznamu
  * slabší přesnost: Existuje čas, po jehož uplynutí není žádný správný proces zařazen v seznamu potenciálně zhroucených žádného správného FD
  * nejslabší přesnost: Existuje čas, po jehož uplynutí nejsou některé správné procesy nikdy zařazeny do seznamu potenciálně zhroucených žádného FD

Problém shody je možné vyřešit použitím perfektního nebo i nejslabšího failure detektoru.
==== Malicious procesy ====

Existuje algoritmus (gossip news, drby), který dokáže dosáhnout shody pokud maximálně třetina procesů lže / je chybných.
===== Volba v distribuovaném prostředí =====

Volba (šéfa) v distribuovaném prostředí představuje proces označení jednoho nebo více uzlů konzistentním předvídatelným způsobem. Takhle označené uzly můžou převzít například roli synchronizátoru komunikace v celém prostředí nebo dělit práci mezi uzly.

Univerzální naivní algoritmus předpokládá existenci unikátních identifikátorů uzlů: každý uzl vyšle svoje ID a pak přeposílá dál všemi směry už je vyšší ID než jaké bylo naposledy obdrženo. Pokud uzl obdrží nižší nebo stejné ID jako naposledy, nic nedělá. Uzl se deaktivuje pokud dostane ze všech směrů stejné ID (a reaktivuje se, pokud dostane vyšší).

Efektivnější algortimy (u kterých je taky snadnější pozorování dokončení procesu) vyžadují jisté znalosti o distribuovaném prostředí:
  * uspořádání uzlů: kruh, úplný graf, mřížka, torus, n-rozměrná krychle, ...
  * směrovost komunikace: pokud uzl A může poslat správu B, tak komunikace je obousměrná pokud B může poslat správu A stejnou cestou
  * identifikace uzlů: zda má každý uzl jedinečný identifikátor
  * smysl pro směrování: zda je možné z identifikátoru uzlu odvodit směr, kterým má být zpráva odeslána aby dorazila co nejdříve

Pro příklad si vezměme algoritmus volby šéfa na jednosměrném kruhu pro uzly s identifikátory: každý uzl pošle svoje ID a přeposílá dál jen ID, které je vyšší než jaké obdržel doposud nebo jeho vlastní. Jakmile uzl obrží svoje ID, tak ho pošle znovu jako potvrzení volby a po opětovném přijmutí algoritmus končí. Algoritmus použije v nejhorším případě <math>n^2</math> zpráv.

Podobné algoritmy je možné využít za jistých okolností i k "diagnostice" prostředí - například nalezení mrtvé komunikace nebo mrtvého uzlu.

Tyhle algoritmy jsou využitelné hlavně v P2P sítích, které používají stromovou, kruhovou, mřížkovou nebo hybridní strukturu.

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

Ukončení nastává, když jsou všechny uzly systému pasivní (čekají na přijetí zprávy). Dijkstra-Scholten algoritmus má jednoho iniciátora, který buduje strom výpočtu (vnitřní uzly jsou procesy, listy jsou zprávy). Po spracování všech potomků (zpráv / podprocesů) proces upovědomí svého rodiče, že je pasivní a odpojí se. Nakonec obdrží iniciátor potvrzení od všech svých potomků a tím má potvrzeno, že byl výpočet ukončen.

====== Předměty ======

[[https://is.muni.cz/auth/predmety/predmet.pl?id=519447|FI:PA160]] Počítačové sítě a jejich aplikace II (jaro 2010), prof. RNDr. Luděk Matyska, CSc.

[[https://is.muni.cz/auth/predmety/predmet.pl?id=632486|FI:IV100]] Paralelní a distribuované výpočty (podzim 2011), doc. RNDr. Rastislav Královič, Ph.D.

====== Použitá literatura ======

-

====== Vypracoval ======

DevelX - Martin Jurča

stav - 95 %