A bizánci tábornokok feladata

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. július 23-án felülvizsgált verziótól ; az ellenőrzések 13 szerkesztést igényelnek .

A bizánci tábornokok feladata a kriptológiában több távoli előfizető interakciója, akik egy központtól kaptak parancsot. Az előfizetők egy része, beleértve a központot is, behatolók lehetnek (vagy a behatolók üzenetet váltottak az átvitel során). Egységes, az előfizetők számára előnyös cselekvési stratégiát kell kidolgozni.

Eredeti megfogalmazás

Bizánc . Az ellenséggel vívott nagy csata előtti este. A bizánci hadsereg légiókból áll , amelyek mindegyikét a saját tábornoka irányítja. A hadseregnek van egy főparancsnoka is, akinek a tábornokok vannak alárendelve. $n$

Ugyanakkor a birodalom hanyatlóban van, és bármelyik tábornok, sőt a főparancsnok is lehet Bizánc árulója, aki érdekelt annak vereségében.

Éjszaka mindegyik tábornok parancsot kap a főparancsnoktól, hogy mit kell tenni reggel 10 órakor (az idő mindenki számára azonos, és előre ismert). Rendelési lehetőségek: „támadás az ellenség ellen” vagy „visszavonulás”.

A csata lehetséges kimenetele:

Ha minden hűséges tábornok támad, Bizánc elpusztítja az ellenséget (kedvező eredmény).
Ha minden hűséges tábornok visszavonul, Bizánc megtartja hadseregét (köztes eredmény).
Ha néhány hűséges tábornok támad, és néhányan visszavonulnak, az ellenség végül részenként elpusztítja Bizánc teljes hadseregét (kedvezőtlen eredmény).

Azt is szem előtt kell tartani, hogy ha a főparancsnok áruló, akkor a hadsereg megsemmisítésének biztosítása érdekében ellentétes parancsokat adhat a különböző tábornokoknak. Ezért a tábornokoknak számolniuk kell ezzel a lehetőséggel, és kerülniük kell az összehangolatlan akciókat.

Ha mindegyik általános a többitől teljesen függetlenül cselekszik (például véletlenszerűen választ), akkor a kedvező kimenetel valószínűsége nagyon kicsi.

Ezért a tábornokoknak információt kell cserélniük egymás között, hogy egységes döntésre jussanak.

Finomított definíció

Hagyja , hogy a "sárga" tábornokok vezessék a seregeket a hegyekben, és készüljenek a "kékek" megtámadására a völgyben. A kommunikációhoz a támadók megbízható csatornát használnak, amely kizárja az elhangzottak helyettesítését, például egy memorizált megállapodást, amelyet egy bizonytalansági helyzet kialakulása előtt alakítottak ki. A tábornokok egy része azonban megfigyelhetően az ellenség oldalán áll, és aktívan próbálják megakadályozni a megállapodás tábornokai egyhangú egyetértését. A megállapodás az, hogy minden tábornok valós információval rendelkezik az összes részt vevő hadsereg méretéről, és ugyanazokra a következtetésekre jut (bár hamisak) az ellenséges hadseregek állapotáról. Az eredeti megfogalmazás szerint az utolsó feltétel különösen fontos, ha a tábornokok a kapott adatok alapján a „harmadik kizárásának” stratégiáját tervezik kidolgozni . $n$ $n$ $m$

Formalizálás

A csere eredményeként minden tábornoknak egy n hosszú egész vektort kell kapnia, amelyben az i-edik elem vagy egyenlő az i-edik hadsereg valódi méretével (ha a tábornok megfelel a megállapodásnak) , vagy dezinformációt tartalmaz az i-edik hadsereg méretéről (ha annak tábornoka nem tartja be az i nullától n-re vonatkozó megállapodást, a főparancsnokhoz rendelt). Ugyanakkor az összes hűséges parancsnok által kapott vektoroknak pontosan azonosaknak kell lenniük.

Megoldási algoritmusok

Különleges eset

Leslie Lamport 1982-ben javasolt egy rekurzív megoldási algoritmust arra az esetre, amikor a tábornokok száma korlátozott és nem változhat dinamikusan . Az algoritmus a tábornokok közötti árulók esetének problémáját az áruló esetére redukálja . $m$ $n$ $m-1$

Az esetre nézve az algoritmus triviális, ezért illusztráljuk az és esetre . Ebben az esetben az algoritmus 4 lépésben történik. $m=0$ $n=4$ $m=1$

1. lépés . Minden tábornok üzenetet küld a többieknek, amelyben jelzi serege méretét. A hűséges tábornokok a valódi számot jelentik, míg az árulók különböző számokat jelenthetnek különböző üzenetekben. Az 1-es tábornok az 1-es (ezer katona), a 2-es tábornok a 2-es, a 3-as tábornok (hazaáruló) a másik három tábornokot jelölte, rendre , , (a valódi érték 3), a 4-es pedig 4-et. $x$ $y$ $z$

2. lépés . Mindegyik saját vektort alkot a rendelkezésre álló információkból:

Általános #1 vektor: (1,2,x,4);
Általános #2 vektor: (1,2,y,4);
Általános #3 vektor: (1,2,3,4);
Általános #4 vektor: (1,2,z,4).

3. lépés . Mindenki elküldi a vektorát mindenki másnak (az általános 3 ismét tetszőleges értékeket küld).

Ezt követően minden általánosnak négy vektora van:

g1	g2	g3	g4
(1,2,x,4)	(1,2,x,4)	(1,2,x,4)	(1,2,x,4)
(1,2,y,4)	(1,2,y,4)	(1,2,y,4)	(1,2,y,4)
(a, b, c, d)	(e,f,g,h)	(1,2,3,4)	(i,j,k,l)
(1,2,z,4)	(1,2,z,4)	(1,2,z,4)	(1,2,z,4)

4. lépés . Minden tábornok maga határozza meg az egyes hadseregek méretét. A -. hadsereg méretének meghatározásához minden tábornok számokat vesz - ennek a hadseregnek a méretét, amely minden parancsnoktól származott, kivéve a -edik hadsereg parancsnokát. Ha ezek között a számok között valamilyen érték legalább egyszer megismétlődik, akkor az a kapott vektorba kerül, ellenkező esetben az eredményül kapott vektor megfelelő eleme ismeretlennek (vagy nullának stb.) van jelölve. $én$ $(n-1)$ $én$ $(n-1)$ $(nm-1)$

Minden hűséges tábornok kap egy vektort , ahol van egy szám, amely legalább kétszer előfordul az értékei között , vagy "ismeretlen", ha mindhárom szám különbözik. Mivel minden hűséges tábornok értéke és funkciója azonos, megegyezés született. $(1,2,f(x,y,z),4)$ $f(x,y,z)$ $(x,y,z)$ $(x,y,z)$ $x,y,z$ $f$

Általános eset

Összekapcsolt szekvenciális blokkokból álló láncok felépítése a munka igazolásával kombinálva – amelyet először a „ Bitcoin ” kriptovalutában használtak – elfogadható kockázati szint mellett lehetővé tette a dinamikus döntéshozatali mechanizmus létrehozását e probléma általánosabb esetben. amikor az általánosok ( hálózati csomópontok ) száma nem pontosan ismert, és dinamikusan tetszőlegesen változhat.

Problémakutatási eredmények

Lamport bebizonyította, hogy a nem megfelelően működő processzorokkal („hűtlen tábornokok”) működő rendszerben csak akkor lehet megegyezni, ha vannak megfelelően működő processzorok („hűséges tábornokok”), vagyis ha szigorúan több „helyes” van, mint az összes szám. $m$ $2m+1$ $2/3$

Alkalmazás

Bitcoin és más kriptovaluták [1] .
Óra szinkronizálás

Lásd még

Jegyzetek

↑ Marc Andressen . Miért számít a Bitcoin ? The New York Times (2014. január 21.). Letöltve: 2015. október 2. Az eredetiből archiválva : 2014. január 31.. ( Marc Andressen . Miért olyan fontos a Bitcoin? . Habrahabr.ru. Hozzáférés dátuma: 2015. október 2. Archiválva : 2014. január 28. (Orosz) - fordítási lehetőség).