CDSLの岡田です。このブログではCDSLのメンバーが研究室の活動の紹介や実用的なコンテンツを提供してくれています。私も例に漏れず活動報告や役立つコンテンツを提供しようとは思いましたが、他メンバーのようないい感じの記事を提供できそうにありません。なので、本記事では直接的に役立つとは思えませんが、コンピュータの分野における問題の一つをご紹介させて頂こうと思います。
導入 ~みんなで外食に行こう~
あなたと２人の友人の計３人で外食に行くことになりました(ここでは, Aさん, Bさん, あなた, とします)。じゃんけんでAさんがお店の決定や予約といった幹事の役割を担う事になりました。Aさんは二人に行くお店を連絡します。念のため、あなたとBさんの２人でもどのお店に行くことになったのか確認することにしました。
さて、あなたに届いた連絡は以下の通りになりました。
あれ？おかしいですね・・・二人からの連絡はそれぞれ違うお店に予約してある事を言ってますね。Aさんが幹事をして２人に連絡してるんだから、Bさんも同じお店を言うはずなのに・・・・
皆さんのお察しの通り、この３人の中に全員集まって外食したくないので本当の事とは違う事を連絡する、いわば裏切り者がいるみたいです。このご時世です。密を避けたいのかもしれないですね。
ではどうすれば、３人で集まれるでしょうか。普通に考えればAさんが幹事ですしAさんの指示に従えば良いように思えます。しかし、もしかしたら、Aさんは△△店に予約を入れてBさんにはそのまま連絡して、あなたには違った内容を送信しているかも。いや、でも普通に考えたらBさんが裏切り者では・・・？
これでは正常な合意形成(この場合は、３人で同じお店に行く)が出来ないという事が分かるかと思います。このように、間違った情報を伝達する存在がいる場合に全体として正しい合意を形成できるかを問う問題を一般的にビザンチン将軍問題と言います。
閑話休題 ~ビザンチン将軍問題~
元ネタは４世紀以降にヨーロッパで栄えたビザンチン帝国を舞台にしたこんな話から来ています。
「9人の将軍が全員で攻撃するか、全員で撤退するかで投票で決める事になった。過半数の投票が入った作戦を決行することにする。そして、４人が攻撃、４人が撤退に投票しているとする。最後の１人が裏切り者だった場合、攻撃に投票した将軍たちに攻撃に投票したと伝え、撤退に投票した将軍たちに撤退に投票したと伝えて攻撃を失敗させることが出来る。さらに、時代が時代なので投票は使者によって運ばせなければならず、投票を届けるのに失敗したり、途中で偽の投票にすり替えられる可能性もある」
このビザンチン帝国の将軍たちと裏切り者の駆け引き(？)を分散コンピューティングの合意問題として定義したのはレスリー・ランポートという人物です。ランポート氏は分散システムの分野で多大な貢献をしている方で、Paxosという合意アルゴリズムを提案した人です。ちなみに、大学生が卒業論文やレポートの作成でお世話になっている(これからなるであろう)LaTeXを作った人でもあります。
分散システムのネットワーク上においても、元ネタの話のように異常な動きをするノードや通信途中でのメッセージ改ざん等で偽の情報を伝達される等で起こされる障害(作為障害)が起こる可能性を否定することは出来ません。そして、このようなビザンチン将軍問題に帰結される故障や障害をビザンチン故障、ビザンチン障害と言い、これらに耐性がある事を一般にビザンチン故障耐性(Byzantine Fault Tolerance：BFT)があると言います。
今日では、特にブロックチェーンの分野においてよく話題に挙げられているものだと思います。ブロックチェーンを構成する技術の一つにコンセンサスアルゴリズム(合意アルゴリズム)がありますが、このアルゴリズムが本問題と密接に関わっています。ちなみに、コンセンサスアルゴリズムはブロックチェーンのためだけのアルゴリズムというわけではありませんが、そのあたりは私も勉強中の身ですので、機会があればという事で・・・
終わりに
長々とお付き合いいただきありがとうございます。人間よりもはるかに優秀な演算性能を持ったコンピュータも場合によっては合意する事に苦労するというのは面白いですね。
本研究室では、クラウド・IoTを主な研究テーマをとして掲げていますが、本記事で取り上げたような問題に関係した研究もやらせてもらえるような自由度の高い研究室です。。CDSLは期間中は随時、研究室説明会をGoogle meetで開催しますので本学の3年生は、ぜひ本研究室の事を聞きに来て下さると幸いです。説明会では実際に所属しているメンバーも参加しますので、気軽に聞きたい事、相談したい事をお話ししてみてください。皆様の参加をお待ちしています。