Přehled látky probrané na přednášce [Principy distribuovaných systémů](Principy%20distribuovaných%20systémů).

{{Not_complete}}

## Distribuovaný systém ##

Distribuovaný systém je takový systém propojení množiny nezávislých uzlů, který poskytuje uživateli dojem jednotného systému.

* distribuovaný OS
* vrstva middleware nad obyčejným OS

### Motivace ###

* ekonomika - lepší poměr výkon/cena
* výkon - technologické limity
* distribuovatelnost
* spolehlivost - výpadek jednoho uzlu
* rozšiřitelnost - snazší přidání uzlu

### Cíle ###

* transparentnost - přístupová, lokační, migrační, replikační, perzistentní, konkurenční, paralelismová
* přizpůsobivost - autonomie, decentralizované rozhodování, otevřenost, migrace procesů a prostředků
* spolehlivost - teorie: nespolehlivost jednoho serveru 1% => nespolehlivost čtyř serverů 0.01^4 = 0.00000001
* výkonnost - teorie: více uzlů -> vyšší výkon, praxe: výrazně nižší než lineární nárůst výkonu
* rozšiřitelnost - vyhnout se čemukoliv centralizovanému

## Architektury ##

* multiprocesory (sdílí paměť)
    * bus - synchronizace cache (max. 64 uzlů)
    * switched - crosspoint switch (kvadratický počet přepínačů), omega network (n log n)
* multicomputery (vlastní paměť, výrazně nižší komunikace)
    * bus - propojeny obyčejnou sítí
    * switched - mřížka, hyperkrychle
* hybridní - NUMA

## Komunikace ##

* absence sdílené paměti -> zasílání zpráv
* potřeba jednotného mechanismu komunikace pro celý systém (lokální, rychlá síť, vzdálená síť, ...)
* klient-server model, request/reply protokol - synchronní/asychronní čekání na požadavek/odpověď
* přímé zasílání, zasílání zpráv přes schránku
* přímé a nepřímé adresování (linky a porty)
* T/TCP - odlehčené protokoly pro lokální sítě, vyšší výkon, složitější zotavování z chyb
* ztráta zprávy -> typické řešení: potvrzování, timeout, opakování; ACK, NAK, AYA, IAA, CON, TRA, ...
* dlouhé zprávy -> burst (buřty) - potvrzuje se dávka paketů
    * pevné dávky - při vyšší zátěži sítě velká chybovost, při volné síti nízká výtěžnost
    * dynamické dávky - velikost na základě úspěšnosti předchozích přenosů
* idempotentní služba - nevadí opakované provedení služby, sečti 1+1
* sémantiky zpracování
    * exactly once (ideální, obecně nelze zajistit)
    * at-least-once
    * at-most-once
* spolehlivost serveru
    * ztratila se zpráva se žádostí
    * ztratila se zpráva s odpovědí
    * server je příliš pomalý nebo zahlcen
    * server nefunguje
* havárie klienta
    * exterminace - klient po zrození sám zruší službu
    * reinkarnace - klient nastartuje novou epochu, předchozí epochy server zruší
    * expirace - kvantum času

## RPC ##

(Remote Procedure Call)

* volání vzdálené služby stejné jako zavolání podprogramu
* síťová komunikace se před programátorem schová, zařídí ji překladač (u klienta i serveru)
* stub - vygenerovaný kód pro zavolání vzdálené služby, přilinkuje se při kompilaci klienta
* skeleton - vygenerovaný kód pro zpracování požadavku, přilinkuje se při kompilaci serveru

1. Klientova funkce normálním způsobem zavolá klientský stub
1. Stub vytvoří zprávu a zavolá jádro
1. Jádro pošle zprávu jádru počítače, kde běží server
1. Vzdálené jádro předá zprávu stubu serveru / skeletonu
1. Stub rozbalí parametry a zavolá server
1. Server zpracuje požadavky a normálním způsobem se vrátí do stubu
1. Stub zabalí výstupní parametry do zprávy a zavolá jádro
1. Jádro pošle zprávu klientovu jádru
1. Klientovo jádro předá zprávu stubu
1. Stub rozbalí výstupní parametry a vrátí se ke klientovi

* server se zviditelní na directory serveru
* použití IDL (Interface Description Language) - definice rozhraní, ze které se pak vygeneruje kód stubu a skeletonu
* problémy:
    * reprezentace dat (marshalling) - endiany, kódování, floaty
    * globální proměnné
    * ukazatele a dynamické struktury
    * předávání polí
    * variabilní parametry
    * odlišná sémantika při vzniku chyb, bezpečnost

## Skupinová komunikace ##

* jeden odesílatel, více příjemců
* atomicita - doručení všem nebo nikomu
* synchronizace - doručování od různých odesílatelů
    * neexistence sdílené paměti - zprávy
    * rozprostřená informace mezi několika uzly
    * rozhodování na základě lokálních informací
    * vyloučení havarijních komponent
    * neexistence společných hodin
* adresování - adresa skupiny, seznam příjemců, predikátová adresace (v kombinaci s předchozími)
* technicky - unicasty, multicast, broadcast
* uzavřené (koop. alg.) x otevřené skupiny (replikované služby)
* flat x hierarchická (přes koordinátora)
* doručovací protokol: 1. příjem, 2. doručení
* jeden uzel může být ve více skupinách, překrývající se skupiny, změna členství
* vnitřní uspořádání skupin - všechny procesy rovnocenné, hierarchické uspořádání, koordinátor skupiny

## Fyzické hodiny ##

* UTC
* požadovaná odchylka δ  ->  intervaly max. δ/2ρ ; ρ = míra přesnosti
* **Cristianův algoritmus** - jeden pasivní timeserver, periodické dotazy na aktuální čas, ošetření komunikační prodlevy
* **Berkeley algoritmus** - aktivní timeserver, periodicky se ptá ostatních na rozdíl času, počítá průměr, vrátí rozdíl
* **distribuovaný algoritmus** - resynchronizační intervaly pevné délky, broadcast, zahození extrémů, spočítání průměru
* **intervalový čas** - čas není okamži, ale interval; někdy nelze porovnat

## Logické hodiny ##

* důležité pořadí, nikoliv přesný čas, nekomunikující procesy nemusí být sesynchronizovány
* relace předchází

1. a, b události v jednom procesu, a se udělá před b, pak a->b
1. send(m)->recv(m)
1. tranzitivita

* jestliže a -> b, pak C(a) < C(b) (zúplnění pro C(a)=C(b) - byrokratické uspořádání podle PID)
* synchronizace logických hodin
    * odesílatel - ke zprávě přiloží svou časovou značku
    * příjemce - zvýší si svou značku, pokud je < než značka zprávy: T = max (T, Tm + 1)

## Kauzální závislost ##

1. jestliže ex.p: e1 ->p e2, potom e1 -> e2
1. send(m)->recv(m)
1. tranzitivita

* zpráva B je kauzálně závislá na A, jestliže A mohla ovlivit obsah B (jestliže byla na uzel doručena před odesláním B)
    * není důležité, zda byla zpráva ovlivněna, ale že mohla být ovlivněna

* konkurentní události - e1 není kauzálně závislá na e2 a e2 není na e1
* jestliže a -> b, pak C(a) < C(b), opačne ne

## Vzájemné vyloučení ##

* **centralizovaný algoritmus** - centralizovaný server s frontou, žádost / potvrzení / zamítnutí / uvolnění, problém s výpadkem serveru, klienta (starvation)
* **Lamportův algoritmus** - proces vyšle žádost a čeká až dorazí potvrzení od všech procesů a všechny žádosti v jeho frontě mají větší časovou značku, po uvolnění KS se posílá release zpráva
* **Ricart & Agrawala**
    * když chce proces vstoupit, pošle všem žádost se svou TM a čeká na všechna potvrzení
    * proces, který přijme žádost
        * nechce vstoupit ani není v KS -> pošle potvrzení
        * je v KS - zařadí žádost do fronty, po výstupu z KS pošle potvrzení všem ve frontě
        * není v KS, ale chce taky - pokud má jeho žádost nižší značku, zařadí do fronty a neodpovídá, jinak pošle potvrzení
* naivní volby - potřeba nadpoloviční většina hlasů, deadlock pokud 2 procesy dostanou stejně hlasů, posílá se žádost o hlasy, ostatní odpovídají, pokud jejich hlas je Available, po výstupu z KS se posílá release zpráva
* **Maekawa**
    * volební okrsky - pro vstup do KS je potřeba získat všechny hlasy z okrsku
        * každé 2 volební okrsky musí mít společného alespoň jednoho kandidáta
        * všechny okrsky stejně velké
        * každý proces ve stejném počtu okrsků
        * složitost O(K), K = velikost okrsku, cíl minimalizovat K
    * prevence deadlocku
        * p má volný hlas: potvrzení ACKr
        * p dal již hlas jinému procesu q s TSq < TSr: zařadit do fronty
        * p dal již hlas jinému procesu q s TSq > TSr: pošle zprávu REJECT procesu q
            * pokud již q je v kritické sekci (dostal všechny potřebné hlasy), odpoví až po opuštění kritické sekce
            * pokud q ještě nemá všechny hlasy, vrátí hlas procesu p a ten ho předá procesu r
* **token ring** - proces vlastnící peška může vstoupit do KS, problémem ztráta peška a výpadek procesu

## Volba koordinátora ##

* **bully algoritmus**
    * koordinátorem se má stát proces s nejvyšším ID
    * nějaký proces zašle zprávu procesům s vyšším ID
    * pokud přijde odpověď, vzdává se
    * pokud nepřijde nic, stává se novým koordinátorem a zašle zprávu o výsledku všem
    * při příjmu zprávy o volbě každý proces zašle žádosti všem vyšším procesům (volba ve dvou kolech)
    * při překročení timeoutu možnost více koordinátorů

* **invitation algoritmus**
    * nejsou požadavky na spolehlivost a dobu odezvy
    * koordinátor je vázán na skupinu, skupiny se mohou dle situace štěpit nebo spojovat
    * koordinátor pravidelně všem posílá AYC (AreYouCoordinator)
    * pokud déle nepřijde AYC od mého koordinátora, prohlásím se za koordinátora své skupiny
    * když koordinátorovi přijde AYC jiného koordinátora, spojí se do jedné skupiny toho vyššího, koordinátoři pošlou zprávu členům své původní skupiny ať se připojí do nové

* **kruhový algoritmus**
    * rozhodnu se volit, pošlu zprávu následníkovi
    * zpráva obsahuje čísla procesů - odesílatel a nejvyšší živý
    * když mi zpráva přijde po kruhu zpět, koordinátorem určím proces s nejvyšším ID a rozešlu všem zprávu
    * stačí znát následníky a mít možnost zjistit následníka nedostupného uzlu

## Doručovací protokoly ##

* globální uspořádání - zprávy jsou doručovány v pořadí odeslání, nelze bez existence globálních hodin
* sekvenční uspořádání - všechny uzly doručí zprávu ve stejném pořadí, nezávisí nutně na času odeslání
* **kauzální uspořádání**
    * kauzálně vázané zprávy ve správném pořadí, konkurentní zprávy v libovolném
    * dest(m) množina procesů, kterým je zaslána zpráva m
    * deliverp(m) je událost doručení zprávy m procesu p
    * m1 -> m2, pak pro každé p z průniku dest(m1) a dest(m2) platí deliverp(m1) ->p deliverp(m2)
* **total-order protokol**
    * všechny zprávy doručeny všem ve stejném pořadí
    * při příjmu zprávy potvrzení odesílateli TSAi
    * odesílatel po příjmu všech potvrzení odešle finalizační zprávu TSF = max(TSAi)
    * po příjmu finalizační zprávy příjemce doručí zprávy podle TSF

## Vektorové hodiny ##

* kauzální doručování
* vektor délky N (= počet uzlů), v každé složce čas daného uzlu
* když 2 vektory nejsou porovnatelné, jedná se o konkurentní zprávy
* před odesláním zvýším svůj TS o 1, ke zprávě přiložím vektor
* před přijetím čekám, než můj vektor bude větší nebo roven vektoru zprávy ve všech složkách kromě odesílatele (tam může být zpráva o jednu větši)
* po přijetí svoje zvýším na maximum (ze svého vektoru a vektoru zprávy) po složkách
* pro překrývající se skupiny: u zprávy posílám vektory všech skupin, kde jsem; při příjmu kontroluji kauzalitu i pro všechny skupiny, kde jsem (kromě té odesílatele, kde u něj může být větší o jedničku)

## Virtuální synchronie ##

Group view – množina uzlů ve skupině (též group membership, delivery list, etc). Značí se L (globální), L<sub>i</sub> (lokální verze procesu i), L<sup>x</sup> (verze pohledu x), L<sub>i</sub><sup>x</sup>

Algoritmus spolehlivého doručování je *virtuálně synchronní*, když:

1. všechny uzly ve skupině udržují stejný L
1. pokud je zpráva m odeslána skupině s L<sup>x</sup> před změnou na L<sup>x+1</sup>
    * buď m doručí všechny uzly z L<sup>x</sup> před provedením změny na L<sup>x+1</sup>
    * nebo žádný uzel z L<sup>x</sup>, který provede změnu na L<sup>x+1</sup>, zprávu m nedoručí

Přitom nemusí platit, že přijetí zprávy členem L implikuje doručení všem členům L (nespolehlivost, havárie odesílatele).

Když se uzly B a C dozvědí, že uzel A přestal být členem jejich skupiny, už od něj pak nemůžou přijímat skupinové zprávy.

## Spolehlivé kauzální doručování ##

* **flooding algoritmus**
    * při příjmu každé doposud nepřijaté zprávy ji každý uzel přepošle všem ostatním, spolehlivý, neefektivní
* **trans algoritmus**
    * p rozesílá Ack(m) když přijal m a všechny kauzálně předcházející zprávy
    * graf kauzality G celé skupiny, graf přijatých zpráv, ale ještě nestabilních Gp
    * ack_list, nack_list - seznam zpráv pro potvrzení / nepřijatých zpráv
    * undelivered_list – seznam přijatých, ale ještě nedoručených zpráv
    * implementace:
        * příjem potvrzení a výpočet vlastních potvrzení
        * detekce nepřijatých zpráv
        * ukládání zpráv a detekce stabilních zpráv
    * jestliže procesor havaruje, paměťová náročnost je neomezená :( -> potreba doplnit o změnu členství ve skupinách
* **transis algoritmus**
    * rozšíření trans o členství ve skupinách
    * při detekci havárie zpráva FAULT(q), při přijetí její přeposlání
    * zprávy kauzálně závislé na nějaké FAULT zprávě pozdržet do dalšího pohledu, pokud víc FAULT zpráv a zpráva závislá jen na jedné z nich, tak doručit
    * zprávy od odesílatele, který spadnul a které jsou kauzálně vázané na nějakou FAULT zprávu nebo jsou k ní konkurentní zahodit, doručit jen ty co byly odeslány před detekcí havárie
* **ISIS protokol**
    * maticové hodiny
    * každý proces zná vektor všech ostatních procesů: VTpi\[j] - co ví proces i o procesu j (pokud i=j tak je to počet odeslaných zpráv)
    * při příjmu zprávy od pi k pj: VTpj\[j]\[i]=VTm\[i], VTpj\[i]\[*]=VTm\[*]
    * členství ve skupinách - každý proces udržuje všechny nestabilní zprávy, při příjmu view change zprávy pošle všechny nestabilní a pak flush, po příjmu flush od každého procesu instaluje nový pohled (každý proces udržuje seznam havarovaných procesů, s každou zprávou se odesíla, zprávy od havarovaných procesů se zahazují)

## Ukončení distribuovaného procesu ##

* **Dijkstra-Scholten algoritmus**
    * strom
        * každý listový proces po ukončení pošle zprávu otci, ten propaguje výš po zjištění ukončení všech synů
        * signál o ukončení dostane iniciační proces od všech synů -> konec
    * DAG
        * na každé hraně deficit (#došlých zpráv - #signálů)
        * končící proces vyšle každým signálním kanálem tolik signálů, aby deficit byl všude 0
    * obecný graf
        * problém - nejsou listy
        * při výpočtu vytvoření kostry grafu - otec = uzel od kterého přišla první zpráva
        * algoritmus ukončení pro jeden proces:
            1. Poslat signál podél všech vstupních hran kromě hrany k otci
            1. Čekat na signál od všech výstupních hran
            1. Poslat signál otci

## Detekce globálního stavu ##

* množina událostí v systému E = {e}
* řez c je rozdělení E na Pc a Fc : Pc u Fc = E & Pc průnik Fc = 0
* konzistentní řez c : a -> b  &  a leží v Fc, pak b leží v Fc
* stav (distribuovaného) procesu je množina událostí, které se v procesu udály
* konzistentní stav S = Pc, kde c je konzistentní řez
* využití:
    * distribuovaná detekce deadlocků
    * distribuovaný garbage collection
    * detekce ukončení distribuovaných výpočtů
    * obecně detekce globálních vlastností

* stav uzlu = množina přijatých a odeslaných zpráv
* stav kanálu = množina zpráv, které byly kanálem odeslány, ale ještě nebyly doručeny

* **Distributed snapshot algoritmus**
    * iniciátor vyšle všem výstupním uzlům značku
    * při příchodu první značky ji rozešlu na výstupy a zapamatuji si svůj stav (přijaté a odeslané zprávy do tohoto okamžiku)
    * u příchozích kanálů, od kterých mi ještě značka nepřišla, si pamatuji příchozí zprávy (až do okamžiku, než mi i tímto kanálem přijde další značka)
    * zprávy mezi první značnou a další značkou z příchozího kanálu jsou stav toho kanálu
    * algoritmus končí po příchodu všech značek

## Distribuovaný konsensus ##

* problém 2 armád - početnější armáda musí zaútočit synchronizovaně, aby mohla vyhrát - řešení neexistuje

### Problém byzantských generálů ###

* uzly mohou havarovat a chovat se zákeřně
* C1: všichni loajální důstojníci vydají stejný rozkaz
* C2: je-li generál loajální, pak každý loajální důstojník vydá rozkaz generála
* 3 uzly, 1 zrádce - řešení neexistuje
* 4 uzly
    * zrádce generál
        * 2 stejné rozkazy - důstojníci se rozhodnou pro většinový rozkaz (C2)
        * 3 různé rozkazy - důstojníci se dohodnou, že generál je zrádce (C1)
    * zrádce důstojník - loajální důstojníci dostanou vetšinu správných rozkazů (C2)
* pro m zrádců existuje řešení pro n ≥ 3m+1 uzlů
* konsensus s nezfalšovatelnými zprávami - všichni přeposílají zprávu tak jak ji dostali, obsahuje i předchozího odesílatele -> loajální uzly se shodnou na majoritní nebo defaultní hodnotě

### Klasifikace problémů distribuovaného konsensu ###

* byzantský konsensus - iniciátorem rozesílaná hodnota
* konsensus - každý má svou iniciální hodnotu
* interaktivní konzistence - loajální se musejí shodnout na vektoru loajálních

## Distribuovaná sdílená paměť ##

### Konzistence bez SP ###

* **striktní**
    * všechny zápisy okamžitě všude viditelné
    * podmínka: musí existovat přesný globální čas -> v DS téměř nemožné
* **sekvenční**
    * výsledek stejný, jako by procesory běžely v nějaké sekvenci a každý procesor běžel podle programu 
    * může dát různé výsledky při spuštění stejného programu (není zaručeno zpoždění)
    * signatura = výstupy procesů v pevně daném pořadí, ne všechny odpovídají sekvenční konzistenci
    * dokázáno r+w>=t, čili pokud optimalizujeme pro čtení, zápis bude pomalý
    * snadno implementovatelné
* **kauzální**
    * kauzálně vázané zápisy (P1:W(x), P2:R(x),W(y)) musí být vidět ve stejném pořadí
    * implementace vyžaduje graf závislostí zápisů na čtení
* **PRAM**
    * zápisy jednoho procesu viděny v pořadí v jakém byly provedeny, zápisy různych procesů konkurenční
    * příklad se zabitím obou procesů
    * snadná implementace
* **slow memory**
    * zápisy jedním procesem do jednoho místa musí být viděny ve stejném pořadí

### Konzistence se synchronizační proměnnou ###

* předchozí modely příliš restriktivní, ne všechny aplikace vyžadují sledování všech zápisů, natož pak jejich pořadí, typická situace: proces v kritické sekci ve smyčce čte a zapisuje data
* řešení: nechat proces ukončit kritickou sekci a poté rozeslat změny ostatním
* speciální druh proměnné - **synchronizační proměnná** (synchronizační operace)

* **slabá konzistence (weak)**
    1. SP sekvenčně konzistentní
    1. na SP se sahá až skončí všechny předchozí zápisy
    1. na data se sahá až skončí všechny přístupy k SP

* **výstupní konzistence (release)**
    1. před přístupem ke sdílené proměnné musí být úspešně dokončeny předchozí Acq()
    1. před Rel() musí být ukončeny všechny předchozí zápisy a čtení procesu
    1. Acq() a Rel() musí být PRAM konzistentní
    * při správném párování Acq a Rel je výsledek ekvivalentní sekvenční konzistenci
    * eager release consistency - vše se propaguje po Rel(), optimalizace přístupové doby
    * lazy release consistency - vše se sosá před Acq(), optimalizace síťového provozu

* **vstupní konzistence (entry)**
    * přístup k datům a SP může být exkluzivní (RW) nebo neexkluzivní (RO)
    * každá SP má vlastníka (proces, který k ní naposledy přistupoval)
    * proces, který není vlastníkem, musí žádat o vlastnictví
    1. Acq() až po aktualizacích všech chráněných dat
    1. exkluzivní přístup k SP jen když nikdo jiný nepřistupuje ani neexkluzivně
    1. po exkluzivním přístupu si příští přístup musí vyžádat kopii od vlastníka

## Distribuované stránkování ##

* přístup k nenamapované stránce - přerušení, obsluha, načtení
* problémy:
    * replikace x konzistence - namapování read-only, synchronizační akce při zápisu, invalidace, aktualizace
    * nalezení stránky - broadcast, centralizovaný manager, replikovaný manager
    * správa kopií - broadcast, copyset
    * uvolňování stránek - které
    * falešné sdílení (nezávislá data na stejné stránce)
* **sekvenčně konzistentní**
    * pro zápis musím být jediný vlastník
* **kauzálně konzistentní**
    * vektorové hodiny pro stránky a procesy
    * při zápisu se zvýší TS stránky i procesu, při přenosu stránky se přiřadí procesu max, při zvýšení TS procesu se zneplatní stránky s nižším TS ve svém políčku

## Distribuované sdílené proměnné ##

* knihovny (typicky se SP, eliminace falešného sdílení, nepodporováno OS, závislé na jazyku, nutnost rekompilace, Munin -- read only, migratory (eager release), write-shared (dirty copy on write, po release se propaguje, při konfliktu dirty/dirty porovnání a případný pád)... konvenční sdílená (single writer, many readers -- jako distrib. stránkování, sekvenční konzistence)
* distribuované objekty (základní distribuovaný předek, pak potomci, class definition language -- automatické generování kódu, middleware: CORBA, Java RMI)

## Identifikace ##

* který objekt (identifikace), kde je (adresa), jak se k němu dostat (cesta)
* aktivní (vlastní kod - agenti, procesy) x pasivní (obsluhovány cizím kódem - souboru, kanály, ...)
* uživatelská jména (občas čitelné i pro člověka) x systémová (porty, desciptory, lidsky nečitelné)
* nestrukturovaná jména x strukturovaná jména (absolutní x relativní) x popisná (atribut = hodnota)
* dynamická jména (deskriptory otevřených objektů) x statická (jména souboru) + převody mezi nimi (freeze/melt)
* capability x ACL
* rozsah platnosti (local/global)

## Kapability ##

* jednoznačná identifikace objektu a přístupu (user nemůže měnit ani generovat)
* k jednomu objektu typicky více kapabilit (vlastník, písař, čtenář)
* +: snadný test oprávěnosti přístupu, každý správce prostředků může nadefinovat vlastní druhy práv
* -: těžko zjistit seznam oprávněných uživatelů, problém odejmutí práva, kontrola propagace
* kapabilita s podpisem - podpis vygenerován z identifikace objektu a práv, celé zašifrováno tajným klíčem (nutnost ochránit podpisovou funkci)
* kapabilita s redundancí
    * server port (dostatečně náhodné číslo) a ID objektu volně přístupné
    * práva + náhodně vygenerovaná hodnota, zašifrovaná práva a generovaná hodnota
    * služba serveru - vygenerování kapability s menšími právy

## Distribuovaná správa jmen ##

* namesever - publikace kapabilit, reg - žádosti o otevření kanálu
* spojení NS a FS - NS("a/b/c") -> FS("b/c") ...
* oddělený NS a FS - NS("a/b/c")="cap 1234" -> FS("cap 1234")
* adresáře - položky typu <jmeno,hodnota> (hodnota může být číslo, odkaz na trvalé objekty, na živé objekty, na adresáře)

## Detekce deadlocků ##

* detekce horší než lokálně
    * distribuovaný Wait-For-Graph (WFG)
    * každý existující deadlock je v konečném čase detekován, detekovaný deadlock musí existovat
* modely deadlocku - single, and, or, and-or, m out of n model
* **pštrosí algoritmus**
    * deadlock se neřeší, nechává se to na uživateli
* **centralizovaný algoritmus**
    * přenos informací - po každé změně, v intervalech, na požádání
    * kauzální doručování proti falešnému uváznutí
    * hierarchický - podřízení si svoje deadlocky řeší sami, nadřízení řeší problémy, které podřízení nevidí
* **path-pushing**
    * uzly spravují lokální kusy WFG
    * sousedním uzlům zasílání externí závislosti
    * phantom deadlock s cyklem mezi uzly?
* **edge-chasing**
    * pošlu zprávu všem, na které čekám, pokud se vrátí, pak deadlock
    * ale mezitím se to ale mohlo odblokovat (řešení - aging, overkill - zpráva zároveň hledá kandidáta)
* **diffusing computation**
    * nalezení cyklu v distribuovaném výpočtu = konec
* **detekce globálního stavu**
    * při příjmu značky proces zaznamená lokální WFG
    * existuje-li deadlock, tak je v konzistentím řezu
    * při příjmu značky uzel zaznamenává lokální WFG, externí závislosti poslány iniciátorovi

## Distribuované hashovací tabulky ##

* hašovací tabulky (pole) rozprostřeno mezi více uzly, každý uzel spravuje svoji část, rozdělení množiny klíčů mezi účastnické uzly
* uložení a vyhledání prvku znamená směrovat dotaz k uzlu, který spravuje danou oblast
* Peer-to-Peer sítě
    * strukturované - založené na DHT, mají pevnou strukturu, která je využívána ke směrování, směrovací tabulky, problémem připojení a odpojení uzlu
    * nestrukturované - záplavové hledání nebo náhodná procházka, problémem vyhledávání a směrování
* prvek S je přiřazen uzlu, jehož ID je nejblíže K(S) (funkce vzdálenosti)
* příslušný uzel je buď vlastníkem klíče anebo zná uzel, který je ke klíči blíže (všichni nemusí vědět o všech)
* odpojení uzlu - jeho oblast přejde na sousedy
* připojení uzlu - sousední uzly mu předají část své oblasti
* **Content-Addressable Network**
    * prostor klíčů je d-rozměrný kartézský souřadnicový systém
    * souřadnice bodů v prostoru představují klíče
    * prostor rozdělen na zóny, každá přísluší jednomu uzlu
    * každý uzel si drží ukazatele na sousední
    * připojení - uzel si zvolí bod v prostoru (vlastní ID), kontaktuje uzel dané oblasti, dohodne se s ním na rozdělení
    * odpojení - dohodne se s nějakým sousedem na spojení oblastí
* **Chord**
    * klíče jsou m-bitová čísla uspořádaná do kružnice
    * měří se vzdálenost dvou klíčů na kružnici ve směru hodinových ručiček
    * funkce *následník(K)* - vrací identifikátor uzlu, který je rovný nebo větší K
    * klíč k je uložen na uzlu *následník(k)*
* **Pastry**
    * klíče jsou m-bitová čísla rozdělená na sekvenci číslic o základu 2<sup>b</sup>
    * uzel směruje zprávu tomu uzlu, jehož id sdílí s klíčem prefix, který je nejméně o jednu číslici delší než prefix, který sdílí klíč s aktuálním uzlem
    * každý uzel má leaf set L = množina uzlů, které jsou numericky nejbližší jeho id
* **Kademlia**

## Vzdálené spouštění procesů ##

* nalezení volného počítače
* znalost vlastní zátěže
* spuštění vzdáleného procesu - transparentnost, přenesení kód a dat, vytvoření prostředí odpovídající domovskému PC (kontexty, systémová volání - přesmerovat x vzdálená)

1. volný počítač se zaregistruje do registru
1. domovský počítač žádá o nějaký volný registr
1. alokace procesoru na volném počítači
1. odregistrování volného z registru
1. nastavení prostředí
1. nastartování procesu
1. běh procesu
1. ukončení procesu
1. zpráva o ukončení domovskému

* pokud hostitel přestane být volný (uživatel se vrátil z hospody)
    * zabít proces
    * nechat doběhnout
    * čas na uložení
    * přemigrovat

## Alokace procesorů ##

* **up-down algoritmus**
    * koordinátor má tabulku s body pro každý procesor
    * při každé významné události (vytvoření procesu, ukončení, tik hodin) se pošle zpráva koordinátorovi
    * trestné body: + za proces jinde, - za neuspokojený požadavek, jinak směrem k nule
    * při uvolnění procesoru se vybere proces z fronty neuspokojených požadavků procesoru, který má nejméně trestných bodů
* **deterministický grafový algoritmnus**
    * minimalizace komunikace (toky v sítích)
    * nutnost znalosti komunikační složitosti
* **hierarchický algoritmus**
    * manažer skupin, při neúspěchu žádost vyšším místům
* **distribuovaný heuristický**
    * náhodné výběry cíle
* **bidding algoritmus**
    * procesy kupují výpočetní sílu, procesory ji nabízejí

## Migrace procesů ##

* motivace: vyvažování zátěže, shutdown, optimalizace
* korektnost - ostatní procesy nejsou migrací ovlivněny
* transparentnost - proces o migraci neví, nemusí spolupracovat, zůstanou zachovány vazby, není narušena komunikace
* problémy:
    * přenesení stavu a adres prostoru
    * komunikace mezi procesy
    * reziduální dependence
    * vícenásobná migrace
* přenos procesu:
    1. zmražení
    1. oznámení příjemci, alokace
    1. přenos stavu - registry, zásobník
    1. přenos kódu / adres prostoru
    1. přesměrování / doručení zpráv
    1. dealokace, vyčištění
    1. vazby na nové jádro, nastartování
    1. dokončení přenosu vazeb, dočištění
* přenos obsahu virtuální paměti
    * přenesení celé během zmražení procesu
    * pre-copying - přenos za běhu procesu, poté zmražení a přenos změněných stránek
    * copy on reference - stránka se přenese až když je vyžadována, na zdrojové stanici se smaže
* zprávy:
    * přesměrování - dočasné/trvalé
    * oznámení migrace všem potencionálním odesílatelům (musím je znát)
    * opakování (no ACK)
    * migrace kanálu

## Příklady systémů ##

* **DEMOS/MP** (83, migrace - cíl si proces tahá k sobě, nepřijaté zprávy přeneseny při migraci)
* **Charlotte** (nezustavaji residualni dependence, sběr statistiky, podle toho migrace, při migraci se kopírují jen hlavičky zpráv, zbytek se dotahává potom průběžně)
* **V** (migruje se "logical host" -- víc procesů + adresový prostor), precopy, broadcast nove adresy, stare zpravy zahozeny)
* **MOSIX** (Izrael) - rozsireni struktury procesu o cas od posledni migrace, cas na procesoru, pricinu migrace , statistiku IPC
* **Sprite** (kazdy proces ma domaci stanici, chtěli všechna volání jádra formardovat na pův systém -- reziduální dependence doma, jednotny prostor jmen, filesystem, global PID | virtualni pamet - kombinace presunu vseho na jednou a copy-on-reference, zmenene stranky na fileserver a ztoho se to postupne taha, zarizuje jadro OS, pre-migratio routine, encapsulation routine, de-encapsulation routine, post-migration routine)
* **T4** - konvencni OS, IPC, vzdalena komunikace, prenos protokoly, name services, vyssi distribuovane sluzby (zdilena pamet, migrace procesu load balancing

## Vyvažování zátěže (load balancing) ##

* úskalí:
    * jak porovnávat zátěž
    * volba migrujícího procesu
    * volba příjemce
* **párový algoritmus**
    * vytvoří se páry, které se vzájemně vyvažují
    * zatíženější procesor vybere proces podle míry vylepšení, zlepšení stavu = další přesouvání, jinak konec
* **vektorový algoritmus**
    * pevný vektor zátěže, první vždy vlastní zátěž
    * pošle první půlku náhodnému příjemci, došlá se proloží (princip zipu) s vlastní půlkou + update vlastní zátěže
    * provádí se periodicky
* **centralizované/hierarchické** vyvažovací algoritmy
    * koordinátor zná zátěže svých procesorů, velí
* **lokální algoritmus**
    * prahová hodnota, když přelezu, ptám se volných N počítačů, vyberu nejlepší odpověď
* **bidding algoritmus**
    * vyhodnocovací buňka - excitátory, inhibitory, procesy pravidelně vyhodnocovány (prahová hodnota)
    * výstup vyšší = OK, nižší = migrace, nula = nelze zmigrovat (inhibitor)
    * migrace - broadcast s žádosti o nabídku do vzdálenosti D, adresát proces ohodnotí, případně vrátí nabídku, při neúspěchu D++
* problémy - aktuálnost údajů, samotná zátěž algoritmu

## Distribuované souborové systémy ##

* distribuovaný FS x jednotný přístup k síťovým FS
* monolitický x oddělené adresářové a souborové služby
* stavový x bezestavový
* cache - v paměti serveru, v paměti klienta - v adresovém prostoru procesu, v jádře klienta, v cache manageru
* posloupnost bytů x záznamy x typovaný
* capability x ACL
* upload model (stáhnu a nahraju) x remote access model (otevře vzdáleně)
* kdy jsou vidět změny - ihned (centralizovaná sémantika) x po zavření souboru (relační sémantika)
* imutabilní soubory - nelze je měnit
* transakce
* adresářové služby - mapování uživatelských jmen na systémová, hierarchický systém souborů, linky, graf adresářů - mazání linků

## Replikace ##

* motivace: spolehlivost, dostupnost, výkon
* explicitní replika - uživatel sám udržuje konzistenci
* odložená replika - primární, akutalizace sekundárních
* skupinová komunikace - simultánní zasílání zpráv všem dostupným replikám
* aktualizační protokoly
    * primární replika - změny se provádí na jedné replice, ta se stará o aktualizaci ostatních
    * většinové hlasování - pro čtení/zápis potřeba získat většinu hlasů, při žádosti o čtení repliky posílají číslo své verze
    * vážené hlasování - read a write quorum, r+w>N
        * hlasování s duchy - server, který se účastní hlasování pro write při výpadku nějakého serveru

## Klientocentrické konzistenční modely ##

* **eventuální konzistence**
    * po skončení všech zápisů budou v konečném čase všechny repliky aktualizovány
    * při připojení k jedné replice uživatel vidí zprávy, po připojení k jiné replice některé zprávy (které již viděl) ještě nevidí
* **monotonic read**
    * po přečtení x všechna další čtení vrátí stejnou nebo novější hodnotu
    * při připojení k jiné replice uživatel vidí všechny dosud přečtené zprávy
    * při čtení serveru si server ověří podle read-setu aktuálnost údajů, klient si případně aktualizuje read-set
* **monotonic write**
    * zápis proměnné proveden před jakýmkoliv dalším zápisem té proměnné
    * CVS commit na různých replikách
    * při zápisu si replika ověří aktuálnost svých zápisů, chybějící doplní, po zápisu replika aktualizuje write-set
* **read your writes**
    * zápis proměnné proveden před jakýmkoliv jejím následným čtením
    * po aktualizaci webové stránky si neprohlížím kopie z cache
    * replika ověří aktuálnost svých zápisů
* **writes follow reads**
    * zápis proměnné po předchozím čtení této proměnné je proveden na stejné nebo novější hodnotě
    * zápis odpovědi do newsgroups se provede tam, kde je i přečtená hodnota
    * aktualizace repliky podle read-set, aktualizace write i read-setu klienta
* naivní implementace WID - globální identifikátor zápisu (kde, co), klient mé dvě množiny read-set, write-set
* problém: read-set a write-set neomezene rostou, řešení: implementovat je vektorovými hodinami

## Epidemické protokoly ##

* implementace eventuální konzistence
* ve VELMI rozsáhlých systémech (neřeší konflikty)
* Antientropie - server náhodně vybere jiný server k výměně dat
* gossiping - s pravděpodobností 1/k přestane infikovat
    * push (k sobe), pull (od sebe), kombinace (oba směry)
    * problém s mazáním dat - časově omezený certifikát smrti (záznam o smazání)