Obsah

12. Paralelní a distribuované systémy

Paralelní a distribuované systémy - základní pojmy a principy operací, koncept paralelních a distribuovaných algoritmů, řešení typových synchronizačních úloh (vzájemné vyloučení, volba vedoucího prvku, byzantská dohoda apod.) v paralelním a distribuovaném prostředí.

Vypracování

Základní pojmy a principy operací

Síťový model paralelních systémů

Formálně se jedná o trojici (C,\mapsto,I), kde C = C_L^n \times M je součin stavů všech procesů a zpráv na linkách, a běh systému je posloupnost \gamma_0\mapsto\gamma_1\mapsto\gamma_3..., kde \gamma_0\in I, tedy I je množina počátečních stavů.

Vzhledem k asynchronnosti nelze přesně měřit čas výpočtu. Pro měření složitosti se algoritmů se používají dva způsoby:

Lamportovy hodiny

var\ \theta_p: integer \ \ \ init 0; (*\ an\ internal\ event\ *) \theta_p := \theta_p + 1; \ (*\ a\ send\ event\ *) \theta_p:=\theta_p+1; send\ <message, \theta_p>; \ (*\ a\ receive\ event\ *) - pokud příjmu zprávu, přečtu příchozí hodnotu \theta_p, porovnám se svojí a vyšší nechám. Tu následně inkrementuji.
receive\ <message, \theta> \theta_p:=max(\theta,\theta_p)+1;

Řešení typových úloh

Prohledávání, traverzování

Prohledávání: Na začátku je jeden iniciátor a je třeba informovat všechny. Traverzování je stejná úloha, ale v každém okamžiku je jen jeden „token“, tedy jen jeden proces je aktivní.

f(x)-traverzování

f(x)-traverzovací algoritmus je takový, který na objevení x vrcholů potřebuje max(f(x),n) zpráv.

Shout-and-echo

Prohledávání do hloubky (traverzování)

Awerbuch - vylepšené prohl. do hloubky

Volba šéfa

Na úplných grafech - jednoduchý algoritmus

Na úplných grafech - pokročilý algoritmus

Na jednosměrných kruzích (Chang Roberts)

GHS

GHS na wiki

Konstruuje MST - (mininalni) kostru grafu.

KKM

lecture03

Založeno na principu f(x)-traverzování, tokeny traverzují a nesou info o levelu. Kdyz se dva tokeny setkají, vznikne nový s vyšším lvl.
Počet zpráv = O(log_n(n + f(n)))

vzájemné vyloučení

Popis problému

Řešení pomocí tokenu

Ricart-Agrawala

S použitím tokenu

Byzantinská dohoda

Popis problému (Consensus problem)

Horní hranice chybných procesů

algoritmus EIG

Materiály

Vypracoval

Michal Trunečka
GHS: Marcel Poul