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í.
Formálně se jedná o trojici , kde je součin stavů všech procesů a zpráv na linkách, a běh systému je posloupnost , kde , tedy 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
- pokud příjmu zprávu, přečtu příchozí hodnotu , porovnám se svojí a vyšší nechám. Tu následně inkrementuji.
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í
Konstruuje MST - (mininalni) kostru grafu.
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)))
Michal Trunečka
GHS: Marcel Poul