39 - Distribuovaný broadcast, synchronizace v distribuovaných systémech
pátek 1. dubna 2016
10:43
Distribuovaný broadcast
K čemu to je dobré?
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.[1] Distributed systems are ones where each computer runs independently toward a common goal, and as a result, designing a successful atomic broadcast system is a significant challenge.[2]
Atomic broadcast is a fundamental problem in distributed computing. A successful system must be a reliable broadcast. In addition, such a system must satisfy the total order property. This means that if computer A sends message 1 first and message 2 second, a success means that computer B receives both messages and that it receives message 1 before message 2. Atomic broadcasts are simple when computers are correct, meaning that they never fail. However, real computers are faulty, and do fail, and even if failures are temporary, this is where the challenge results.[2]
The following properties are usually required from an atomic broadcast protocol. Validity means that if a correct participant broadcasts a message, then all correct participants will eventually receive it. Uniform agreement means that if a participant delivers a message, then all correct participants will eventually deliver it as well. Uniform integrity means that any given message is delivered by each participant at most once, and only if it was previously broadcast.
The definitions for validity and integrity may be sometimes formulated in different way. E.g. Michel Raynal et al.[3] and Schiper et al.[4] define validity property of atomic broadcast slightly differently, but the main requirement that messages are broadcast in the correct order remains.
[link]
[link] 
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.
Základní vlastnosti broadcastu
A process is called "correct" if it does not fail at any point during its execution.
3 hlavní vlastnosti
Následující 3 vlastnosti tvoří spolehlivý broadcast.
Platnost (validity): pokud správný proces odešle zprávu, pak všem procesům je tato zpráva nakonec doručena.
Shoda (agreement): pokud správný proces doručí zprávu (přijme ji), pak všem procesům je tato zpráva nakonec doručena.
Celistvost (Integrity): každý proces přijme zprávu jen jedenkrát.
Další vlastnosti
FIFO řazení (FIFO order): pokud proces odešle zprávu 𝒎 před 𝒏, tak žádný proces správný proces nesmí přijmout 𝒏 před 𝒎.
“FIFO order” from single process
Kauzální řazení (Causal order): pokud zpráva 𝒎 kauzálně předchází 𝒏, tak žádný proces nesmí doručit 𝒏 aniž by předtím doručil 𝒎.
“FIFO order” from all processes
Celkové řazení (Total order): pokud správné procesy 𝒑 a 𝒒 oba doručí zprávy 𝒎 a 𝒏, pak 𝒑 doručí 𝒎 před 𝒏 tehdy a jen tehdy pokud 𝒒 doručí 𝒎 před 𝒏.
Receiving in the same order.
Klasifikace broadcastu
Reliable = Validity + Agreement + Integrity
FIFO = Reliable + FIFO Order
Causal = Reliable + Causal Order
Atomic = Reliable + Total Order
FIFO Atomic = Reliable + FIFO Order + Total Order
Causal Atomic = Reliable + Causal
Order + Total Order
Synchronizace v distribuovaných systémech
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)
Token-based (Raymond)
Lamportovy logické hodiny
První je (asi) potřeba pochopit Lamportovy logické hodiny.
Neexistuje tu žádné spojení s fyzickými hodinami.
Získává částečné nebo totální pořadí událostí, které se staly v různých procesech(procesorech).
Založeno na vztahu: "happens-before" (NEREFLEXNÍ ČÁSTEČNÉ USPOŘÁDÁNÍ)
Tedy pokud ve stejném procesu vzniknou události 𝑎 a 𝑏 a 𝒂 předchází 𝒃, pak a→b.
Pokud a→b a 𝑏→c, pak 𝑎→c.
Co se týče logických hodin, tak ty jsou založeny na inkrementování čítače.
Procesor 𝑖 má logické hodiny Ci
Hodnota těchto hodin se inkrementuje před každou událostí na 𝑖.
Každá událost 𝑎 přiřadí hodinám hodnotu 𝐶(𝑎).
𝐢𝐟 𝐚→𝐛, 𝐭𝐡𝐞𝐧 𝐂𝐚<𝐂(𝐛)
Implementace logických hodin
Inkrementuj hodiny při každém eventu.
Pošli časovou známku 𝑡 společně se zprávou 𝑚.
Příjemce 𝑞 udělá: 𝐂𝐪=𝐦𝐚𝐱𝐂𝐪,𝐭+𝟏.
Časová známka se přiřadí eventům po inkrementaci.
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)
Lamportův algoritmus
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 𝟑∗(𝒏−𝟏) zpráv.
Probíhá ve třech fázích:
Požadavek (req)
Potvrzení (ack)
Uvolnění (rel)
Samotný Lamportův algoritmus
Proces 𝑃 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 𝑃 – odstranění požadavku procesu 𝑷 z fronty.
Povolení zpracování požadavku – požadavek je na prvním místě ve frontě a je potvrzen ostatními procesy.
Na obrázku jsou dvojce: 𝑡𝑖𝑚𝑒, 𝑝𝑟𝑜𝑐𝐼𝐷
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
Je to optimalizovaný Lamport.
Spojuje release a reply zprávy.
Tedy místo 3(n−1) zpráv se posílá jenom 𝟐(𝐧−𝟏)
Pokud to chápu správně, tak se REL zpráva pošle jenom tomu procesu, který je další na řadě.
Raymond’s algorithm
Tento algoritmus je token-based a procesy má uspořádány do stromu.
[link]
Samostatný token v systému reprezentuje kritickou sekci (CS).
Proces vstupuje do CS pokud má token.
Problémy: hladovění, deadlock, tolerance chyb
Analýza Raymondova lagoritmu
Raymond's algorithm is guaranteed to be O(log n) per critical section entry if the processors are organized into a K-ary tree. Additionally, each processor needs to store at most O(log n) bits because it must track O(1) neighbors.
Samotný Raymonduv algoritmus
If a node i wishes to receive the token in order to enter into its critical section, it sends a request to its parent, node j.
If node j FIFO is empty, node j shifts i into the its FIFO queue; j then issues a request to its parent, k, that it desires the token
If node j FIFO queue is not empty, it simply shifts i into the queue
When node j receives the token from k, it forwards the token to i and i is remo dved from the queue of j
If the queue of j is not empty after forwarding the token to i, j must issue a request to i in order to get the token back
Note: If j wishes to request a token, and its queue is not empty, then it places itself into its own queue. Node j will utilize the token to enter into its critical section if it is at the head of the queue when the token is received.
Init
Req
In CS
Release
Notes
2. Otazka (predmet) (okruh): 49. Distribuovaný broadcast, synchronizace v distribuovaných systémech.
Kdo me primarne zkousel: Zbořil František, doc. Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Opäť nebola podotázka. Toto bola téma, ktorú som si síce asi 2-krát prechádzal, ale nemal som ju dobre naučenú a tak som počas tej minútovej prípravy rozmýšľal hlavne nad ňou. Vyzval ma, že môžem nejako začať a nešpecifikoval, na čo sa zamerať. Povedal som teda nejakú úvodnú "filozofickú" vetu, na čo broadcasty sú. Potom som povedal tie 3 základné vlastnosti broadcastu. Vlastne nepovedal som ich názvy a na jednu som si nevedel spomenúť vôbec. Nechcel som ale zostať ticho, tak som išiel hovoriť ďalej, ale doc. Zbořil ma pozastavil a tú chýbajúcu vlastnosť doplnil. Potom som chcel hovoriť o FIFO Order, Causal Order a Total Order. Vedel som, aké sú ich podmienky, vedel som, že sa nejako implementujú, ale že ako, to už som si nevedel spomenúť. Tak som povedal podmienku pre FIFO order a potom ma pozastavil, že ako to implementovať, čo práve som si už nepamätal. Opäť som sa snažil nebyť moc dlho ticho a tak som špekuloval a skúsil niečo povedať, už si sám nepamätám, čo to bolo, ale bolo to zle. Snažil sa ma potom naviesť na správnu odpoveď, ale trvalo to dlhšie a tak sme sa už na ďalšie Ordery nedostali. C
From <[link]> 
2. Otazka (předmět) (okruh): Distribuovaný broadcast (PRL)
Kdo me primarne zkousel: Zbořil
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Nejdříve jsem se ujistil, že se neptá na Lamporta a tu relaci a řekl že tak daleko ne. Pak mě nasměroval na reliable broadcast a nějak jsme se dostali k těm třem vlastnostem. Pak jsme probrali FIFO atd. Nakonec začal mluvit o fragmentaci zpráv na pakety, jejich odesílání a příjmání s bufferem. To jsem v žádných materiálech k této otázce neviděl.
From <[link]> 
1. Otazka (okruh): 51. Distribuovaný broadcast, synchronizace v distribuovaných systémech.
Kdo me primarne zkousel: Zboril ml.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
zacal som broadcastom hned ma zastavil ze to viem to je lahke a zacal sa sprtat v lampartovi a pytal sa ma na niake relacie atd to som moc nevedel... snazil sa pomoct tak sme to niako nakoniec dali dokopy... za D
From <[link]> 
2. Otazka (okruh): Distribuovaný broadcast, synchronizace v distribuovaných systémech.
Kdo me primarne zkousel: Zboril
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Sice jsem se na to dival nez jsem sel z domu ale byl jsem uplne vymazanej. Nemohl jsem si to nejak srovnat. Tak se me nakonec ptal. Rekl jsem mu ze se tam posilaji zpravy, jak to zhruba komunikuje, ze se posilaji nejaky casovy znacky. Ptal se co je to spolehlivy broadcast, jaky je rozdil mezi kauzalnim/nekauzalnim systemem. Vzpomnel jsem si nastesti na Lamporta, ale vylezl jsem zpocenej az na prdeli 
. [E]
From <[link]> 
2. Otazka (okruh):Distribuovaný broadcast, synchronizace v distribuovaných systémech
Kdo me primarne zkousel: Zboril
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Rikam si no fajn prijdu na Lammpartuv algoritmus ktery (jsem si myslel) ze umim. Zacal jsem mluvit neco o logickych hodinach. Pak chtel Zboril vedet neco co jsem ze sebe proste nebyl schopen dostat. Neco ve stylu, v jake relaci jsou tyto procesy. Asi 3x jsem neco placnul a odpoved byla "no to urcite ne, tak to rozhodne neni" rikal jsem si posledni hrebik do rakve.
Znamka asi E (nevim jestli to nebylo naopak)
From <[link]> 
1. Otazka (okruh): 29. Distribuovaný broadcast, synchronizace v distribuovaných systémech
Kdo me primarne zkousel: Ryšavý
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Otázky byly směrovány zejména na motivaci, proč distribuovaný broadcast provádět a jak zajistit synchronizaci. Tohle není zrovna moje parketa, takže občas něco plácnul a pak víceméně odkejvával, co si Ryšavý sám odpovídal. Snažil se pomoct, ale moc jsem mu toho sám neřekl.
From <[link]> 