IN-POS 4. Modely distribuovaných systémů

1. MASTER uzel se periodicky ptá na čas SLAVE uzlů.
2. Odečte polovinu obrátky.
3. Zprůměruje a odešle aktuální hodnotu SLAVE uzlům.

• Možnost přesné synchronizace s UTC v Internetu.
• Časové servery tvoří hierarchickou strukturu.
• Módy synchronizace:
  • Multicast: jeden server odesílá informace o čase skupině.
  • Procedure-call: server vrací časové razítko na žádost (de facto Cristianův alg.)
  • Symmetric: mezi 2 servery v různých úrovních; servery si opakovaně posílají časová razítka a opravují chyby

• S každou událostí se sváže časové razítko.
• Každý proces si udržuje logické (Lamportovy) hodiny. (Mapují částečné uspořádání.)
• Odeslání zprávy:
  • Odešleme aktuální časové razítko.
  • Lokální čas zvýšíme o jedna.
• Příjem zprávy:
  • Porovnáme přijaté časové razítko s lokálními hodinami.
  • Vezmeme větší z nich, zvýšíme o jedna a nastavíme jako lokální čas.
• Vztah událostí:
  • A→B ⇒ TS(A) < TS(B)

• Řeší problém s opačnou implikací u Lamprotových hodin.
• Místo jednoho razítka pro lokální čas použijeme vektor časových razítek. (velikost = počet procesů)
  • iniciálně vyplněn nulami
• Před odesláním proces zvýší „svůj“ prvek vektoru o jedna. Pouze toto časové razítko se odesílá se zprávou.
• Při přijetí zprávy zaktualizujeme odesilatelům prvek vektoru na maximum z lokální a přijaté hodnoty.
• Vztah vektorových razítek:
  • V = V' iff všechny členy vektoru jsou si rovny
  • V < V' iff V[j] < V'[j] pro j=1,…|V|

• iniciátor = proces iniciující zjištění globálního stavu
  • zaznamená momentku svého lokálního stavu a odešle MARKER všem sousedům v DS
• MARKER získal proces, který dosud nevypracoval momentku
  • zaznamená momentku svého lokálního stavu a pošle ji iniciátorovi
  • označí vstupní kanál, ze kterého přijal MARKER„, jako prázdný
  • všem ostatním sousedům pošle MARKER
• MARKER získal proces, který již momentku vypracoval
  • zaznamená události od poslední momentky a pošle iniciátorovi
• Iniciátor nakonec sestaví globální stav
  • zná lokální momentky všech procesů
  • zná zprávy v „éteru“
  • Kanály jsou FIFO, tedy je globální momentka smysluplná ((ne)zahrnuté zprávy jsou odděleny v kanálech MARKERy).

• lineární složitost

• ➕ Splněna podmínka bezpečnosti.
• ➕ Splněna podmínka živosti.
• ➕ Podmínka spravedlnosti splněna zajištěním maximálně jednoho předběhnutí od jiného procesu.
• ➖ Ztrátu příznaku je nutné řešit distribuovanou volbou procesu, který jej vygeneruje.
• ➖ Výpadek jednoho uzlu nutné řešit rekonstrukcí kruhu.

Příznak se předává po kostře grafu tak, aby se dodržela podmínka spravedlnosti na bázi časového pořadí vzniků žádostí.

• Uzel držící příznak je kořenem stromu.
• Uzel žádá o vstup do KS svého rodiče, ten jej předává po cestě ke kořeni.
• Při předání příznaku se konfigurace stromu aktualizuje.

• ➕ Vzájemná výlučnost splněna trvale.
• ➕ Nemůže dojít ani k uváznutí ani ke stárnutí.

Příznak se předává na bázi cykličnosti uspokojování žádosti procesů.

Přehled nově generovaných a dosud nesplněných žádostí se udržuje distribuovaně v uzlech a v příznaku.

• Proces pro žádost o vstup do KS odesílá všem uzlům REQUEST zprávu.
• Uzel držící příznak po výstupu z KS odešle vybranému z procesů příznak.
• Procesy si drží čísla žádostí od ostatních, token obsahuje pole s vyhověnými žádostmi.
• Postupuje se cyklicky, přes procesy, které mají zájem.

• ➖ Procesy se musí navzájem znát.

• Jestliže je příjemce v KS, neodpovídá a zařadí požadavek do fronty.
• Jestliže příjemce není v KS a ani do ní nechce vstoupit, pak pošle zpět potvrzení práva vstupu do KS.
• Jestliže příjemce není v KS, ale chce do ní vstoupit (sám vyslal žádost), porovná časovou značku své a přijaté žádosti.
  • Pokud byla vlastní žádost odeslána dříve, neodpovídá a uloží žádost do fronty.
  • Pokud byla přijatá žádost odeslána dříve, pošle zpět potvrzení práva vstupu do KS.

• Až získá proces souhlas od všech, vstupuje do KS.
• Po opuštění KS proces odešle potvrzení všem procesům, které má ve frontě.

• ➕ Je splněna podmínka bezpečnosti.
• ➕ Je splněna podmínka živosti.
• ➕ Komunikační složitost je lineární.
• ➖ Proces musí znát ostatní.
• ➖ Výpadek jednoho procesu způsobí kolaps celého systému. ⇒ Vhodné pro malé a stabilní množiny procesů.

Proces požadující vstup do KS žádá o příznak procesy ve svém kvóru.

• kvůrum = podmnožina procesů, navzájem se protínají
• Oslovený jej pošlu pokud jej ještě vlastní a sám se v KS nenachází.

Proces s hlasy od procesů v jeho kvóru vstupuje do KS. Po vystoupení hlasy vrací původním majitelům.

Podmínky kvóra:

• bezpečnost:
  • Každá dvojice volebních okrsků má alespoň jeden společný prvek.
  • Každý má pouze jeden hlas. ⇒ Nemohou být současně zvoleny dva procesy.
• spravedlnost
  • Velikost okrsků je konstantní a každý proces je ve stejném počtu okrsků.
  • Všechny procesy potřebují pro vstup do KS stejný počet hlasů