Byzantine generals problem

Angol

Főnév

Byzantine generals problem (tsz. Byzantine generals problems)

(informatika) A Byzantine Generals Problem (BGP) egy alapvető konszenzus‐probléma az elosztott rendszerekben, amely a megbízható döntéshozatal kérdését vizsgálja akkor, ha egyes szereplők (csomópontok, katonai hadvezérek) akár rosszindulatúan (Byzantine hiba) is viselkedhetnek. Leslie Lamport és munkatársai fogalmazták meg 1982-ben.

1. A probléma leírása

Képzeljünk el ${\textstyle n}$ római hadvezért, akik különálló táborokban állomásoznak egy ellenséges város körül. Minden hadvezérnek el kell döntenie, támadjanak-e („Attack”) vagy vonuljanak vissza („Retreat”). A siker érdekében:

Egységes döntésre kell jutniuk: minden lojalitásban maradt hadvezér ugyanazt a parancsot hozza.
Ha a főparancsnok („commander”) lojalitásos („loyal”) és parancsot ad, minden lojalitásos tiszt végrehajtja azt.

Viszont akár a főparancsnok, akár bármelyik alhadvezér lehet csaló («Byzantine»), aki üzeneteket hamisít, késve vagy összevissza küldi őket. A kérdés: milyen kommunikációs és döntési protokoll mellett képesek a lojalitásos hadvezérek konszenzusra jutni, ha legfeljebb ${\textstyle f}$ hiba lehet?

2. Modell és feltételezések

Csomópontok: ${\textstyle n}$ generális, köztük 1 potenciális főparancsnok és ${\textstyle n-1}$ alhadvezér.
Hibák típusa: Byzantine – a csalók tetszőleges, akár rosszindulatú viselkedést tanúsíthatnak (ellentmondó vagy hiányos üzenetek).
Kommunikáció: privát, hitelt érdemlő hitelesített csatornákon. Két modell:
- Oral messages (hitelesítés nélküli): a küldő személyazonosságát lehet bizonyítani, de tartalom hamisítható.
- Signed messages (digitális aláírással): a csaló nem hamisíthatja más alhadvezér aláírását.
Synchronous környezet: az üzenetek garantáltan egy ismert, korlátos időn belül megérkeznek.

3. Megoldhatósági határok

Oral messages esetén
- Konszenzus csak akkor lehetséges, ha
  
  $n>3f.$
- Tehát a megengedhető csalók száma ${\textstyle f<{\frac {n}{3}}}$ .
- A megoldás általában rekurzív üzenetküldést használ (Lamport–Shostak–Pease protokoll), és ${\textstyle f+1}$ körben zajlik.
Signed messages esetén
- Ha a hitelesített aláírás biztosított, akkor elegendő
  
  $n>f,$
  
  vagyis bármennyi hiba esetén működik, amíg marad legalább egy lojalitásos alhadvezér.
- Az aláírások segítségével a csomagút követhető, nincs szükség rekurzióra.

4. A Lamport–Shostak–Pease protokoll (oral messages)

A legegyszerűbb eset ${\textstyle f=1}$ , ${\textstyle n=4}$ generális. A protokoll:

Kör 0: a főparancsnok (“ ${\textstyle \mathrm {Cmd} }$ ”) elküldi az „Attack” vagy „Retreat” parancsát minden alhadvezérnek.
Kör 1: minden alhadvezér, aki üzenetet kapott, továbbküldi azt minden más alhadvezérnek. Akik semmit sem kaptak, üres értéket („Ø”) továbbítanak.
Döntés: minden alhadvezér rekúrral definiált függvénnyel („majority‐vote”) dönt: ha legalább két „Attack” érkezett, támad; ha kettő „Retreat”, hátrál; egyébként „Retreat”.

Általános ${\textstyle f}$ esetén ${\textstyle f+1}$ kört futtatunk, minden kör új rekurzív réteget ad hozzá.

5. Várakozásos és aszinkron kiterjesztések

Synchronous vs. Asynchronous A fenti protokoll a szinkron környezetre épül. Aszinkron rendszerben (ismeretlen késleltetések, esetleges kiesések) FLP-tétel (Fischer–Lynch–Paterson) bizonyítja, hogy nem létezik determinisztikus, toleráns konszenzus aszinkron környezetben, ahol még 1 csomópont is elhalálozhat.
Probabilistic és végzetes eljárások – Randomized Byzantine Agreement: véletlen penny-flipeléssel elérhető aszimptotikusan gyors konszenzus bizonyos hiba-ráta mellett. – Leader‐based protokollok: pl. PBFT (Practical Byzantine Fault Tolerance), amely szinkron modellhez közeli generálódási sorozatot használ, és optimista gyorsítást.

6. Practical Byzantine Fault Tolerance (PBFT)

Mikro-szolgáltatások és blokkláncok inspirálta protokoll:

Rétegek: Pre‐prepare, Prepare, Commit, Reply üzenetek.
Replikák: ${\textstyle n=3f+1}$ példány, elosztott szolgáltatás, melyeket ügyfelek kérdeznek le.
Vezetőcsomópont (primary) forgása a view-change mechanizmus és checkpointing révén.
Teljesítmény: alacsony késleltetés és magas átbocsátóképesség, amíg ${\textstyle f}$ elosztott hiba nem lép fel.

7. Alkalmazások

Distributed databases: megbízható tranzakciók és replikáció.
Blokkláncok és kriptovaluták: permissioned hálózatok (Hyperledger Fabric, Tendermint) PBFT‐szerű konszenzust használnak.
Missziós kritikus rendszerek: repülésirányítás, védelmi és koszmunikációs rendszerek.

8. Összefoglaló

A Byzantine Generals Problem rávilágít arra, hogy háromszor annyi résztvevőre van szükségünk, mint a megengedett hibák száma, ha nem tudjuk hitelesíteni az üzeneteket, és aszinkron környezetben determinisztikus konszenzus nem lehetséges. A probléma megoldása alapvető a megbízható elosztott rendszerekben, és a modern protokollok – mint a PBFT – közvetlenül ebből nőnek ki.

További információk

Byzantine generals problem - Szótár.net (en-hu)
Byzantine generals problem - Sztaki (en-hu)
Byzantine generals problem - Merriam–Webster
Byzantine generals problem - Cambridge
Byzantine generals problem - WordNet
Byzantine generals problem - Яндекс (en-ru)
Byzantine generals problem - Google (en-hu)
Byzantine generals problem - Wikidata
Byzantine generals problem - Wikipédia (angol)