この記事は何?

分散環境下において合意を取るためのプロトコルがいくつか存在するので、それらを簡単にまとめることとする。

※分散システムの勉強を兼ねて書いておりますので、間違い等ありましたらご指摘頂けると幸いです。

利用用途

分散合意プロトコルは、以下のようなシチュエーションで使われている:

リーダ選出 (Leader election)

例. master-slaveモデルの分散システムにおいてmasterがダウンした際に、master eligible nodesから次なるmasterを選出する

ログ複製の管理 (Replicated state machine)

例. masterが正しいログを保持し、複製を他のnodesに配る

そもそも合意って何?

"The distributed consensus problem deals with reaching agreement among a group of processes connected by an unreliable communications network"

プロセス系全体として一つの値を決定すること、だと解釈している。

例えば5人の人間A,B,C,D,Eが存在し、お昼ご飯について合意を取るとする。

A,B,Cがラーメンを食べる、Dがカレーを食べる、Eが寿司を食べるとなった時、多数決を取り「ラーメンを食べる」で系として合意を得るイメージ?

分散合意プロトコルの話に入る前に、前提となる背景知識について述べる。

背景知識

Byzantine Generals Problem (1982)

Byzantine Generals Problem(ビザンチン将軍問題)は "相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題" である。 (Wikipediaより)

例え話として、通信など無縁な時代において、小国A, B, C, D, Eの軍隊らが協力し、大国Fを攻めようと画策している状況を考える。

当然A-E単独で攻め込んだところで返り討ちに合うことは目に見えているため、協力して大国Fを攻め落とそうという話になった。

しかし、A-Eは地理的に離れているため、協力するためには攻撃の日を "合意" することで決定する必要がある。

ある小国ともう一方の小国における "通信" 手段は連絡兵を送り合うことのみであるが、小国間には危険な地域があるため、連絡兵がもう一方の小国へ無事に辿り着けない可能性がある。

さらには、A-Eのどれかの国が裏切りを図る可能性もある。

このような状況下でA-E全体として正しい合意を得られるか？を問う問題である。

同期システムの場合、特に弱ビザンチン将軍問題において 3t < n (n: ノード数, t: 障害数) であれば、合意をとることができる (逆にいうと the oral-messages model において3t ≧ n の場合に解決できないことが示されている)

the oral-messages modelは以下参照。

www.blockchainengineer.tokyo

一方、非同期システムの場合、障害が発生した場合において有限時間内に合意を取る方法はない https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf ということがMichael J. Fischer, Nancy Lynch, and Mike Patersonらによって示されている。これをFLP impossibilityと呼び、後述する。

ビザンチン将軍問題 - Wikipedia