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ů

• Kruh je jednosměrný, každý proces má jednoho souseda a komunikace probíhá ve FIFO režimu.
• Z příchozích zpráv si uzel postupně zapamatovává ID ostatních a zprávy přeposílá dál po kruhu.
• Po přijetí zprávy s vlastním ID zná proces všechny procesy v kruhu a za vodce zvolí proces s nejmenším/největším ID.

• Každý proces je ve stavu participant, nebo non-participant.
  • Iniciálně jsou všichni non-participant.
• Proces zahajující volební běh se označí za participant a pošle volící zprávu následníkovi.
• Následník se rozhoduje:
  • : přepošle
  • a není účastníkem volby: přepošle a označí se za účastníka volby
  • a je účastníkem volby: přijatou zprávu nepřeposílá = ruší volební běh ; volební běh běží
  • : získal volící zprávu, kterou vyslal
    • přepne se do stavu vůdce
    • označí se za non-participant
    • pošle po kruhu ukončovací zprávu (ostatní si označí vůdce a zruší účast)

• ➕ sledování stavu participant/non-participant umožňujue likvidovat zbytečné násobné běhy.
• ➖ výpadek uzlu značí výpadek celé úlohy

• Iniciátor v jednotlivých fázích r=0,1,.. posílá svou identitu do vzdálenosti nesoucí průzkumovou zprávu.
• Identity cestující po kruhu jsou likvidovány jako u algoritmu Chang-Roberts.
• Do další fáze vstupují pouze vítězové. (vítěz ve fázi = nejvyšší ID do vzdálenosti )
  • Ostatní pouze přeposílají zprávy.

Použitelnost:

• proces může poslat zprávu každému z ostatních procesů.
• Mohou se vyskytovat výpadky uzlů.
  • Poznán na základě timeoutu.
• Komunikační systém je spolehlivý (neztrácí se zprávy).

Když se proces rozhodne volit, zvolí sebe a zašle o tom zprávu všem procesům s vyšší prioritou.

Pokud proces přijme zprávu o volebním běhu:

• má určitě vyšší prioritu ⇒ vrátí zamítavou odpověď
• sám spouští volební běh → zašle zprávu všem procesům s vyšší prioritou

Odpovědi:

• Když proces dostane zamítavou odpověď, existuje proces s vyšší prioritou ⇒ proces ukončí svůj volební běh.
• Když nedostane zamítavou odpověď, volbu vyhrál.
  • Nastaví se jako nový vůdce a pošle o tom všem ostatním procesům zprávu.

Pokud proces obnoví svůj běh, okamžitě zahajuje volební běh a nastane jedna ze dvou možností:

• Stane se vůdcem.
• Dozví se, kdo je vůdcem.