Broadcast páronkénti csatornával:

Tisztességes résztvevők száma n: összes résztvevő

Csalók száma

Cél szimuláljunk broadcastot (egy résztvevő mindenkinek küld üzenetet)

- tisztességesek MIND ugyanazt higgyék

1) küldő

mindenkinek elküldi

2) A tisztességesekkel nincs baj, mert mindenkinek ugyanazt az üzenetet küldik el, a probléma a csalókkal van, akiket ki kell szűrni és ki kell zárni.

Mindenki elküldi mindenkinek, amit az 1) lépésben kapott.

A tisztességes: 1 2 i csaló n Ezaz

*

tárolja. hogy 2. üzenetben kitől mit kapott

B tisztességes: 1 2 i n

tárolja. hogy 2. üzenetben kitől mit kapott

ha az n db érték között van legalább 2/3 egyforma Þ ezaz:

ha az n db érték között nincs legalább 2/3 egyforma Þ ezaz: *

Áll: Ha A és B is értékre gondol, akkor ugyanarra gondolnak.

Biz.: A 2. üzeneteit átrendezzük:

egyforma > 2/3 n csillag

B 2. üzeneteit átrendezzük:

egyforma >2/3 n

Tekintsük azon résztvevőket, akik mindkét halmazban egyformák között vannak , ezek száma legalább 1/3, mivel:

A-nak elfogadott értéket küldték legfeljebb 2/3 n

legalább 1/3 n

B-nek elfogadott értéket küldték legfeljebb 2/3 n

Van tisztességes résztvevő, aki A-nak és B-nek is ugyanazt küldte.

3) Megpróbáljuk elérni, hogy mindenki ugyanazt az értéket vagy *-ot kapja.

Mindenki elküldi mindenkinek, hogy mit kapott, vagy a *-ot.

A tisztességes csak akkor küld *-ot, ha nem tudta elérni, hogy 2/3-os többségét.

A 3. lépésben kapott üzenetei:

* * * *

>1/3 A több mint 2/3-ban, ami nem * van legalább 1/3-nyi egyforma,

akkor elfogadjuk, ha nincs, akkor *-ot mondunk.

Áll.: Aki tisztességes vagy *-ot fogja elfogadni vagy ugyanazt az értéket.

Biz.: A többség A-nak nem *-ot üzen:

<1/3 értékek>2/3

* * * *

tiszt.

a tisztességes játékosok, mind egyformát küldenek

csalók többség

.

.

.

.

A bizánci tábornokok:

Igyekeznek összebeszélni, meg mindenkinek keresztbe tenni, ezért a tisztességesek megpróbálnak közös álláspontban megegyezni.