Konsenzus (agreement, shoda) je fundamentální problém koordinace: Jak dosáhnout shody mezi procesy na jedné hodnotě, i když některé uzly selhávají nebo je síť nespolehlivá?

Je to jeden z nejtěžších a nejdůležitějších problémů v distribuovaných systémech.

[!note] Vztah k uspořádání (komunikace v distribuovaných systémech)#Totální uspořádání (total ordering) Totální uspořádání a dosažení konsensu je ve své podstatě ten samý problém. V totálním uspořádání se uzly musejí dohodnout jaká je jedna korektní sekvence zpráv. Algoritmy na tyto dva problémy se dají použít na oba

Proč je konsenzus důležitý?

Konsenzus je základní stavební kámen pro:

• State Machine Replication - všechny repliky musí aplikovat operace ve stejném pořadí
• Leader Election - kdo je leader?
• Group Membership - kdo je součástí skupiny?
• Distribuované databáze - na jaké hodnotě se shodneme?
• Blockchain - jaký je další blok v řetězci?

Bez konsenzu nelze stavět spolehlivé distribuované systémy.

vztah konsenzu a detekce globálního stavu

Formální definice problému

Proces $P_i$ navrhuje hodnotu $v_i$. Konsenzus algoritmus musí zajistit:

1. Termination

Každý správný (nehavarovaný) proces se nakonec rozhodne pro nějakou hodnotu.

2. Agreement

Všechny správné procesy se rozhodnou pro stejnou hodnotu.

\(\forall i, j: \text{decide}_i = \text{decide}_j\)

3. Validity

Pokud se všechny procesy rozhodnou pro hodnotu $v$, pak $v$ byla navržena nějakým procesem.

Jinými slovy: Nelze “vymyslet” hodnotu, která nebyla navržena.

4. Integrity

Každý proces se rozhodne nejvýše jednou.

Teoretické limity

problém dvou armád

V nespolehlivé síti nelze dosáhnout 100% jistoty o shodě (nekonečná regrese potvrzení).

FLP impossibility

V asynchronním systému nelze garantovat deterministický konsenzus při selhání byť jen jednoho procesu.

Jak to obejít v praxi?

1. Částečná synchronie - předpoklad, že zprávy dorazí “nakonec” (ne nekonečně dlouho)
2. Timeouts - považuj proces za mrtvý po timeoutu (riziko false positive)
3. Randomizace - probabilistické algoritmy (např. Ben-Or)
4. Failure detectors - odhad, kdo je živý/mrtvý

Praktické algoritmy (paxos, RAFT):

• Obětují garantovanou terminaci (mohou se zaseknout při edge cases)
• Ale v praxi fungují dobře (částečná synchronie drží)

Rozdělení konsenzus algoritmů

Podle typu selhání

Crash fault tolerance (CFT)

• paxos - složitý, teoreticky elegantní
• RAFT - jednodušší

  Byzantine Fault Tolerance (BFT)

  Algoritmy pro systémy, kde procesy mohou lhát nebo se chovat libovolně špatně.

• PBFT (practical byzantine fault tolerance)

Probabilistický BFT:

• proof of work (PoW) - Bitcoin, Ethereum (do 2022)
• proof of stake (PoS) - Ethereum 2.0, Cardano
• Škáluje na tisíce uzlů

Podle centralizace

| Typ | Příklad | Leader? | Zprávy | Odolnost | | —————— | ———– | —————– | ——- | ——– | | Leader-based | Raft, Paxos | Ano (volený) | $O(N)$ | Failover | | Leaderless | PBFT, PoW | Ne | $O(N²)$ | Vysoká |

Srovnání nejdůležitějších algoritmů

| Vlastnost | paxos | RAFT | proof of work (PoW) (Bitcoin) | | ———- | ——————– | —————————- | ————————————– | | Hlavní cíl | Bezpečnost, Obecnost | Srozumitelnost, Implementace | Sybil resistence, Open membership | | Lídr | Dočasný (Proposer) | Silný, stabilní | Probabilistický (kdo najde blok) | | Bezpečnost | Absolutní (Safety) | Absolutní (Safety) | Pravděpodobnostní (Confirmation depth) | | Komunikace | $O(N)$ zpráv | $O(N)$ zpráv | Gossip / Flooding |

Kdy použít který konsenzus?

Paxos

• Potřebuješ teoreticky čistý, provably-correct algoritmus
• Staví se kritická infrastruktura (Google-level)
• Máš tým schopný pochopit a implementovat Paxos správně

Raft:

• Chceš consensus pro praktickou aplikaci
• Potřebuješ srozumitelnou implementaci
• Staví se distribuovaná databáze, koordinační služba
• Většina případů - Raft je lepší volba

PBFT/BFT:

• Permissioned blockchain
• Kritická infrastruktura s možností kompromitace uzlů
• Do ~100 uzlů

Proof of Work

• Veřejný, permissionless blockchain
• Tisíce neznámých uzlů
• Můžeš obětovat energii za decentralizaci
• Nízký throughput je akceptovatelný

Proof of Stake

• Veřejný blockchain s nižší spotřebou energie
• Vyšší throughput než PoW

• Riziko centralizace (bohatí validují více)

Praktické systémy používající konsenzus

Klíčová poznání

1. Konsenzus je hard - FLP dokázal, že v asynchronních systémech je teoreticky neřešitelný
2. Praktické algoritmy fungují - díky částečné synchronii a timeoutům
3. Quorum je klíč - většina algoritmů používá majority quorum
4. Trade-off: CFT vs. BFT
   • CFT (Paxos/Raft): Rychlejší, jednodušší, ale nepočítá se zlovolnými uzly
   • BFT (PBFT/PoW): Odolnější, ale pomalejší a složitější
5. Raft > Paxos (pro většinu aplikací) - jednodušší, srozumitelnější, stejně správný