Byzantská dohoda

• Zadanie:

  • dva druhy procesov: spolahlivé a nespolahlivé
  • špeciálny proces generál: jeden z nich; môze byt spolahlivý alebo nespolahlivý
  • procesy navzájom komunikujú
  • kazdý má lokálnu premennú, sú ulozené v poli byz: proces x má premennú byz[x]

• Úloha: navrhnút program, ktorý ked vykonávajú spolahlivé procesy, tak všetky si nastavia rovnakú hodnotu premennej byz. Naviac, ak je generál spolahlivý, tak touto hodnotou je pociatocná hodnota generála d0[g] (dohoda medzi spolahlivými byzantskými vojvodcami [so spolahlivým generálom] o tom, ci sa má alebo nemá útocit [ako tvrdil na zaciatku generál])

• Predpokladáme, ze je

t nespolahlivých

> 2.t spolahlivých

(inak algoritmus neexistuje: napr. 1 nespolahlivý a 2 spolahliví: toto je aj základ pre dôkaz)

• Oznacenie premenných:

u, v, w ? spolahlivý proces

x, y, z ? lubovolný proces

g ? proces generál

• premenné spolahlivých procesov budeme oznacovat spolahlivé, podobne pre nespolahlivé

Previous slide

Next slide

Back to first slide

View graphic version