はじめに
タイトルにも挙げた二つのワードですが、あまり聞きなれない方もいるのではないかと思います.かくいう私も最近勉強し始めた内容なんですけども・・・
この記事はそんな初心者のちょっとしたアウトプットとして読んでいただければ幸いです.
分散合意アルゴリズム
そもそも「合意」ってどんな意味なんでしょうね？言葉は知ってるけど、日常では滅多に使わない言葉ですよね.調べてみると色々出てきますが、大体こんな意味みたいですね
二人以上の者の意見が一致すること
という事で,言葉から読み取るには分散している環境で意見を一致させるアルゴリズムなんだという事なんですね.
つまりどういうこと？
このアルゴリズムが活躍しているのは分散された環境です.世の中色んなシステムが分散できますよね.DBとか最近よく耳にするKubernetesとか、僕たちが目にしない日なんてないwebも分散してますね.
そして、分散しているからといってシステムを構成しているマシンが各々好き勝手にデータの保持だったり命令を実行してたら一つのシステムとして機能しません.
分散合意アルゴリズムは、分散システムでそういったことが起こらないように、一貫性だったり可用性、耐故障性を実現するためのアルゴリズムです.合意の意味に沿って言うと、分散システムを構成している二つ以上のプロセスが、持っているデータや実行する命令などを同一にするっていう感じになると思います.
例えばどんなの
Raft
Kubernetesの分散KVSであるetcdを動かしている分散合意アルゴリズムです.qiitaを使わせていただいている限りだと、Raftを解説するコンテンツが豊富で,論文を読まなくても基本的な部分は理解させていただけます.先人の方々の解説記事がとても優秀なのでもしこの記事を読んで興味がわきましたら探して読んでみてください
Paxos
合意アルゴリズムの金字塔 とRaftの論文でも言われている通り、とても有名な合意アルゴリズムです.様々な合意アルゴリズムが,このPaxosを元に生まれていきました.
とても素晴らしいアルゴリズムという事なのですが,如何せん論文が難解であり,アルゴリズムを理解するのが難しいとのことです.私も先人の方々の解説を拝見させていただいてるのですが,まだ私のポンコツ脳は完璧には理解できていません.
上のRaftは「Paxosは理解するの難しいから実装方法も統一されないし・・・だったらもっと理解が簡単で同じくらいの性能のやつ作ろう！」みたいなスタンスで生まれた感じです.Raftの論文でもこの名前は序盤に結構出てきます.それだけ、意識されるくらいの存在感があるってことなんだと思います.
ちなみに、考案者はレスリー・ランポート先生という方なのですが、この方はLaTeXを作った方でもあります.
ビザンチン将軍問題
時はさかのぼること幾星霜、舞台のビザンチン帝国で9人の将軍が攻撃か撤退かを多数決で決める事になりました。過半数以上が攻撃なら全員で攻撃,過半数以上が撤退なら全軍撤退.さて、ここで賛成4人,反対4人になっている状態です.9人目のあなたが裏切り者で,ビザンチン帝国を負けさせたい場合,どうしますか？
みたいな感じの話が元ネタ(?)の問題です.作戦を失敗にする方法は,考えればいろいろ出てくると思います.賛成4人に賛成,反対４人に反対の意見を送ったりとかetc
概要
間違った情報を伝達する存在(裏切り者)がいる場合に全体として正しい合意を形成できるかを問う問題を一般的にビザンチン将軍問題といいます.
そして、このようなビザンチン将軍問題に帰結される故障や障害をビザンチン故障、ビザンチン障害と言い、これらに耐性がある事を一般にビザンチン故障耐性(Byzantine Fault Tolerance：BFT)があると言います
先ほど名前の挙がったのレスリー・ランポート先生を含めた3人の方々が1980年頃に出した「The Byzantine Generals Problem」という論文で分散コンピューティング上の問題として定義されました.論文中では,裏切り者が3分の1以下であればBFTが達成できるといわれています.
まとめ
最近では,ブロックチェーンの分野でよく取り上げられるワードたちだと思います.ブロックチェーンの合意アルゴリズムは、ビザンチン障害にも耐えられるように設計されています.仮想通貨などのお金を扱うシステムに多く取り入れられているので悪意のあるものからの攻撃に晒される機会が多いからなのかなと思います.
おわりに
分散合意アルゴリズムとビザンチン将軍問題について触れてみました.このアルゴリズムを覚えれば直接何かの役に立つとは言いにくいですが、今日の情報社会では分散システムは無くてはならないシステム形態です.システムのいつもより中の部分について知るというのも面白いのかなとは思います.
記事は以上になります。お疲れさまでした。