49 - Distribuovaný broadcast, synchronizace v distribuovaných systémech

Question 1

Distribuovaný broadcast

Answer 1

K tomu, aby když posíláme zprávy v distribuovaných systémech, tak abychom si byli jisti, že dojdou příjemci a nepomíchaly se (tedy zprávy byly vždy doručeny a to maximálně jednou a ve správném pořadí).

Posílání zpráv používá například Lamportův algoritmus pro vzájemné vyloučení zdroje.

“In distributed systems, atomic broadcast or total order broadcast is a broadcastmessaging protocol that ensures that messages are received reliably and in the same order by all participants”

pojmy:

• m - zpráva z množiny možných zpráv, každá zpráva zahrnuje odesílatele (sender(m)) a sekvenční číslo (seq(m))
• funkce bcast(m) a deliver(m)
• např. sender(m)=p a seq(m)=i znamená, že m je i-tá zpráva poslaná procesem p
  • komunikace: známe horní mez zpoždění zprávy; lokální hodiny pro každý proces
  • topologie: obecná topologie grafu

	• specifikace
		○ m = zpráva z množiny možných zpráv
		○ každá zpráva obsahuje
			§ totožnost odesilatele: sender(m)
			§ pořadové číslo (kolikátou zprávu odesilatel poslal): seq(m)

• Tedy deliver - doručit, znamená prakticky přijmout na straně aplikace.

Question 2

3 hlavní vlastnosti broadcastu - spolehlivý broadcast

Answer 2

Následující 3 vlastnosti tvoří spolehlivý broadcast

platnost (validity): když se pošle, tak se doručí
dohoda (agreement): když někdo přijme, všichni prijmou
celistvost (integrity): každý přijme zprávu jen jednou

• Platnost (validity): pokud správný proces odešle zprávu, pak všem procesům je tato zpráva nakonec doručena.  - (Pokud korektní proces odešle broadcast, pak všechny korektní procesy tento broadcast obdrží (dříve či později))

• Dohoda (agreement): pokud správný proces doručí zprávu (přijme ji), pak všem procesům je tato zpráva nakonec doručena.  - (Pokud korektní proces obdržel broadcast, potom všechny korektní procesy obdrží broadcast také (dříve či později))

• Celistvost (Integrity): každý proces přijme zprávu jen jedenkrát.  - (Každý korektní proces obdrží broadcast maximálně jednou (nedojde k zacyklení))

Question 3

Další vlastnosti broadcastu a klasifikace

Answer 3

FIFO - když proces odešle m před n, všichni přijmou v tomto pořadí
casual - pokud m předchází n, všichni přijmou v tomto pořadí
total - všichni přijmou ve stejném pořadí

• FIFO řazení (FIFO order): pokud proces odešle zprávu m před n, tak žádný proces správný proces nesmí přijmout n před m.
	○ “FIFO order” from single process

• Náhodné řazení (Casual order): pokud zpráva m náhodně předchází n, tak žádný proces nesmí doručit n aniž by předtím doručil m.
	○ “FIFO order” from all processes

• Celkové řazení (Total order): pokud správné procesy p a q oba doručí zprávy m a n, pak p doručí m před n pokud q doručí m před n.
	○ Receiving in the same order.

Klasifikace

Reliable (RBCAST) = Validity + Agreement + Integrity

FIFO (FBCAST) = reliable + FIFO Order
Causal (CBCAST) = reliable + Causal Order
Atomic (ABCAST) = reliable + Total Order

Question 4

Algoritmus pro spolehlivý broadcast (RBCAST)

Answer 4

Odesílatel o:
bcast(R,m): //R = reliable bcast, m = zprava
- pridej do m odesilatele(m) a sekvencni_cislo(m);
- send(m) vsem sousedum, vcetne sebe;

Prijemce p:
deliver(R,m):
-  pri receive(m) do
 - -  if p jeste neprijal tento broadcast then
 - - -   if sender(m) != p then send(m) vsem sousedum;
  - -  deliver(R,m)
  - endif;
 enddo;

Question 5

Synchronizace v distribuovaných systémech

Answer 5

V distribuovaných systémech není údaj o globálním čase (i kdyby byl, nejsme schopní kontrolovat zpoždění mezi doručením zpráv). Tedy každý uzel má vlastní hodiny. Řešíme problém vzájemného vyloučení pří požadavku více klientů v distribuovaném prostředí na sdílený zdroj. 2 možnosti:

• absence globálních a synchronizačních hodin
• vzájemné vyloučení
	○ existuje pevný počet procesorů, které sdílí jeden zdroj a ten může v danou chvíli používat pouze jeden procesor
	○ centralizované řešení

• Třídy algoritmů:
	○ Timestamp-based (Lamport + optimalizace Ricart-Agrawala algoritmus)
	○ Token-based (Raymond)

Question 6

Synchronizace v distribuovaných systémech - Lamportovy logické hodiny

Answer 6

Lamportovy logické hodiny

• Není zde žádná souvislost s fyzickými hodinami, ve skutečnosti jde o časová razítka.
• !!! NEREFLEXNÍ ČÁSTEČNÉ USPOŘÁDÁNÍ Založeno na relaci mezi dvěma událostmi stalo_se_dříve(a,b) - “happens-before” !!!
• > Tyto hodiny představují nereflexní částečné uspořádání - Nicméně dá se to rozšířit i na totální uspořádání (použije se sekundární klíč, např. ID procesu)
• Vychází z pravidel fyzické kauzality (než něco přijmeme, musíme to odeslat)
• Synchronizace hodin mezi 2 procesy probíhá takto:

1. Každý proces má vlastní čítač běžící různou rychlostí
2. Proces 1 chce odeslat zprávu procesu 2, společně se zprávou vloží hodnotu svého čítače
3. Proces 2 přijme zprávu od procesu 1 a zjistí časové razítko
4. Proces 2 porovná hodnoto svého čítače s hodnotou extrahovanou z časového razítka procesu 1
5. Proces 2 si nastaví hodnotu svého čítače na vyšší z těchto dvou hodnot a inkrementuje hodnotu
6. V tuto chvíli jsou procesy 1 a 2 synchronizovány (ale jen na chvíli, protože jejich čítače běží obecně různě rychle)

Co se týče logických hodin, tak ty jsou založeny na inkrementování čítače.
• Procesor i má logické hodiny C_i
• Hodnota těchto hodin se inkrementuje před každou událostí na i.
• Každá událost a přiřadí hodinám hodnotu C(a).
• if a→b, then C(a)

Question 7

Synchronizace v distribuovaných systémech - Lamportův algoritmus a ricart-agrawala vylepšení

Answer 7

• Decentralizovaný algoritmus vzájemného vyloučení.
• Předpokládá obousměrné FIFO kanály mezi procesy.
• Každý proces udržuje vlastní prioritní 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:
		1. Požadavek (req)
		2. Potvrzení (ack)
		3. Uvolnění (rel)

• Proces P požaduje zdroj posláním požadavku do všech procesů zasláním zprávy req.
• 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.
	○ Tady konečně vidíme, k čemu jsou potřeba ty logické hodiny :-)

* Ukončení zpracování požadavku – odstranění požadavku z fronty a poslání zprávy rel ostatním procesům.
* Přijetí zprávy rel od procesu P – odstranění požadavku procesu P z fronty.
* Povolení zpracování požadavku – požadavek je na prvním místě ve frontě a je potvrzen ostatními procesy.

Lamport po lopatě
	○ Nějaký proces P se rozhodne, že chce přistoupit ke sdíleném zdroji. Jelikož je slušňák, tak svůj úmysl oznámí všem ostatním procesům, a to tak, že jim pošli REQ zprávu spolu se svou časovou značkou a ID.
	○ Poté, co mu všechny ostatní procesy odpoví zprávou ACK, se proces podívá do své fronty požadavků, jestli je na řadě.
		§ Pokud je na řadě, tak použije sdílený zdroj a potom všem procesům pošle zprávu REL, které je informuje, že už daný zdroj nepotřebuje.
	○ Pokud není na řadě, tak počká dokud mu nepřijde REL zpráva od ostatních procesů a on se na řadu konečně dostane.

Ricart-Agrawala algorithm - prostě spojí ack a rel zprávu
Je to optimalizovaný Lamport.
• Spojuje release a reply zprávy.
○ Tedy místo 3(n−1) zpráv se posílá jenom 2(n−1)

Pokud to chápu správně, tak se REL zpráva pošle jenom tomu procesu, který je další na řadě.

Question 8

Synchronizace v distribuovaných systémech - raymondův algoritmus

Answer 8

• token-based algoritmus
• procesy uspořádány do stromu
• samotný token představuje KS - pokud má token, může vstoupit

Problémy: hladovění, deadlock, tolerance chyb

Uzly, představující procesy v distribuovaném systému jsou uspořádány do binárního stromu. V tomto stromě se pohybuje “token”, udávající povolení ke vstupu do kritické sekce. Procesy bojují o token, pouze ten který ho má smí vstoupit do KS. Problémem je přerušení některé větve v systému - pak procesy v této větvi nemohou vstoupit do KS.

Proces který potřebuje token pošle svou žádost nejkratší cestou k procesu co ho zrovna má, po uvolnění se pošle token dalšímu čekajícímu

Question 9

PRAM shrnutí

Answer 9

• synchronní model paralelního výpočtu ve kterém procesory komunikují sdílenou pamětí
• výpočet probíhá po krocích:
1. čtení sdílené paměti
2. lokální operace
3. zápis do sdílené paměti
• přístupy do paměti: EREW, ERCW, CREW, CRCW
• řešení zápisových konfliktů
○ COMMON: všechny zapisované hodnoty musí být shodné
○ ARBITRARY: zapisované hodnoty mohou být různé, zapíše se libovolná hodnota
○ PRORITY: procesory mají prioritu
• broadcast
○ hodnota uložená v paměti má být rozšířena mezi N procesory
○ pro CREW a CRCW řešení v konstantním čase
○ pro EREW je třeba simulovat současné čtení (P1 přečte D a zpřístupní jej P2, P1 a P2 jej zpřístupní P3 a P4…)
- Tedy v logaritmickém čase.