名前がカッコいいので、ビザンチン将軍問題について調べた

名前がカッコいいので、ビザンチン将軍問題 について調べた #11 札幌開催：はじめてのIT勉強会 in 札幌(2024) @MSprzk

自己紹介

自己紹介 宮本直幸 - Miyamoto Naoyuki N高等学校（北海道情報大学に進学予定） JS, TS, Java フロントエンド、バックエンド （最近 電子工作で遊ぶのにハマってます） @Msprzk とまとくん

アジェンダ 1. ビザンチン将軍問題とは 2. 具体例 3. どこで使われているの？ 4. まとめ

ビザンチン将軍問題とは

ビザンチン将軍問題とは ビザンチン将軍問題 偽の情報を流すものが存在するとき、分散 システムが一貫性を保つためにはどうした らいいのかという問題。 この概念は1982年にレスリー・ランポート 博士らによって提唱された。 レスリー・ランポート博士 (https://www.lamport.org/ より)

• https://www.lamport.org/

具体例

具体例 ときは14XX年、 ビザンツ帝国（東ローマ帝国）という国がありました。 ビザンツ帝国

具体例 ときは14XX年、１４YY年、 ビザンツ帝国（東ローマ帝国）という国がありました。 ビザンツ帝国

具体例 ときは14XX年、１４YY年、 ビザンツ帝国（東ローマ帝国）という国がありました。 攻め込む ビザンツ帝国 BC王国（仮）

具体例 3人の場合 B A C

具体例 3人の場合 B A C

具体例 3人の場合 B(裏切り） A ？？？？？ C

具体例 4人の場合 B(裏切り） A C D

具体例 4人の場合 B(裏切り） A C D

具体例 4人の場合 B(裏切り） A C D

具体例 4人の場合 A ここでクイズ C B(裏切り） D

Q. 裏切り者が2人のときは、誠実な将軍は最低 何人いたらいいでしょうか？ A, 4人 B, 5人 C, 7人

Q. 裏切り者が2人のときは、誠実な将軍は最低 何人いたらいいでしょうか？ A, 4人 B, 5人 C, 7人

クイズ 裏切り者が n人 のとき、誠実な将軍が 2n + 1人 以上ならば ↓ 誠実な将軍は高確率で判断を一致させ られる！

どこで使われているの？

どこで使われているの？ ビザンチン将軍問題 分散システムにおける同意問題 ※ここにおける同意とは、複数のコンピュータで同じ 値を持つこと。

どこで使われているの？ 課題 コンピュータは壊れる。間違った通信や処理を始めることもある。 →分散システムやブロックチェーンにビザンチン将軍問題の考 え方を取り入れ、壊れたコンピュータを裏切り者に見立てて、 正常なコンピュータの合意を形成できるようにするといった活用 がされている。

どこで使われているの？ ブロックチェーン BFT(Byzantine Fault Tolerance)という考え方があり、ブロック チェーン分野でとても重要なものになっている。 ビットコインなど暗号資産が存在するために不可欠。 BFTなコンセンサスアルゴリズムの例 PBFT, HotStuff, Tendermint, etc…

まとめ

まとめ ● 偽の情報を流すものがいるとき、誠実に情 報を伝えるものが 2n + 1人以上いれば高確率で合意でき る。 ● ビザンチン将軍問題は、分散処理やブロック チェーンに不可欠な考え方。

参考 佐藤一郎. (2015). ‘「「ビザンチン将軍問題」とは何か」第69号 NII Today’, NII Today / 国立情報学研究所, 2015-09, https://www.nii.ac.jp/today/69/4.html (Accessed: 2025-02-26) Leslie Lamport, Robert Shostak, Marshall Pease: "The Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems, Vol.4, No.3, pp. 382-401, 1982. https://www.lamport.org/

• https://www.nii.ac.jp/today/69/4.html
• https://www.lamport.org/