読者です 読者をやめる 読者になる 読者になる

ビザンチン合意と一斉射撃問題

某所で聞き損ねたこと.
そういえばCAの方の文脈で一斉射撃問題というのがあるそうだ.

一斉射撃問題
横一列に兵士が並んでいて, 適当な位置に一人将軍が居る. 命令の伝達は隣の人にしか行えない. このとき, 一斉に射撃するにはどうするか.

兵士間の伝達経路を適当にした場合には任意のグラフ上での話しになる (多分).

暗号というかMPCの文脈で似たような話としてビザンチン合意がある.

ビザンチン合意
将軍達の間に適当な数のスパイがいる. スパイの存在を考慮した上で, 正直な将軍達が一斉に攻撃または撤退するにはどうするか.

似ている気がしたが, そういえばこっちは伝達経路が完全グラフだった. あんまり似てないのかしらね. と適当なメモ.