Tak si to predstavme. V izbe je zamknutých 5 mačiek a na to, aby mohli ísť zobudiť majiteľa, sa musia všetci dohodnúť medzi sebou, lebo dvere môžu otvárať len piati, ktorí sa o ne opierajú. Ak je jedna z mačiek Schrödingerova mačka a ostatné mačky o jeho rozhodnutí nevedia, vyvstáva otázka: „Ako to môžu urobiť?
V tomto článku vám zjednodušene poviem o teoretickej zložke sveta distribuovaných systémov a princípoch ich fungovania. Tiež povrchne preskúmam hlavnú myšlienku, ktorá je základom Paxosu.
Keď vývojári používajú cloudové infraštruktúry, rôzne databázy a pracujú v klastroch veľkého počtu uzlov, sú si istí, že dáta budú úplné, bezpečné a vždy dostupné. Ale kde sú záruky?
Záruky, ktoré máme, sú v podstate dodávateľské záruky. V dokumentácii sú opísané takto: „Táto služba je celkom spoľahlivá, má danú zmluvu SLA, nebojte sa, všetko bude fungovať distribuovane tak, ako očakávate.“
Máme tendenciu veriť v to najlepšie, pretože šikovní chlapci z veľkých spoločností nás ubezpečili, že všetko bude v poriadku. Nekladieme si otázku: prečo to vlastne môže fungovať? Existuje nejaké formálne opodstatnenie správneho fungovania takýchto systémov?
Nedávno som išiel do a veľmi ma inšpirovala táto téma. Prednášky v škole boli skôr hodiny kalkulu než niečo, čo sa týkalo počítačových systémov. Ale presne takto boli naraz overené najdôležitejšie algoritmy, ktoré používame každý deň bez toho, aby sme o tom vedeli.
Väčšina moderných distribuovaných systémov využíva konsenzuálny algoritmus Paxos a jeho rôzne modifikácie. Najskvelejšie na tom je, že platnosť a v zásade aj samotná možnosť existencie tohto algoritmu sa dá dokázať jednoducho perom a papierom. V praxi sa algoritmus používa vo veľkých systémoch bežiacich na veľkom počte uzlov v cloude.
Ľahká ilustrácia toho, o čom sa bude diskutovať ďalej: úloha dvoch generálovPoďme sa pozrieť na rozcvičku .
Máme dve armády – červenú a bielu. V obliehanom meste sídlia biele jednotky. Červené jednotky vedené generálmi A1 a A2 sa nachádzajú na dvoch stranách mesta. Úlohou ryšavých je zaútočiť na biele mesto a vyhrať. Armáda každého červeného generála jednotlivo je však menšia ako biela armáda.
Podmienky víťazstva pre červených: obaja generáli musia útočiť súčasne, aby mali početnú prevahu nad bielymi. Na to sa musia generáli A1 a A2 navzájom dohodnúť. Ak zaútočí každý zvlášť, červenovlásky prehrajú.
Na dosiahnutie dohody si môžu generáli A1 a A2 navzájom posielať poslov cez územie bieleho mesta. Posol môže úspešne dosiahnuť spojeneckého generála alebo ho môže zachytiť nepriateľ. Otázka: existuje taká postupnosť komunikácie medzi ryšavými generálmi (sekvencia posielania poslov z A1 do A2 a naopak z A2 do A1), v ktorej sa zaručene dohodnú na útoku v hodine X. Tu záruky znamenajú, že obaja generáli budú mať jednoznačné potvrdenie, že spojenec (iný generál) definitívne zaútočí v určenom čase X.
Predpokladajme, že A1 pošle posla k A2 so správou: "Zaútočme dnes o polnoci!" Generál A1 nemôže zaútočiť bez potvrdenia od generála A2. Ak posol z A1 dorazil, potom generál A2 pošle potvrdenie so správou: "Áno, dnes zabijeme bielych." Teraz však generál A2 nevie, či jeho posol dorazil alebo nie, nemá žiadnu záruku, či bude útok simultánny. Teraz generál A2 opäť potrebuje potvrdenie.
Ak ďalej popíšeme ich komunikáciu, je jasné, že bez ohľadu na to, koľko cyklov výmeny správ existuje, neexistuje žiadny spôsob, ako zaručiť, že obaja generáli dostali svoje správy (za predpokladu, že ktorýkoľvek posol môže byť zachytený).
Problém dvoch generálov je skvelou ilustráciou veľmi jednoduchého distribuovaného systému, kde existujú dva uzly s nespoľahlivou komunikáciou. To znamená, že nemáme 100% záruku, že sú synchronizované. Podobné problémy sú diskutované len vo väčšom rozsahu ďalej v článku.
Predstavujeme koncept distribuovaných systémov
Distribuovaný systém je skupina počítačov (ďalej ich budeme nazývať uzly), ktoré si môžu vymieňať správy. Každý jednotlivý uzol je nejakým druhom autonómnej entity. Uzol môže sám spracovávať úlohy, ale aby mohol komunikovať s inými uzlami, potrebuje odosielať a prijímať správy.
Ako presne sú správy implementované, aké protokoly sa používajú - to nás v tomto kontexte nezaujíma. Je dôležité, aby si uzly distribuovaného systému mohli navzájom vymieňať údaje posielaním správ.
Samotná definícia nevyzerá veľmi zložito, no musíme brať do úvahy, že distribuovaný systém má množstvo atribútov, ktoré budú pre nás dôležité.
Atribúty distribuovaných systémov
- súbežnosť – možnosť simultánnych alebo súbežných udalostí vyskytujúcich sa v systéme. Okrem toho budeme považovať udalosti, ktoré sa vyskytujú na dvoch rôznych uzloch, za potenciálne súbežné, pokiaľ nemáme jasné poradie výskytu týchto udalostí. Ale spravidla ho nemáme.
- Žiadne globálne hodiny. Nemáme jasné poradie udalostí kvôli chýbajúcim globálnym hodinám. V bežnom svete ľudí sme zvyknutí na to, že hodiny a čas máme absolútne. Všetko sa mení, pokiaľ ide o distribuované systémy. Dokonca aj ultra presné atómové hodiny sa posúvajú a môžu nastať situácie, keď nevieme povedať, ktorá z dvoch udalostí sa stala skôr. Preto sa nemôžeme spoliehať ani na čas.
- Nezávislé zlyhanie uzlov systému. Je tu ďalší problém: niečo sa môže pokaziť jednoducho preto, že naše uzly netrvajú večne. Pevný disk môže zlyhať, virtuálny počítač v cloude sa môže reštartovať, sieť môže blikať a správy sa stratia. Okrem toho môžu nastať situácie, keď uzly fungujú, ale zároveň pracujú proti systému. Posledná trieda problémov dostala dokonca samostatný názov: problém . Najpopulárnejším príkladom distribuovaného systému s týmto problémom je Blockchain. Ale dnes nebudeme uvažovať o tejto špeciálnej triede problémov. Budeme sa zaujímať o situácie, v ktorých môže jednoducho jeden alebo viac uzlov zlyhať.
- Komunikačné modely (modely správ) medzi uzlami. Už sme zistili, že uzly komunikujú prostredníctvom výmeny správ. Existujú dva známe modely zasielania správ: synchrónny a asynchrónny.
Modely komunikácie medzi uzlami v distribuovaných systémoch
Synchrónny model – s istotou vieme, že existuje konečná známa delta času, počas ktorej sa správa zaručene dostane z jedného uzla do druhého. Ak tento čas uplynul a správa neprišla, môžeme pokojne povedať, že uzol zlyhal. V tomto modeli máme predvídateľné čakacie doby.
Asynchrónny model – v asynchrónnych modeloch uvažujeme, že čas čakania je konečný, ale neexistuje taká delta času, po ktorej by sme mohli zaručiť, že uzol zlyhal. Tie. Čakacia doba na správu z uzla môže byť ľubovoľne dlhá. Toto je dôležitá definícia a budeme o nej hovoriť ďalej.
Koncept konsenzu v distribuovaných systémoch
Pred formálnym definovaním pojmu konsenzus uvažujme o príklade situácie, keď ho potrebujeme, a to: Replikácia štátneho stroja.
Máme distribuovaný denník. Chceli by sme, aby bol konzistentný a obsahoval identické údaje o všetkých uzloch distribuovaného systému. Keď sa jeden z uzlov dozvie novú hodnotu, ktorú sa chystá zapísať do protokolu, jeho úlohou je ponúknuť túto hodnotu všetkým ostatným uzlom, aby sa protokol aktualizoval na všetkých uzloch a systém prešiel do nového konzistentného stavu. V tomto prípade je dôležité, aby sa uzly medzi sebou dohodli: všetky uzly súhlasia s tým, že navrhovaná nová hodnota je správna, všetky uzly túto hodnotu akceptujú a iba v tomto prípade môže každý zapísať novú hodnotu do protokolu.
Inými slovami: žiadny z uzlov nenamietal, že by mal relevantnejšie informácie a navrhovaná hodnota bola nesprávna. Zhoda medzi uzlami a zhoda na jedinej správnej akceptovanej hodnote je v distribuovanom systéme konsenzus. Ďalej budeme hovoriť o algoritmoch, ktoré umožňujú, aby distribuovaný systém dosiahol konsenzus.
Formálnejšie môžeme definovať konsenzuálny algoritmus (alebo jednoducho konsenzuálny algoritmus) ako určitú funkciu, ktorá prenáša distribuovaný systém zo stavu A do stavu B. Tento stav navyše akceptujú všetky uzly a všetky uzly ho môžu potvrdiť. Ako sa ukazuje, táto úloha nie je vôbec taká triviálna, ako sa na prvý pohľad zdá.
Vlastnosti konsenzuálneho algoritmu
Konsenzuálny algoritmus musí mať tri vlastnosti, aby systém mohol pokračovať v existencii a mal určitý pokrok v prechode zo stavu do stavu:
- Dohoda – všetky správne fungujúce uzly musia mať rovnakú hodnotu (v článkoch sa táto vlastnosť označuje aj ako bezpečnostná vlastnosť). Všetky uzly, ktoré momentálne fungujú (nezlyhali ani nestratili kontakt s ostatnými), sa musia dohodnúť a prijať nejakú konečnú spoločnú hodnotu.
Tu je dôležité pochopiť, že uzly v distribuovanom systéme, o ktorých uvažujeme, sa chcú dohodnúť. To znamená, že teraz hovoríme o systémoch, v ktorých môže niečo jednoducho zlyhať (napríklad niektorý uzol zlyhá), ale v tomto systéme rozhodne nie sú uzly, ktoré by zámerne pôsobili proti iným (úloha byzantských generálov). Vďaka tejto vlastnosti zostáva systém konzistentný.
- integrita — ak všetky správne fungujúce uzly ponúkajú rovnakú hodnotu v, čo znamená, že každý správne fungujúci uzol musí akceptovať túto hodnotu v.
- Ukončenie – všetky správne fungujúce uzly nakoniec nadobudnú určitú hodnotu (vlastnosť živosti), ktorá umožňuje algoritmu napredovať v systéme. Každý jednotlivý správne fungujúci uzol musí skôr či neskôr akceptovať výslednú hodnotu a potvrdiť ju: “Pre mňa je táto hodnota pravdivá, súhlasím s celým systémom.”
Príklad toho, ako funguje konsenzuálny algoritmus
Zatiaľ čo vlastnosti algoritmu nemusia byť úplne jasné. Preto si ukážeme na príklade, akými fázami prechádza najjednoduchší konsenzuálny algoritmus v systéme so synchrónnym modelom zasielania správ, v ktorom všetky uzly fungujú podľa očakávania, správy sa nestratia a nič sa nezlomí (naozaj sa to stáva?).
- Všetko to začína návrhom na sobáš (Propose). Predpokladajme, že klient sa pripojil k uzlu s názvom „Uzol 1“ a spustil transakciu, pričom uzlu odovzdal novú hodnotu – O. Odteraz budeme volať „Uzol 1“ ponuka. Ako navrhovateľ musí „Uzol 1“ teraz oznámiť celému systému, že má čerstvé údaje, a posiela správy všetkým ostatným uzlom: „Pozrite sa! Napadol ma význam „O“ a chcem si ho zapísať! Potvrďte, že do denníka zaznamenáte aj „O“.
- Ďalšou fázou je hlasovanie za navrhovanú hodnotu (Voting). Načo to je? Môže sa stať, že iné uzly dostali novšie informácie a majú údaje o rovnakej transakcii.
Keď uzol „Uzol 1“ odošle svoj návrh, ostatné uzly skontrolujú údaje o tejto udalosti vo svojich protokoloch. Ak nie sú žiadne rozpory, uzly oznámia: „Áno, nemám žiadne iné údaje pre túto udalosť. Hodnota „O“ je najnovšia informácia, ktorú si zaslúžime.“V každom inom prípade môžu uzly odpovedať na „Uzol 1“: „Počúvajte! Mám novšie údaje o tejto transakcii. Nie "O", ale niečo lepšie."
Vo fáze hlasovania uzly dospejú k rozhodnutiu: buď všetky akceptujú rovnakú hodnotu, alebo jeden z nich hlasuje proti, čím naznačuje, že má novšie údaje.
- Ak bolo hlasovacie kolo úspešné a všetci boli za, tak systém prechádza do novej fázy – Akceptovanie hodnoty. „Uzol 1“ zhromažďuje všetky odpovede od ostatných uzlov a hlási: „Všetci sa zhodli na hodnote „O“! Teraz oficiálne vyhlasujem, že „O“ je náš nový význam, rovnaký pre všetkých! Zapíšte si to do svojej malej knižky, nezabudnite. Zapíšte si to do denníka!"
- Zvyšné uzly posielajú potvrdenie (Accepted), že si zapísali hodnotu „O“, počas tejto doby neprišlo nič nové (druh dvojfázového odovzdania). Po tejto významnej udalosti považujeme distribuovanú transakciu za ukončenú.
Algoritmus konsenzu teda v jednoduchom prípade pozostáva zo štyroch krokov: navrhnúť, hlasovať (hlasovať), prijať (prijať), potvrdiť prijatie (prijaté).
Ak sme v niektorom kroku neboli schopní dosiahnuť dohodu, algoritmus sa spustí znova, pričom sa zohľadnia informácie poskytnuté uzlami, ktoré odmietli potvrdiť navrhovanú hodnotu.
Konsenzuálny algoritmus v asynchrónnom systéme
Predtým bolo všetko hladké, pretože sme hovorili o synchrónnom modeli správ. Ale vieme, že v modernom svete sme zvyknutí robiť všetko asynchrónne. Ako funguje podobný algoritmus v systéme s asynchrónnym modelom zasielania správ, kde sa domnievame, že čakacia doba na odpoveď z uzla môže byť ľubovoľne dlhá (mimochodom, zlyhanie uzla možno považovať aj za príklad, keď uzol môže reagovať ľubovoľne dlho).
Teraz, keď vieme, ako v princípe funguje konsenzuálny algoritmus, otázka pre tých zvedavých čitateľov, ktorí to dotiahli až sem: koľko uzlov v systéme N uzlov s asynchrónnym modelom správ môže zlyhať, aby systém stále mohol dosiahnuť konsenzus?
Za spoilerom je správna odpoveď a zdôvodnenie.Správna odpoveď je: 0. Ak čo i len jeden uzol v asynchrónnom systéme zlyhá, systém nebude schopný dosiahnuť konsenzus. Toto tvrdenie dokazuje v určitých kruhoch dobre známa veta FLP (1985, Fischer, Lynch, Paterson, odkaz na originál na konci článku): „Nemožnosť dosiahnuť distribuovaný konsenzus, ak zlyhá aspoň jeden uzol .“
Chlapi, potom máme problém, sme zvyknutí, že všetko je asynchrónne. A je to tu. Ako ďalej žiť?
Hovorili sme len o teórii, o matematike. Čo znamená „konsenzus nemožno dosiahnuť“ v preklade z matematického jazyka do nášho – inžinierstva? To znamená, že „nie vždy sa dá dosiahnuť“, t.j. Existuje prípad, v ktorom nie je možné dosiahnuť konsenzus. Čo je to za prípad?
Toto je presne vyššie popísané porušenie vlastnosti živosti. Nemáme spoločnú dohodu a systém nemôže dosiahnuť pokrok (nemôže sa dokončiť v konečnom čase) v prípade, že nemáme odpoveď zo všetkých uzlov. Pretože v asynchrónnom systéme nemáme predvídateľný čas odozvy a nemôžeme vedieť, či sa uzol zrútil, alebo či mu odpoveď len trvá dlho.
V praxi však vieme nájsť riešenie. Nech je náš algoritmus schopný pracovať dlho v prípade porúch (potenciálne môže fungovať donekonečna). Ale vo väčšine situácií, keď väčšina uzlov funguje správne, budeme mať pokrok v systéme.
V praxi sa zaoberáme čiastočne synchrónnymi komunikačnými modelmi. Čiastočná synchronizácia sa chápe takto: vo všeobecnom prípade máme asynchrónny model, ale formálne je zavedený určitý koncept „globálneho času stabilizácie“ určitého časového bodu.
Táto chvíľa nemusí prísť na dlho, ale raz musí prísť. Zazvoní virtuálny budík a od toho momentu vieme predpovedať časový delta, za ktorý správy prídu. Od tohto momentu sa systém mení z asynchrónneho na synchrónny. V praxi sa zaoberáme práve takýmito systémami.
Algoritmus Paxos rieši problémy konsenzu
je rodina algoritmov, ktoré riešia problém konsenzu pre čiastočne synchrónne systémy, pričom existuje možnosť, že niektoré uzly môžu zlyhať. Autorom Paxosu je . V roku 1989 navrhol formálny dôkaz existencie a správnosti algoritmu.
Ukázalo sa však, že dôkaz nie je ani zďaleka triviálny. Prvá publikácia bola vydaná až v roku 1998 (33 strán) popisujúca algoritmus. Ako sa ukázalo, bolo to mimoriadne náročné na pochopenie a v roku 2001 vyšlo vysvetlenie k článku, ktoré zabralo 14 strán. Objem publikácií je uvedený s cieľom ukázať, že problém konsenzu v skutočnosti nie je vôbec jednoduchý a za takýmito algoritmami sa skrýva obrovské množstvo práce tých najmúdrejších ľudí.
Je zaujímavé, že sám Leslie Lamport vo svojej prednáške poznamenal, že v druhom výkladovom článku je jeden výrok, jeden riadok (nešpecifikoval ktorý), ktoré možno interpretovať rôznymi spôsobmi. A z tohto dôvodu veľké množstvo moderných implementácií Paxos nefunguje úplne správne.
Podrobná analýza Paxosovej práce by zabrala viac ako jeden článok, preto sa pokúsim veľmi stručne sprostredkovať hlavnú myšlienku algoritmu. V odkazoch na konci môjho článku nájdete materiály na ďalšie ponorenie sa do tejto témy.
Úlohy v Paxose
Algoritmus Paxos má koncepciu rolí. Zoberme si tri hlavné (existujú úpravy s ďalšími rolami):
- Navrhovatelia (možno použiť aj výrazy: vedúci alebo koordinátori). Sú to chlapci, ktorí sa od používateľa dozvedia o nejakej novej hodnote a prevezmú rolu lídra. Ich úlohou je spustiť kolo návrhov na novú hodnotu a koordinovať ďalšie kroky uzlov. Paxos navyše umožňuje prítomnosť niekoľkých lídrov v určitých situáciách.
- Prijímatelia (voliči). Sú to uzly, ktoré hlasujú za prijatie alebo odmietnutie určitej hodnoty. Ich úloha je veľmi dôležitá, pretože na nich závisí rozhodnutie: do akého stavu sa systém dostane (alebo neprejde) po ďalšej fáze konsenzuálneho algoritmu.
- študujúci. Uzly, ktoré jednoducho akceptujú a zapíšu novú akceptovanú hodnotu, keď sa stav systému zmení. Nerozhodujú, len prijímajú dáta a môžu ich odovzdať koncovému užívateľovi.
Jeden uzol môže kombinovať niekoľko rolí v rôznych situáciách.
Pojem kvóra
Predpokladáme, že máme systém N uzly A z nich maximum F uzly môžu zlyhať. Ak F uzly zlyhajú, musíme mať aspoň 2F+1 akceptorové uzly.
Je to potrebné, aby sme vždy, aj v najhoršej situácii, mali väčšinu „dobrých“ uzlov, ktoré fungujú správne. Teda F+1 „dobré“ uzly, ktoré súhlasili, a bude akceptovaná konečná hodnota. V opačnom prípade môže nastať situácia, že naše rôzne lokálne skupiny nadobudnú rôzne významy a nebudú sa vedieť medzi sebou dohodnúť. Na víťazstvo v hlasovaní preto potrebujeme absolútnu väčšinu.
Všeobecná predstava o tom, ako funguje konsenzuálny algoritmus Paxos
Algoritmus Paxos zahŕňa dve veľké fázy, z ktorých každá je rozdelená do dvoch krokov:
- Fáza 1a: Pripravte sa. Počas prípravnej fázy vedúci (navrhovateľ) informuje všetky uzly: „Začíname novú fázu hlasovania. Máme tu nové kolo. Číslo tohto kola je n. Teraz začneme hlasovať." Zatiaľ len hlási začiatok nového cyklu, no neoznamuje novú hodnotu. Úlohou tejto fázy je začať nové kolo a informovať každého o jeho jedinečnom čísle. Číslo kola je dôležité, musí to byť hodnota väčšia ako všetky predchádzajúce hlasovacie čísla od všetkých predchádzajúcich lídrov. Pretože práve vďaka okrúhlemu číslu ostatné uzly v systéme pochopia, aké aktuálne sú údaje vedúceho. Je pravdepodobné, že ostatné uzly už majú výsledky hlasovania z oveľa neskorších kôl a jednoducho povedia lídrovi, že zaostáva za časom.
- Fáza 1b: Sľub. Keď akceptorské uzly dostanú číslo novej fázy hlasovania, sú možné dva výsledky:
- Číslo n nového hlasovania je väčšie ako číslo akéhokoľvek predchádzajúceho hlasovania, na ktorom sa prijímateľ zúčastnil. Potom akceptant pošle vedúcemu sľub, že sa už nezúčastní na ďalších hlasovaniach s číslom nižším ako n. Ak akceptant už za niečo hlasoval (teda už v druhej fáze prijal nejakú hodnotu), tak k svojmu sľubu pripojí prijatú hodnotu a číslo hlasu, na ktorom sa zúčastnil.
- V opačnom prípade, ak prijímateľ už vie o hlase s vyšším číslom, môže jednoducho ignorovať prípravný krok a neodpovedať vedúcemu.
- Fáza 2a: Prijať. Vodca musí počkať na odpoveď od kvóra (väčšina uzlov v systéme) a ak dostane požadovaný počet odpovedí, má dve možnosti vývoja udalostí:
- Niektorí z prijímateľov poslali hodnoty, za ktoré už hlasovali. V tomto prípade vedúci vyberie hodnotu z hlasovania s maximálnym počtom. Nazvime túto hodnotu x a odošle správu všetkým uzlom ako: „Prijať (n, x)“, kde prvá hodnota je hlasovacie číslo z vlastného kroku návrhu a druhá hodnota je to, na čo sa všetci zhromaždili, t.j. hodnotu, za ktorú vlastne hlasujeme.
- Ak nikto z prijímateľov neposlal žiadne hodnoty, ale jednoducho sľúbil, že budú hlasovať v tomto kole, líder ich môže vyzvať, aby hlasovali za svoju hodnotu, hodnotu, pre ktorú sa stal lídrom v prvom rade. Nazvime to y. Všetkým uzlovým bodom pošle správu ako: „Prijať (n, y)“, podobne ako v predchádzajúcom výsledku.
- Fáza 2b: Prijaté. Ďalej akceptorské uzly po prijatí správy „Prijať(...)“ od vedúceho s ňou súhlasia (pošlite všetkým uzlom potvrdenie, že súhlasia s novou hodnotou), iba ak neprisľúbili nejaké (iné) ) lídra zúčastniť sa hlasovania s číslom kola n' > n, inak žiadosť o potvrdenie ignorujú.
Ak väčšina uzlov odpovedala na vedúceho a všetky z nich potvrdili novú hodnotu, potom sa nová hodnota považuje za prijatú. Hurá! Ak sa nedosiahne väčšina alebo existujú uzly, ktoré odmietli prijať novú hodnotu, všetko sa začína odznova.
Takto funguje algoritmus Paxos. Každá z týchto etáp má veľa jemností, prakticky sme nezohľadnili rôzne typy zlyhaní, problémy viacerých lídrov a oveľa viac, ale účelom tohto článku je len predstaviť čitateľovi svet distribuovaných počítačov na vysokej úrovni.
Za zmienku tiež stojí, že Paxos nie je jediný svojho druhu, existujú aj iné algoritmy, napr. , ale toto je téma na iný článok.
Odkazy na materiály na ďalšie štúdium
Úroveň začiatočníka:
- , Preethi Kasireddy, článok na blogu Medium
- , Adi Kancherla, článok na blogu Medium
- , Ittai Abraham, blog
- , Ittai Abraham, článok na blogu
Úroveň Leslie Lamport:
- , Fischer, Lynch a Paterson, výskumná práca, 1985
- , Leslie Lamport, výskumná práca, 1998
- , Leslie Lamport, výskumná práca, 2001
Zdroj: hab.com