Z Studentská wiki

Okruhy k písemnému testu z Distribuovaných systémů. Test bude obsahovat 10 otázek a bude ohodnocen maximálně 20 body (místo původně uvažovaných 10 bodů), které se započítají do výsledné známky s koeficientem 1. Abyste získali nárok na zápočet, je třeba (kromě splnění dalších podmínek) napsat test alespoň na 10 bodů (nutná, nikoli postačující podmínka). Ve většině následujících úloh budete žádáni o nakreslení (vyplnění) časového diagramu.

Obsah [skrýt] 1 Architektury volně vázaných a těsně vázaných systémů, sběrnice a přepínače. 2 Náčrt přenosu zpráv v systému blokovaném/neblokovaném, s odpovědí/bez odpovědi, s vyrovnávací pamětí/bez vyrovnávací paměti, s potvrzením/bez potvrzení. 3 Náčrt přenosu pomocí RPC, synchronní RPC, asynchronní RPC, callback. 4 Nepřímá komunikace. 5 Mapování čísla služby na port (portmapper). 6 Sémantiky volání RPC. 7 Protokoly pro spolehlivý broadcast (ABCAST, CBCAST). 8 Fyzické hodiny, způsob synchronizace, Christianův algoritmus. 9 Fyzické hodiny, Berkeley algoritmus synchronizace. 10 Realizace CBCASTu pomocí vektorových logických hodin. 11 Určení konkurenčních událostí pomocí vektorových hodin. 12 Maticové hodiny. 13 Globální stav a Chandy Lamportův algoritmus. 14 Algoritmy výběru jednoho z N (Bully algoritmus, logický kruh, stromová struktura). 15 Algoritmy vzájemného vyloučení (centralizovaný, decentralizovaný s časovými značkami – Lamport, Richard+Agrawala, Makeawa). 16 Algoritmy vzájemného vyloučení – Suzuki+Kassami, LeLann, Raymond. 17 Transakce – uzamykání pomocí zámků (výlučné, sdílené) a časových značek. 18 Algoritmy ukončení transakcí (2 fázové, 3 fázové). 19 Detekce ukončení – algoritmus Dijkstra-Scholten. 20 Algoritmus shody na hodnotě a na vektoru hodnot, Byzantští generálové. 21 Detekce deadlocku v centralizovaném systému (WFG). 22 Metody předcházení deadlocku wait-die a wound-wait. 23 Detekce distribuovaného deadlocku Ho-Ramamoorthy (1 fáze, 2 fáze). 24 Konzistentnost – sekvenční, linearizovatelnost, příčinná, FIFO, slabá, uvolňovací, vstupní. 25 Konzistentnost konečná (eventual), monolitic read, monolitic write, read your writes, writes follow reads. 26 Replikace – metoda hlasování. 27 Distribuovaná sdílená paměť (DSM) – sekvenční čtení a zápis, zneplatnění dat, určení vlastníka dat. 28 Distribuovaný systém souborů (DFS) – sémantiky, transparentnost, bezestavový server. 29 Distribuované Hashovací tabulky - DHT – Chord, uložení a vyhledání informace. 30 Ověřování – MAC, digitální podpis, arbitrovaný digitální podpis, vzájemné ověřování (mezi členy, vzhledem k ověřovacímu serveru).

[editovat] Architektury volně vázaných a těsně vázaných systémů, sběrnice a přepínače.

? ¿

• těsně vázané (společná paměť) - mají společný stav
• volně vázané (komunikace posíláním zpráv) - neexistuje globalní stav

• přepínače

        MEM   MEM   MEM
  CPU ---|-----|-----|
         |     |     |
  CPU ---|-----|-----|
         |     |     |
  CPU ---|-----|-----|

• sběrnice

  CPU       CPU       CPU
 cache     cache     cache      paměť
   |        |         |          |
-----------------------------------

[editovat] Náčrt přenosu zpráv v systému blokovaném/neblokovaném, s odpovědí/bez odpovědi, s vyrovnávací pamětí/bez vyrovnávací paměti, s potvrzením/bez potvrzení.

[editovat] Náčrt přenosu pomocí RPC, synchronní RPC, asynchronní RPC, callback.

Při volání synchronního RPC se čeká na dokončení celého volání vzdálené prcedury. Při volání asynchronního se čeká pouze na potvrzení, že vzdálená procedura byla spuštěna. Musí tedy existovat mechanismus jak se klient dozví, že server již dokončil svou práci. Při ryzím asynchronním volání klient zadá serveru požadavek a až sám klient chce, tak si ho dalším voláním vyzvedne. V případě callbacku klient zadá požadavek serveru a pracuje dál. Sever pak sám zavolá vzdáleně metodu klienta a pošle mu výsledek. V tomto případě si tedy neříká o vysledek klient sám, ale server mu jej dopraví zpětným voláním. Prostě klient a server si vymění role.

[editovat] Nepřímá komunikace.

Producent a příjemce si vyměňují zprávy pomocí schránky (mailbox) také nazývane port. Schránka může být chápana jako objekt, do ktereho procesy vkládají zprávy a odkud mouhou být tyto zprávy procesy vyzvedávány.

Kazda schranka ma jedinecnou identifikaci. V tomto pripade muze proces komiunikovat s jinymi prostrednictvim mnozstvi ruznych schranek. Dva procesy mohou komunikovat pouze sdili-li spolecny mailbox. funkce send a receive maji nasledujici hlavicku:

• send(A, zprava) - Posli zpravu do schranky A.
• receive(A, zprava) - Prijmi zpravu ze schranky A.

V tomto pripade ma komunikacni spojeni nasledujici charakteristiky:

• Spojeni je navazano mezi dvema procesy pouze maji-li sdilenou schranku.
• Spojeni muze byt navazano mezi vice nez dvema procesy.
• Mezi kazdym parem komunikujicich procesu muze byt navazano vice spojeni; kazde spojeni vyzaduje jednu schranku.
• Spojeni muze byt nesmerove nebo dvousmerove.

Druhym typem jsou schranky ve vlastnictvi operacniho systemu. OS provadi mechanismy vedouci k:

1. Vytvoreni nove schranky;
2. Poslani a prijeti zpravy prostrednictvim schranky;
3. zruseni schranky.

Proces, ktery schranku vytvoril je implicitne jejim vlastnikem a jedine on muze do schranky zasilat zpravy. Vlastnictvi, stejne jako pravu zapisu do schranky muze byt udeleno jinemu procesu prostrednictvim preruseni.

Procesy mohou sdilet schranku prostrednictvim techniky tvorby procesu. Pokud proces P vytvori schranku A a posleze vytvori novy proces Q, potom oba procesy P a Q sdili schranku A.

[editovat] Mapování čísla služby na port (portmapper).

RPC server musí nějakým způsobem informovat své okolí o tom, které služby a jakým způsobem poskytuje. Tuto činnost provádí tzv. portmapper, což je jakýsi správce RPC. Portmapper je démon, který běží na portu TCP/IP 111 a je typicky umístěn v /sbin/portmap. Seznam služeb a jejich číselných označení je umístěn v souboru /etc/rpc, který je s případnou nově nabízenou službou nutno ručně editovat. Otázkou zůstává, jak jsou RPC službám přidělovány porty. Tato situace je řešena při každém startu portmapperu a porty jsou službám, které běží pod jeho správou, přiděleny víceméně náhodně podle toho, které porty jsou v daný okamžik dostupné. Může se tedy lehce stát, že jednou bude mít služba port 256 a po rebootu stroje např. 815. Klienti tyto informace samozřejmě potřebují zjistit, takže před vlastním použitím služby zašlou dotaz na portmapper s požadavkem na informace o dané službě.

Jednoznačně přidělený identifikátor na portmapperu se skládá ze tří složek:

• Z čísla programu (program number), které souhrnně identifikuje skupinu procedur, zajišťujících určitou službu. Například všechny vzdálené procedury, které jsou používány v rámci implementace protokolu NFS, tvoří jednu takovouto skupinu, a mají tudíž přiřazeno jedno číslo programu (pro NFS konkrétně 10003).
• Z čísla procedury (procedure number), které jednoznačně identifikuje příslušnou proceduru v rámci její skupiny.
• Z čísla verze (version number).

Společnosti Sun, jako globálnímu koordinátorovi, stačí pečovat pouze o jednoznačnost první složky. Kdokoli, kdo se rozhodne implementovat pomocí mechanismu RPC nějakou novou službu, si od firmy Sun může vyžádat jednoznačné číslo programu. Jednotlivým procedurám, které pak pro zajištění své služby vytvoří, již přiděluje druhou složku (číslo procedury) sám. Konečně třetí složka vychází vstříc postupnému vývoji jednotlivých služeb, který dává postupně vznikat novým a novým verzím. Díky této složce identifikátoru vzdálené procedury je pak možné průběžně implementovat nejnovější verze, ale současně s tím zabezpečit i zpětnou kompatibilitu a podporovat i verze předchozí.

[editovat] Sémantiky volání RPC.

Právě jednou

Odeslání požadavku právě jednou. Pokud server vypadne, klient nemá možnost zjistit, zda-li byla operace provedena.

Neomezené čekání

Klient odešle požadavek jednou. Pak čeká nekonečně dlouho, dokud nepřijde potvrzení.

Opakované volání

Nejvýše jednou

Vykoná se pouze jednou. Pokud server vypadne, nemá klient možnost zjistit zda byla operace provedena. ? Vypadá stejně jako možnost právě jednou ¿

Alespoň jednou

Volá se opakovaně dokud klient nedostane odpověď.

• Operace se může provést i vícekrát. Nežádoucí.
• Idempotentní operace - Provádím takové operace, u kterých opakované volání bude mít týž výsledek. Například inkrementaci záznamu provedu tak, že záznam přečtu, u sebe zvýším jeho hodnotu a pak tuto hodnotu zapíši.

Získání výsledku poslední prováděné operace

Jednou nebo vůbec

transakce

[editovat] Protokoly pro spolehlivý broadcast (ABCAST, CBCAST).

ABCAST

Uspořádaný broadcast.

1. Iniciátor pošle zprávu s kódem operace všem členům skupiny.
2. Všechny uzly odpoví s časovou značkou = návrh času na provedení operace.
3. Iniciátor vybere nejvyšší hodnotu a odešle všem uzlům.
4. Jednotlivé uzly obsahují frontu požadavků, které se mají provést (před provedením musí být potvrzeny všemi uzly) -> ve všech uzlech se provedou operace ve stejném pořadí, ale ne ve stejné době.

CBCAST

Protokol s oslabeným uspořádáním.

1. Incoming vector timestamp is compared to current timestamp.
2. If conditions for delivery to process not met, then message placed on holdback queue.
3. When an incoming message is delivered, the timestamp is updated by the merge.
4. Examine all messages in the holdback queue to see if they can be delivered.
5. CBCAST requires reliable delivery.

[editovat] Fyzické hodiny, způsob synchronizace, Christianův algoritmus.

A clock synchronization algorithm used to synchronize the time on a machine with a remote time server. This is a very straightforward algorithm, and is quite easy to understand.

The procedure:

1. A process p requests the time in a message mr and receives the time value t in a message mt.
2. t is inserted in mt at the last possible point before transmission from the server S.
3. Tround = Time(send mr) + Time ( receive mt) = (1-10)*10-3 seconds on a LAN.
4. min = minimum queueing time for S.

The earliest point at which S could have placed the time mt was min after p dispatched mr. The time by S’s clock when the message is received by P is in the range t + min < p < t + Tround - min. The total width of this range is Tround - 2*min. This gives an accuracy of (Tround / 2 – min). If all of that made absolutely no sense to you, here’s a much simpler (but far less rigorous) explanation. Basically, the client sends a request for the current time to the time server. When it receives the response, it finds the transmission delay (time between the request being sent and the response being received), divides that in half, and adds that to the time received back from the server. The idea is to eliminate the inaccuracy caused by network delays. This assumes that the link is equally fast both ways, which may not always be the case. But as with any algorithm, you have to make tradeoffs.

[editovat] Fyzické hodiny, Berkeley algoritmus synchronizace.

Unlike Cristian's algorithm the server process in Berkeley algorithm, called the master periodically polls other slave process. Generally speaking the algorithm is as follows:

1. A master is chosen via an election process such as Chang and Roberts algorithm.
2. The master polls the slaves who reply with their time in a similar way to Cristian's algorithm.
3. The master observes the round-trip time (RTT) of the messages and estimates the time of each slave and its own.
4. The master then averages the clock times, ignoring any values it receives far outside the values of the others.
5. Instead of sending the updated current time back to the other process, the master then sends out the amount (positive or negative) that each slave must adjust its clock. This avoids further uncertainty due to RTT at the slave processes.

Je potřeba například u databází, kde se nesmí skákat v čase. Klienti dostanou pouze pokyn ke zpomalení hodin a tím se časem dostanou na správný čas.

[editovat] Realizace CBCASTu pomocí vektorových logických hodin.

• Událost A kauzálně předchází B <=> timestamp A je ve všech prvcích menší než B
• Událost A nemá kauzální vztah k B <=> timestamp A není porovnatelný s B

TODO

[editovat] Určení konkurenčních událostí pomocí vektorových hodin.

• 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

TODO

[editovat] Maticové hodiny.

Maticové hodiny – každý proces si udržuje vektor s odeslanými zprávami (sem si uklada, pri prijeti nejake dalsi zpravy od prijemce cas odelsani posledni zpravy od nej, kterou prijemce odstal), a zároveň vektory co mu došly od všech ostatních. Z toho zjistí které zprávy už mají všichni (a jsou stabilní).

ISIS protokol - Zaručení synchronie: když se proces dozví o novém pohledu, rozešle všechny nestabilní zprávy a potom potvrzení instalace (flush message), když pak dostane flush od každého procesu, může nový pohled nainstalovat. Každý proces si udržuje seznam "havarovaných" procesů dle aktuálního pohledu, ten se posílá se zprávami a sjednocuje při příjmu. Zprávy od havarovaných se zahazují.

[editovat] Globální stav a Chandy Lamportův algoritmus.

Algoritmus detekce globálního stavu 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 Algoritmus:

1. Iniciátor vyšle všem výstupním uzlům značku
2. Příjem první značky:
   1. Uzel si zapamatuje poslední přijaté a odeslané zprávy = stav uzlu
   2. Stav všech příchozích kanálů označí za prázdný
   3. Vyšle všem výstupním uzlům značku
3. Příjem zpráv od uzlů, od kterých ještě nepřišla značka:
   • Zapamatuje si čísla zpráv
4. Příjem značek od dalšího uzlu:
   • Stav kanálu = zaznamenané zprávy došlé od uzlu první a touto značkou
5. Konec algoritmu po přijmutí všech značek

Zaznamenané stavy uzlů a kanálů definují konzistentní stav systému

Chandy, Lamport '85

[editovat] Algoritmy výběru jednoho z N (Bully algoritmus, logický kruh, stromová struktura).

Bully algoritmus

• proces P pošle zprávu ELECTION všem procesům s vyšším PID
• na tuto zprávu se odpovídá zprávou OK
• pokud nikdo neodpoví, pak P vyhrává, má tedy nejvyšší PID
• pokud odpoví procesy s vyšším PID, práce procesu P končí, nemůže být koordinátor
• proces co vyhrál rozešle všem zprávu COORDINATOR a dá tak najevo, že vyhrál

Logický kruh

• procesy jsou supořádány v kruhu podle PID
• proces, který zjístí, že koodrinátor nereaguje pošle zprávu se svým PID následovníkovi
• ten do ní přídá svoje PID atd.
• jakmile zpráva dojde k procesu, který volbu začal, tak tento proces vybere nejvyšší PID
• po vybrání nejvyššího PID se nechá kruhem kolovat zpráva COORDINATOD s vybraným PID

Strom (nepovedlo se mi nikde najít přesne ale aspoň něco)

• iniciátor volby rozešle WAKEUP zprávu, čímž dá najevo, že začíná volba
• volit se začíná od listů, každý list vyšle svoje PID k rodiči
• jakmile rodiči dojdou všechny PID potomků, vybere min(PID všech poromků, PID rodiče ) a ten pošle rodiči
• nakonec ke kořeni vybublá nějnižší PID ve stromu a ten se stává koordinátorem

[editovat] Algoritmy vzájemného vyloučení (centralizovaný, decentralizovaný s časovými značkami – Lamport, Richard+Agrawala, Makeawa).

Lamport

• Předpokládá obousměrné FIFO kanály mezi procesy.
• Každý proces udržuje vlastní frontu požadavků.
• Používá časových značek k uspořádání požadavků.
• Vyžaduje 3(n-1) zpráv.
• Probíhá ve třech fázích - Požadavek (req), Potvrzení (ack), Uvolnění (rel).

1. Proces P požaduje zdroj posláním požadavku do všech procesů zasláním zprávy req.
2. Při příjmu požadavku je požadavek zařazen do fronty požadavků uspořádané dle časových značek, poslání zprávy ack.
3. Ukončení zpracování požadavku – odstranění požadavku z fronty a poslání zprávy rel ostatním procesům.
4. Přijetí zprávy rel od procesu P – odstranění požadavku procesu P z fronty.
5. Povolení zpracování požadavku – požadavek je na prvním místě ve frontě a je potvrzen ostatními procesy.

Zkráceně: Proces vyšle žádost o přístup do kritické sekce a čeká, až dorazí odpovědi od všech procesů, pokud všechny žádosti v jeho frontě mají větší časovou značku, může vstoupit do KS.

Richard Agrwala

Když chce proces vstoupit do kritické sekce, zašle žádost s časovou značkou ostatním procesům a čeká na všechny došlé odpovědi s potvrzením možnosti vstupu. Když proces přijme zprávu se žádostí, pak:

1. Jestliže příjemce není v kritické sekci a ani do ní nechce vstoupit, pak pošle zpět zprávu s potvrzením.
2. Jestliže je příjemce v kritické sekci, pak neodpovídá, požadavek si zařadí do fronty.
3. Jestliže příjemce ještě není v kritické sekci, avšak chce do ní vstoupit, porovná časovou značku přijaté žádosti s časovou značkou vlastní žádosti. Pokud vlastní žádost má nižší časovou značku, tj. byla vyslána dříve, pak neodpovídá a zařadí žádost odesílatele do fronty. V opačném případě, kdy byla žádost odesílatele odeslána dříve, pošle příjemce zpět zprávu s potvrzením.

Makeawa

1. Vzájemné vyloučení zajištěno vytvořením hlasovacího quora.
2. Vyžaduje souhlas (2N)−1  procesů.

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36

[editovat] Algoritmy vzájemného vyloučení – Suzuki+Kassami, LeLann, Raymond.

LeLann (logický kruh)

V kruhu obíhá pešek. Kdo má peška, může vstoupit do kritické sekce. Kritické sekce se proces vzdá kdy chce, pak pošle peška dál. Pokud nechce proces do kritické sekce, prostě přepošle peška.

Suzuki-Kasami (broadcast)

Metoda využívá distribuci pověření mezi jednotlivými procesy. Každý uzel udržuje celočíselné pole největších sekvenčních čísel obdržených od jednotlivých procesů. Proces posílá ostatním pověření, které obsahuje frontu požadavků a vektor LN posledních požadavků jednotlivých procesů. Pokud chce proces vstoupit do kritické sekce a nemá pověření. Zvýší vlastní TS ve vektoru TS a pošle ostatním požadavek (i, TSi). Pokud proces přijme požadavek od i-tého procesu. Nastaví položku vektoru TS[i] na maximum. Jestliže má pověření a TS[i]=LN[i]+1, pošle pověření do Pi. Pokud Pi opouští kritickou sekci: Nastaví LN[i] v pověření na vlastní vektor časových značek. Frontu v pověření nastaví tak, že do ní zahrne všechny procesy, které v ní nejsou a mají časovou značku požadavku o 1 vyšší než je časová značka v pověření. Pověření se pošle prvnímu ve frontě (ten se z fronty odstraní). Fronta je posílána v pověření.

Raymond

Pracuje na bázi předávání pověření. Proces udržuje frontu požadavků na pověření od procesů nižších úrovní. Požaduje-li vstup do KS a fronta je prázdná, posílá požadavek nadřazenému a řadí se do fronty. Požaduje-li podřízený proces vstup do CS, předá mu pověření nebo jej zařadí do fronty. Obdrží-li pověření, předá ho prvnímu ve frontě.

[editovat] Transakce – uzamykání pomocí zámků (výlučné, sdílené) a časových značek.

[editovat] Algoritmy ukončení transakcí (2 fázové, 3 fázové).

[editovat] Detekce ukončení – algoritmus Dijkstra-Scholten.

[editovat] Algoritmus shody na hodnotě a na vektoru hodnot, Byzantští generálové.

Tři nebo více generálů se potřebuje vzájemně seznámit se svými záměry. Jeden nebo více generálů může být zrádce, který dává chybné informace. K řešení tohoto problému používají protokol. Každý z generálů posílá svou informaci ostatním (předpokládáme spolehlivou komunikaci). Jakmile generál shromáždí všechny hodnoty, pošle vektor hodnot ostatním generálům. S využitím hlasovacího mechanizmu může každý generál získat správné hodnoty. Problém není řešitelný pro N≤3. Pro k zrádců je třeba 2k+1 loajálních generálů. Problém nemůže být řešen pokud chybný proces lže konzistentně. Lze použít zabezpečení zprávy (šifrování, digitální podpis).

[editovat] Detekce deadlocku v centralizovaném systému (WFG).

• Každý uzel posílá zprávu do hlavního detekčního uzlu.
• Hlavní detekční uzel vytváří a analyzuje WFG.
• Pokud je deadlock detekován, hlavní detekční uzel řídí odstraňování deadlocku.

• AND modelu požadavků požaduje aby všechny právě požadované zdroje byly přiděleny jako podmínka pro odblokování výpočtu. V tomto modelu je detekce cyklu postačující podmínkou pro detekci deadlocku.
• OR model požadavků dovoluje vytvářet při výpočtu požadavky na více různých zdrojů a odblokování výpočtu je možné pokud je alespoň jeden uspokojen. V tomto modelu je cyklus podmínkou nutnou. Knot je podmínkou postačující. (Knot (uzel): podmnožina orientovaného grafu taková, že počínajíc z libovolného uzlu podmnožiny je nemožné opustit knot po hranách grafu.)

[editovat] Metody předcházení deadlocku wait-die a wound-wait.

Mějme dva procesy, starší proces OLD a mladší proces YOUNG.

Wait-die

• Pokud proces YOUNG vlastní zdroj a chce ho OLD, tak čeká, než se YOUNG vzdá zdroje.
• Pokud proces OLD vlastní zdroj a proces YOUNG ho chce, pak je proces YOUNG zabit.

Wound-wait

• Pokud proces YOUNG vlastní zdroj a chce ho OLD, pak je YOUNG preemptivne odstaven.
• Pokud proces OLD vlastní zdroj a YOUNG ho chce, pak proces YOUNG čeká.

[editovat] Detekce distribuovaného deadlocku Ho-Ramamoorthy (1 fáze, 2 fáze).

1 fázový

Každý uzel udržuje dvě tabulky. Stavovou tabulku zdrojů, stavovou tabulku procesů. Transakce v tabulce zdrojů mohou být uzamčeny nebo čekají na zdroje. Tabulka procesů je tvořena zdroji v uzamčené transakcemi nebo čekající v transakcích. Řídicí uzel periodicky soustřeďuje tyto tabulky ze všech uzlů. Z transakcí vytváří WFG společný pro obě tabulky. Nalezení cyklu znamená deadlock.

2 fázový

Každý uzel si udržuje stavovou tabulku o přidělených (uzamčených) zdrojích a čekajících procesech. Řídicí uzel se periodicky dotazuje na obsah těchto tabulek ve všech uzlech. Tabulky jednoho uzlu stahuje najednou (atomická operace). Řídicí uzel vytváří WFG, analyzuje jej, hledá smyčky a pokud je najde, pak hledá řešení. Nutnou podmínkou pro detekci deadlocku je nalezení smyčky, pokud najde smyčku, požádá znovu o zaslání tabulek z ostatních uzlů pokud je opět detekován cyklus, může se jednat o deadlock může se jednat i o falešný (false) nebo zdánlivý (phantom) deadlock.

[editovat] Konzistentnost – sekvenční, linearizovatelnost, příčinná, FIFO, slabá, uvolňovací, vstupní.

Striktní konzistentnost

• Definice - jakékoliv čtení datové položky X vrací hodnotu odpovídající výsledku poslední operace zápisu X.
• Definice implicitně předpokládá existenci absolutního globálního času. Je přirozeně dostupná v jednoprocesorových systémech, ale neimplementovatelná v distribuovaných systémech.

	Striktně konzistentní paměť		Paměť, která není striktně konzistentní
P1:	W(x)a		W(x)a
P2:		R(x)a		R(x)NIL	R(x)a

Linearizovatelnost a sekvenční konzistentnost

Sekvenční konzistentnost: Výsledek jakéhokoliv provádění je tentýž, jako kdyby operace čtení a zápisu všech procesů nad datovou pamětí byly prováděny v nějakém sekvenčním pořadí a operace všech individuálních procesů se jeví v téže sekvenci, ve které je specifikována jejich programem. Všechny procesy vidí totéž pořadí operací zápisu.

	Sekvenčně konzistentní paměť					Paměť, která není sekvenčně konzistentní
P1:	W(x)a					W(x)a
P2:		W(x)b					W(x)b
P3:			R(x)b		R(x)a			R(x)b		R(x)a
P4:				R(x)b	R(x)a				R(x)a	R(x)b

Příčinná konzistentnost

• Vyžaduje úplné uspořádání pouze pro operace zápisu, které jsou vzájemně závislé.

1. Operace read je příčinně vztažena k operaci write, pokud write zapisuje data, která read čte.
2. Operace write je příčinně vztažena k operaci read, která nastane dříve než write v tomtéž procesu.
3. Jestliže read závisí na write_1 a write_2 na read, pak také write_2 závisí na write_1.

• Nutné podmínky

1. Zápisy, které mají potenciálně příčinný vztah musí být viděny všemi procesy ve stejném pořadí.
2. Konkurentní zápisy mohou být viděny v různých pořadích v různých pořadích v různých procesech.

	Dobře v příčinné. Špatně v striktně, nebo sekvenčně.						Špatně v příčinné					Správná v příčinné
P1:	W(x)a			W(x)c			W(x)a					W(x)a
P2:		R(x)a	W(x)b					R(x)a	W(x)b				W(x)b
P3:		R(x)a			R(x)c	R(x)b				R(x)b	R(x)a			R(x)b	R(x)a
P4:		R(x)a			R(x)b	R(x)c				R(x)a	R(x)b			R(x)a	R(x)b

FIFO konzistentnost (také PRAM nebo Pipeline RAM)

1. Zápisy od jednoho procesu jsou ostatními procesy viděny v tomtéž pořadí, ve které byly vyslány.
2. Zápisy od různých procesů mohou být viděny různými procesy v různém pořadí.

	Platná sekvence událostí FIFO konzistentnosti
P1:	W(x)a
P2:		R(x)a	W(x)b	W(x)c
P3:					R(x)b	R(x)a	R(x)c
P4:					R(x)a	R(x)b	R(x)c

Slabá (weak) konzistentnost

Synchronizační proměnné zajišťují konzistentnost skupiny operací (transakcí), ne individuálních zápisů a čtení.

1. Přístup k synchronizačním proměnným spojeným s datovou pamětí je sekvenčně konzistentní.
2. Není dovoleno, aby byla nad synchronizační proměnnou provedena operace zápisu, dokud není na všech místech dokončena předchozí operace zápisu.
3. Není dovolena operace čtení nebo zápisu nad daty, dokud nejsou provedeny všechny předchozí operace nad synchronizačními proměnnými.

	Platná posloupnost pro slabou						Neplatná pro slabou
P1:	W(x)a	W(x)b	S				W(x)a	W(x)b	S
P2:				R(x)a	R(x)b	S				S	R(x)a
P3:				R(x)b	R(x)a	S

Uvolňovací konzistentnost

1. Před provedením operace čtení nebo zápisu nad sdílenými daty musí být úspěšně ukončeny všechny předchozí požadavky.
2. Před provedením požadavku uvolnění (release), musí být ukončeny všechny předchozí čtení a zápisy daného procesu.
3. Přístupy k synchronizačním proměnným jsou FIFO konzistentní (sekvenční konzistentnost není požadována).

	Platná posloupnost pro uvolňovanou konzistentnost
P1:	Acq(L)	W(x)a	W(x)b	Rel(L)
P2:					Acq(L)	R(x)b	Rel(L)
P3:								R(x)a

Vstupní (entry) konzistentnost

1. Získání přístupu k synchronizačním proměnným vztaženým k procesu je požadováno teprve tehdy, když jsou provedeny všechny opravy chráněných sdílených dat vztažených k tomuto procesu.
2. Před povolením režimu výlučného přístupu k synchronizační proměnné procesem nesmí mít jiný proces přístup k této synchronizační proměnné ani v sdíleném (nevýlučném) režimu.
3. Po ukončení režimu výlučného přístupu k synchronizační proměnné nemůže být proveden sdílený přístup k této synchronizační proměnné jinými procesy dokud není vzat na zřetel vlastníkem proměnné.

Metody bez synchronizačních proměnných

Přísná, Linearizovatelnost, Sekvenční, Příčinná, FIFO

Metody se synchronizačními metodami

Slabá, Uvolňující, Vstupní

[editovat] Konzistentnost konečná (eventual), monolitic read, monolitic write, read your writes, writes follow reads.

Konečná (eventual) konzistentnost

Po nějaké době vidí všechny repliky všechny opravy a přechází do konzistentního stavu (jsou postupně konzistentní). Tento typ konzistentnosti je znám jako možná (konečná) konzistentnost.

Monolitic read - write

Nepožaduje se stejný pohled na data pro všechny klienty, ale aby se jevily data konzistentně jednomu klientovi s ohledem na jeho operace.

Read your writes

TODO

Writes follow reads

TODO

[editovat] Replikace – metoda hlasování.

Mějme N úložišť, odkud budeme data číst a kam je budeme ukládat. Zároveň je dájno, že u každého uloženého souboru je zapsána i jeho verze. Pokud chceme do úložišť zapsat, musíme získat alespoň N/2+1 hlasů, že je to možné, tedy nadpolovičí většinu. To samé v případě zápisu. Pokud tendy čteme soubor a dostaneme N/2+1 odpovědí, pak to znamená, že čteme nejaktuálnější verzi souboru, protože N/2+1 jeho kopií muselo být předtím zapsáno do úložišť.

[editovat] Distribuovaná sdílená paměť (DSM) – sekvenční čtení a zápis, zneplatnění dat, určení vlastníka dat.

[editovat] Distribuovaný systém souborů (DFS) – sémantiky, transparentnost, bezestavový server.

Transparentnost přístupu

Klienti nevnímají, že soubory jsou na vzdálených serverech.

Transparentnost umístění

Konzistentní prostor jmen souborů (stejně označení lokální i vzdálené soubory).

Transparentnost souběžných přístupů

Koherentní (vnitřně provázané) modifikace.

Transparentnost chyb

Schopnost klienta fungovat správně i po chybě serveru.

Heterogenita

Schopnost zajistit operace se soubory na různých programových i technických platformách.

[editovat] Distribuované Hashovací tabulky - DHT – Chord, uložení a vyhledání informace.

[editovat] Ověřování – MAC, digitální podpis, arbitrovaný digitální podpis, vzájemné ověřování (mezi členy, vzhledem k ověřovacímu serveru).