\(\def\vector#1{\boldsymbol{#1}}\)

分散システム

Takami Torao
  • このエントリーをはてなブックマークに追加

同期/非同期

標準的な分散コンピューティング環境ではメッセージを遅延させる攻撃者の存在によって通信の不確実性がもたらされる。メッセージを遅延させる攻撃者による攻撃を制限するための 3 つの通信モデルを定義する。

同期モデル

同期モデル (synchronous model) ではメッセージの配信に対して既知の有限時間範囲 \(\delta\) が定義されており、攻撃者はメッセージの配信に対して最大でも \(\delta\) の遅れまでしか発生させることができない。つまり送信者がメッセージを送信するとある時間 \(\delta\) 以内に相手に受信されることが保証されている。この \(\delta\) はすべての参加者が知っている。

非同期モデル

非同期モデル (asynchronous model) ではメッセージの配信に対して最終的に配信されることのみが規定されており、攻撃者はメッセージの配信を任意の有限時間だけ遅らせることができる。

部分同期モデル

部分同期モデル (partial synchronous model) は同期モデルと非同期モデルの中間に位置する。既知の有限時間範囲 \(\delta\) に加えて GST (global stabilization time) と呼ばれるイベントが存在する。

部分同期モデルでは、時刻 \(t\) に送信されたメッセージは時刻 \(\max(x,{\rm GST}) + \delta\) までに配信されなければならない。つまり、システムは GST までは非同期モデルで動作し、GST 以降は同期モデルで動作する。攻撃のためには未知の有限時間後に GST イベントを発生させる必要がある。

合意問題

ビザンチン合意問題

ビザンチン合意問題は、初期値に関して他のプロセスと合意するために、初期値を持つソースプロセスと呼ばれる指定プロセスを必要とする。

  • Termination: 全ての非故障プロセスは最終的に値を決定しなければならない。
  • Agreement: 全ての非故障プロセスは同一の値に合意しなければならない。
  • Validity: ソースプロセスが非故障である場合、全ての非故障プロセスによって合意された値はソースプロセスの初期値と同じ値でなければならない。

合意の目的に対して termination と agreement の必要性は述べるまでもないだろう。validity は、例えばどのような初期値に対しても "false" を合意するような可能性を排除し、合意した値がソース値と相関している事を確認する。ソースプロセスに障害がある場合、非故障プロセスがどのような値にも合意することができる。故障プロセスが何に合意するか、またはプロセスが終了して何に合意するかは考慮しない。

ビザンチン合意問題はコンセンサス問題と対話的一貫性問題という 2 つの特徴がある。

コンセンサス問題

ビザンチン合意問題と異なり、コンセンサス問題は各プロセスには初期値があり、全ての非故障プロセスが単一の値に合意しなければならない。

  • Termination: 全ての非故障プロセスは最終的に値を決定しなければならない。
  • Agreement: 全ての非故障プロセスは同一の単一値に合意しなければならない。
  • Validity: 全ての非故障プロセスが同じ初期値を有する場合、全ての非故障プロセスによって合意された値は同じ値でなければならない。

相互一貫性問題

ビザンチン合意問題とは異なり、相互一貫性問題は各プロセスには初期値があり、全ての非故障プロセスが、プロセスごとに一つの値を持つ一連の値に合意しなければならない。

  • Termination: 全ての非故障プロセスは最終的に配列値 \(A\) を決定しなければならない。
  • Agreement: 全ての非故障プロセスは同一の配列値 \(A[v_1,\cdots,v_n]\) に合意しなければならない。
  • Validity: プロセス \(i\) が非故障であり、その初期値が \(v_i\) の場合、全ての非故障プロセスは配列の \(i\) 番目の要素として \(v_i\) に合意する。もしプロセス \(j\) が故障の場合、非故障プロセスは \(A[j]\) に対してどのような値でも合意することができる。

FTP 不可能性

一つでもプロセス故障が発生しうる (許容する) 非同期 (メッセージパッシング) システムは、有限時間内に合意に達する保証ができない。

FLP 不可能性 (FLP impossibility) は障害耐性と安全性を持つ分散システムは合意が不可能であることを示す基本的な定理。この結果の正当性の証明は大域的状態の価数の重要な概念に導かれている。

\(v(S_g)\) を任意の大域的状態 \(S_g\) から到達可能なある大域的状態で合意可能な値の集合を表すとする。\(|v(S_g)|\) を大域的状態 \(S_g\) の valency (価数; 取り得る値の個数) と定義する。大域的状態は 0 または 1 のブール代数の決定値に対して 2 の価数を持てば bivalent (二価) であるし、また 1 の価数を持てば monovalent (一価) である。言い換えれば bivalent なら合意に達することができず monovalent であれば合意に達することができる。

monovalent 状態の \(S_g\) は \(v(S_g) = \{1\}\) であれば 1-valent、\(v(S_g) = \{0\}\) なら 0-valent である。二価性をとる大域的状態からは 0-valent または 1-valent の状態のどちらにも到達可能であるため、決定における不確実性を導く。

コンセンサス値は入力のよって決定することから初期状態では一価である。しかし、故障が発生したケースではコンセンサスプロトコルは必然的に二価の初期状態を持つことを示すことができる (各プロセスが \(\{0,1\}\) から任意の初期値を持つことができると仮定し trivial な解を除外する)。これは背理法から導くことができる。

入力が全て 0 である初期状態は 0-valent であり、入力が全て 1 である初期状態は 1-valent であることは明かである。入力割り当てを all-0 から all-1 に移行すると、それぞれ 0-valent と 1-valent の入力割り当て \(\vector{I}_0\) と \(\vector{I}_1\) が存在し、一つのプロセス \(p_f\) の入力のみが異なる入力値をとるとする。もし 1 つのプロセスの故障に耐えられるコンセンサスプロトコルが存在する場合、以下のようになる。

  1. \(\vector{I}_0\) から始まりすぐに \(p_f\) が発生した場合、他のプロセスは termination 条件のために 0 に合意しなければならない。
  2. \(\vector{I}_1\) から始まりすぐに \(p_f\) が発生した場合、他のプロセスは termination 条件のために 1 に合意しなければならない。

実行 2. は実行 1. と同じに見えるが、しかし実行 2. はコンセンサス値 0 (矛盾) で終了する必要がある。従って、少なくとも 1 つの二価の初期状態が存在しなければならない。

コンセンサスに達するためには初期値を交換する必要があることに注意。(モデルによるがメッセージパッシングか共有メモリによって)。従って、実行中のプロセスでコンセンサスを一方的に決定することはできない。不可能性結果の鍵となる考えは、潜在的なプロセス故障に遭遇した場合、プロセスが故障したこととプロセスまたは通信経路が非常に遅いことを区別できないことである。従って 2 価状態から 1 価状態に遷移することはできない。具体的には次のようになる。プロトコルが 2 価の大域的状態から 1 価の大域的状態に遷移し、証明における推論のために大域的時間インターリーブモデルを使用するためには、コンセンサス値を決定することで価数を変更する重要なステップ実行が存在しなければならない。これは 2 つの可能性がある:

  • 重要なステップは単一のプロセスで発生するイベントである。しかし、他のプロセスは、このプロセスがクラッシュした 2 つのシナリオと、このプロセスが非常に遅いシナリオを区別できない。どちらのシナリオでも、他のプロセスは永遠に待機し続けることができるため、プロセスはコンセンサス値に到達することができず、2価状態のままになる可能性がある。
  • 重要なステップは、異なるプロセスにおける服す野独立した (すなはち送受信関連ではない) イベントで発生する。しかし、様々なプロセスでの独立したイベントはどのような順序でも起こりうるため、重要なステップは明確に定義されておらず、この可能性は受け入れられない。

故障が発生する可能性のあるいかなる非同期システムにおいても合意の問題が全ては解決できないことを意味するため、この不可能性の問題は重要である。次のような合意を必要とする全ての問題は1つの故障であっても解決できない可能性があることを示すことができる。

  • リーダー選挙
  • broadcast-convergecast フローを用いたネットワーク側のグローバル機能問題
  • 信頼できるブロードキャストの終了
  • アトミックブロードキャスト

一般的な戦略は、コンセンサス問題から検討中の問題 X へのリダクションマッピングを使用することである。アルゴリズムを使って X を解くことでコンセンサスが得られることを示す必要がある。しかし、コンセンサスは解決できないため問題 X に違いない。

P2P

管理されていないネットワークで Byzantine 障害を想定する P2P システム

  • Scalability
  • Decentralization
  • Security -