同意問題とAtomic Broadcast

この記事のゴールは同意問題 (Consensus Problem) とAtomic Broadcast（全順序ブロードキャスト）が同等な問題であることを説明することです。
説明のみを読みたい方は「同意問題とAtomic Broadcastの同値性」までスクロールしてください。

同意問題とは何か

突然ですが、以下のお話を考えてみましょう。

二人の将軍が敵の城を攻めることにしました。攻撃は同時に行った場合にのみ成功します。
しかし、二人の将軍は離れた場所にいるため、互いに連絡を取り合う必要があります。
連絡手段は伝令の馬に頼るしかなく、伝令が敵に捕まってしまう可能性があります。
どのようにすれば、二人の将軍は確実に同時に攻撃を行うことができるでしょうか？

このお話は「Two Generals' Problem（二人の将軍問題）」として知られており、不確実な通信下での合意に関する古典的な例です。

もう少しこの例え話を掘り下げてみましょう。この問題を解決する方法はあるのでしょうか？

答え

実はこの問題は不可能であることが証明されています。

二人の将軍をそれぞれ将軍A、将軍Bとしましょう。将軍Aが「今日の18時に攻撃をしよう」と伝令を送ったとします。
この伝令は運良く敵から逃れ、将軍Bへ連絡することができました。

この時、二人の将軍は攻撃のタイミングについて同意しましたか？答えは「いいえ」です。
なぜなら、将軍Bは伝令を受け取ったことを将軍Aに伝えていないからです。

じゃあ将軍Bは伝令を受け取った後、将軍Aに「了解」と返信の伝令を送りましょう。
しかし、この返信の伝令も敵に捕まってしまうかもしれません。そして、もし捕まってしまった場合、将軍Aは将軍Bが攻撃のタイミングについて同意したかどうか分かりません。

このように、どれだけ伝令を送り合っても、敵に捕まってしまう可能性がある限り、二人の将軍は攻撃のタイミングについて同意することができません。
つまりこの問題は不可能であることが分かります。

では、どうすればこの問題を解決できるのでしょうか？

この例はあくまで直感的な説明のためのものですが、このように複数のプロセスが、ある環境の下である値について同意する問題を**同意問題 (Consensus Problem)**と呼びます。

同意問題の定式化

上では、将軍や攻撃という具体例を用いて同意問題を説明しましたが、以降は以下のように定式化して説明します。
いくつかの仮定が異なっていることに注意してください。

まず、システムは複数のプロセス (ノード) から構成され、それらはメッセージを送受信できるとします。
各プロセスは以下の二つのことを行います。

• 提案: 各プロセスは値を提案します。
• 決定: 各プロセスは提案された値の中から一つを選び、決定します。

そして、同意問題は以下の三つの条件を満たすことを要求します。

1. 終了性 (Termination): すべての正常なプロセスは最終的に決定を行う。
2. 一貫性 (Agreement): すべての正常なプロセスは同じ値を決定する。
3. 妥当性 (Validity): 決定された値は、少なくとも一つの正常なプロセスによって提案された値である。

ここで、正常なプロセスとはメッセージの送受信ができ、提案と決定の両方を決められた手順に従って正しく実行するプロセスのことだと考えてください。故障した（正常でない）プロセスは停止し、メッセージの送受信ができなくなるとします。^[1]

また送受信されるメッセージは、重複せず改竄されず、プロセスが正常である限り必ず届くものとします。ただし、いつ届くかは保証されません。
さらに、同意問題が解決可能になるための追加仮定（システムが部分同期であるなど）を置きます。

二人の将軍問題の例とは異なり、ここではメッセージがいつか必ず届くと仮定しています。
上の正常/故障の定義と合わせて気になる方は、例えば「分散システム 障害モデル」や「Failure model in distributed systems」などで調べてみてください。
実際、さまざまな故障モデルやメッセージ伝達モデルがありますが、ここでは同意問題とAtomic Broadcastの同値性を説明するために、上記のような単純なモデルを仮定しています。

Atomic Broadcast （全順序ブロードキャスト）とは何か

Atomic Broadcastとは分散システムにおけるメッセージ配信のうち、以下の性質を持つものを指します。

正常なプロセスがメッセージを受信した場合、すべての正常なプロセスがそのメッセージを受信し、同じ順序で処理することを保証する。

同意の話からずれたように感じるかもしれませんが、同意問題が難しい理由には、通信遅延や故障などにより各プロセスの観測が食い違うことが挙げられます。そこで、全員が同じ集合を同じ順序で受信できるという強い通信抽象として Atomic Broadcast を導入します。

もう少し厳密に言うと、Atomic Broadcastは以下の5つの条件を満たすことを要求します。^[2]
理解のために、Atomic Broadcastは、それぞれのプロセスに付随して動作するAtomic Broadcastプロセス(ABP)によって実現されていると考えてください。

各プロセスと付随するABP間はメッセージが失われず、ABP間はメッセージが失われる可能性がある通信路で接続されています。^[3]

プロセスとAtomic Broadcastプロセスの関係図

プロセスは、この付随したABPにメッセージの配信要求を行います。

配信と送受信の違いについて

配信と受信はややこしいですがこのように理解してください。

• 配信: 各プロセスがABPを介してメッセージの送受信を行うこと（主語は各プロセス, 英語broadcastに対応）
• 受信: 各プロセスがABPからメッセージを受信すること（主語は各プロセス, 英語deliverに対応）

1. Validity: 正常なプロセスがメッセージを配信した場合、そのプロセスは最終的にそのメッセージを受信する。
2. No duplication: 同じメッセージが2度以上受信されることはない。
3. No creation: あるメッセージがプロセスpと紐づけられて受信された時、そのメッセージはプロセスpによって配信されたものである。
4. Agreement: もしあるメッセージが正常なプロセスpによって受信された場合、すべての正常なプロセスはそのメッセージを受信する。
5. Total order: メッセージ$m_1$と$m_2$が正常なプロセスpとqの両方によって受信された場合、pが$m_1$を$m_2$より先に受信したならば、qも同様に$m_1$を$m_2$より先に受信する。

なぜ5つも条件があるのか

なぜこんな面倒な条件5つに分かれているのか？もっと簡潔な文章で表せないのか？と思ったかもしれません。
実際、Atomic Broadcastの定義はもう少し簡潔に表現することも可能です。

しかし、今回このように条件を分けているのは、一般に分散システムを考える際、Correctness（正しさ）を保証するために、そのCorrectnessをLiveness（生存性）とSafety（安全性）に分けて考えるためです。つまり、あるシステムが満たして欲しい性質をLivenessとSafetyに分けて考えることで、システムの正しさをより細かく検討できるようになります。
今回の場合、Validity, AgreementはLivenessの条件であり、No duplication, No creation, Total orderはSafetyの条件です。

同意問題とAtomic Broadcastの同値性

ここまでで同意問題とAtomic Broadcastの定義を紹介しました。ようやく本題である同値性の証明に入りましょう。

同意問題とAtomic Broadcastが同値であることを示すために、以下の二つを証明します。

1. Atomic Broadcastを実装できるならば、同意問題を解決できる。
2. 同意問題を解決できるならば、Atomic Broadcastを実装できる。

もし、自分で証明を考えたい方はここで一旦スクロールを止めてください。

1. Atomic Broadcastを実装できるならば、同意問題を解決できる

これは比較的簡単です。Atomic Broadcastを実装できるならば、各プロセスは以下のように同意問題を解決できます。

1. 各プロセスは自分の提案する値をAtomic Broadcastプロセスに配信する。
2. 各プロセスはAtomic Broadcastプロセスから最初に受信したメッセージの値を決定する。

この方法が同意問題の三つの条件を満たすことを確認しましょう。

• 終了性: 各プロセスは自分の提案値を必ず1回Atomic Broadcastで配信するとする。Atomic BroadcastのValidityにより、正常なプロセスが配信したメッセージはそのプロセスに最終的に受信（deliver）される。さらにAgreementとTotal orderにより、正常なプロセスは同じメッセージ列を同じ順序で受信する。したがって、すべての正常なプロセスは最初に受信したメッセージを用いて最終的に決定を行うことができる。
• 一貫性: Atomic BroadcastのAgreementとTotal order条件により、すべての正常なプロセスは同じメッセージを同じ順序で受信する。したがって、すべての正常なプロセスが最初に受信したメッセージの値は同じになる。（もちろんその後に受信するメッセージも同じ順序で同じものを受信しますが、最初に受信したメッセージだけを決定に使うので問題ありません）
• 妥当性: Atomic BroadcastのNo creation条件により、受信されたメッセージは必ずあるプロセスによって配信されたものであるため、決定された値は、少なくとも一つの正常なプロセスによって提案された値であることが保証される。

2. 同意問題を解決できるならば、Atomic Broadcastを実装できる

こちらはどうでしょうか？

以下のようなアルゴリズムを考えます。
Atomic Broadcastプロセス (ABP) は以下の状態を持つ

• pending: 受け取ったがまだ順序確定されていないメッセージの集合
• delivered: すでに受信させたメッセージの集合
• i: Consensus instance (同意ラウンド) の番号（初期値0）

またABP間のメッセージのやり取りにはReliable Broadcast（少なくとも正常ABPが送ったメッセージは最終的に他の正常なプロセスに届く）を用いるものとします。

アルゴリズム1. メッセージ配信要求とpendingへの追加

1. 各Atomic Broadcastプロセス (ABP) は対応するプロセスからメッセージ$m$の配信要求を受け取ると、$m$に全体で一意のidをつけ保存する。
2. 各ABPは$m$を他のABPに送信する。他のABPは重複してなければ$m$をpendingに追加する。

これにより正常ABPのpendingには、最終的にすべての正常プロセスが配信要求したメッセージが保存されます。

アルゴリズム2. 順序決定

1. ABPは各ラウンドで集合 pending \ delivered を consensus instance $i$に提案する。
2. Consensus instance $i$は提案された集合の中から一つを決定する。
3. 各ABPは決定された集合に含まれるメッセージを決められた順番（例えばidで昇順）で対応するプロセスに受信(deliver)させ、deliveredに追加する。
4. $i$を$i+1$に更新し、ステップ1に戻る。

この方法がAtomic Broadcastの5+1つの条件を満たすことを確認しましょう。

• Validity: 正常なプロセスが $m$ を broadcast したとする。Reliable Broadcast により、ある時刻 $T$ 以降、すべての正常ABPの pending に $m$ が含まれる。$m$ が deliver されるまでは delivered に入らないため、$T$ 以降に開始される任意の consensus instance では、各ABPの提案集合 pending \ delivered は必ず $m$ を含む。よって同意問題の Validity（決定値は提案値のいずれか）により、決定集合にも $m$ が含まれ、最終的にすべての正常プロセスが $m$ を deliver する。
  • なお、決定集合に含まれるメッセージは、各ABPがメッセージ本体を受け取ってから deliver するものとする（未受信の場合は受信を待つ）。
• No duplication, No creation: 自然に満たされます。
• Agreement: プロセスが正常ならば、メッセージの受信ができるため、あるプロセスがメッセージを受信した場合、そのメッセージは同意問題の決定値として選ばれたことになります。したがって、同意問題のAgreement条件により、すべての正常なプロセスはそのメッセージを決定し、受信します。
• Total order: アルゴリズムの途中で決定された値の送信順序は、consensus instanceの番号$i$とラウンド内での決め打ち順序によりすべてのプロセスで同じになります。したがって、もしあるメッセージ$m_1$が$m_2$より先に決定された場合、すべての正常なプロセスは$m_1$を$m_2$より先に受信します。

以上により、同意問題とAtomic Broadcastが同等な問題であることを確認できました。^[4]

おわりに

同意問題とAtomic Broadcastの同値性について説明しました。

厳密な証明はまたまとめたいと思ってますが、同意問題とAtomic Broadcastの関係性を理解する一助になれば幸いです。

また同意問題とAtomic Broadcastの同値性は同意問題が解決可能である場合にのみ成り立ちます。今回は同意問題が解決可能である場合を前提として説明しましたが、例えば一般の非同期システムにおいては同意問題は解決不可能であり、Atomic Broadcastも実装不可能です。理解できていない点も多いので、今後さらに勉強していきたいと思います。

脚注

1. 正常でないプロセスが停止する故障モデルは**クラッシュ故障モデル (Crash failure model)**と呼ばれます。他にも様々な故障モデルがありますが、ここではクラッシュ故障モデルを前提としています。

2. Introduction to Reliable and Secure Distributed Programming, Christian Cachin, Rachid Guerraoui, and Luís Rodrigues, 2011. pg. 283. から引用・翻訳

3. ここでは簡単のために、各プロセスがAtomic Broadcastプロセスを一つずつ持っていると仮定していますが、実際には各プロセスの中にAtomic Broadcastの機能が組み込まれていることが多いです。そのため、プロセスとABP間のメッセージが失われないという条件は自然に満たされます。

4. ここまで読んで、Processが生きている状態でABPがクラッシュした場合はどうなるのか？など疑問に思った方もいるかもしれません。実際には^[3:1]で述べたように、ABPはプロセスに組み込まれていることが多く、ABPがクラッシュする場合はプロセスもクラッシュすると暗黙に仮定しています。