Distributed Algorithms for Message-Passing Systems: 第六章

damps-06.md

第二部 分散システムでの論理時間とグローバル状態

第二部は四章からなり、以下の内容を扱っている:

• 分散計算の、イベント/ローカル状態/グローバル状態、の概念
• それらに関連した論理時間について
• => __信頼可能な__分散システム上での非同期分散計算の性質を考察する上で基礎となる概念

六章:

• プロセスのイベント群の部分順序によって、分散計算を表現する方法
• 整合グローバル状態の概念の導入と、それを計算するためのアルゴリズム(x2)
• グローバル状態の格子の概念について

七章:

• 分散システムで遭遇するいくつかの異なる論理時間の導入:
  • スカラ時間(a.k.a ランポート時間)
  • ベクトル時間
  • マトリックス時間

八章:

• 非同期メッセージパッシング分散システム上でのチェックポイントの計算方法:
  • 通信とチェックポイントパターンの概念の導入
  • チェックポイント計算アルゴリズムが保障する二つの整合性条件の提示:
    • z-cycle-freedomとrollback-dependency trackability

九章:

• 非同期分散システム上で同期システムをシミュレートするための汎用的なテクニックについて

第六章 分散計算の性質とグローバル状態の概念

概要

分散実行をどうモデル化するか？

• 逐次計算なら「連続するローカル状態のシーケンス」として表現可能
  • 各状態は、初期状態から始まり、ステートメント列によって実行(遷移)していく
• この章では、分散実行をモデル化するための三つの方法を提示する:
  • イベント群の部分順序として
  • ローカル状態群の部分順序として
  • グローバル状態の格子として
• 表現力的にはいずれも等価
  • 焦点が異なるので、分散実行の分析の際には、その目的により適したものを選択すれば良い

分散計算の基礎的な概念である__グローバル状態__についても触れる:

• 分散状態の分析
• オンザフライで分散アプリケーションのグローバル状態を計算するためのいくつかのアルゴリズムの提示:
  • __観察__アルゴリズムに分類される (アプリケーション自体には影響を与えない)
  • アルゴリズムは「分散実行が通った__かもしれない__グローバル状態」を求める (and それがベスト):
    • (分散システム内のプロセスが)結果のグローバル状態が、実在したものであるかどうかを識別するのは不可能
    • 分散計算の観察の相対的な性質を反映している (この性質は分散計算問題を解くことを阻害するものではない)
• なお"グローバル状態"と"スナップショット"は文献では同じ意味で使用される (本章では前者の使う)

6.1 分散実行はローカルイベント群の部分順序

6.1.1 基礎定義

この章が想定する非同期システム:

• n個のプロセスから構成
  • p[1]...p[i]のプロセスが存在し、各プロセスの識別子はi
• 各プロセスの表現力は「チューリングマシン + P2Pのsend/recv操作」

イベント

イベント:

• プロセスよるステートメントの実行のこと
• 一つのプロセス内の処理は逐次実行される
  • => プロセスはイベントのシーケンスで構成される
• 分散システムでは、三種類のイベントが存在する:
  • 他のプロセスとの通信用の二つのイベント:
    • sendイベント
    • receiveイベント
  • それ以外は__内部イベント__:
  • 内部イベントの粒度は様々 (e.g., サブプログラムの実行から一つのCPU命令ステップまで)
  • ただし、通信を挟まないイベントは外部(他のプロセス)から観測する手段がない
    • そのため通信イベントを間に挟まない内部イベント群は、一つの抽象的な内部イベントしてまとめられる

プロセス履歴

各プロセスは逐次実行:

• (つまり)一つのプロセス内で実行されるイベント群は全順序
• イベント群の実行シーケンスはp[i]の__履歴__と呼ばれる
  • e[i][x]: p[i]によって実行されるx番目のイベント
  • ^h[i]: p[i]の履歴
  • => ^h[i] = e[i][1], e[i][2], ..., e[i][x], e[i][x+1], ...
• プロセスの履歴は(h[i], ->[i])と表記されることもある:
  • h[i]: p[i]が生成するイベントの集合
  • ->[i]: イベント群の(ローカルな)全順序

6.1.2 分散実行はローカルイベント群の部分順序

• 表記: H[i]はU{1 =< i =< n} h[i]となる
  • ある分散実行で生成される全てのイベント群の集合
• 仮定: プロセスは同一のメッセージを二度送信しないものとする

メッセージ関係

• M: ある実行中に交換されるメッセージの集合
• ->msg: __メッセージ順序__関係
  • s(m) ->msg r(m), ∀m ∈ M
    • s(m): メッセージmの送信イベント
    • r(m): メッセージrの受信イベント
  • => ->msgは、全てのメッセージは受信前に必ず送信されている、という事実を表現している

分散計算

分散実行(計算)の制御フローは、以下の最小部分順序関係、で捕捉される:

• ^H[i] = (H[i], ->ev):
  • e[i][x] ->ev e[j][y]は、次の条件群のいずれかが満たされた場合に真となる:
    • プロセス順序: i = j and x < y
    • メッセージ順序: ∃ m ∈ M: e[i][x] = s(m) and e[j][y] = r(m)
    • 推移閉包: ∃ e: e[i][x] ->ev e and e ->ev e[j][y]
  • ->evは通常__happened before関係__と呼称される:
    • __因果先行(causal precedence)関係__と呼ばれることもある
    • e[i][x]とe[i][y]に必ずしも、原因・結果、の関係がある訳ではないので、実は若干不正確
    • 「e[i][x]は、e[i][y]に因果的な影響を与え得る」と解釈して"happen before"の同義語として扱う

分散計算をイベント群の部分順序としてモデル化するアプローチは、ランポート(1978)によるもの:

• 分析の際の基盤となる手法:
  • 物理時間から解放される
  • 非同期分散計算の本質を捉えている
  • => 分散計算を抽象化する簡単な方法であり、その上に立って分析や推測が可能
• 図6.1: 分散実行の例
  • 空間・時間ダイアグラムで図示可能

6.1.3 因果過去、因果未来、平行、カット

因果パス

• ->evで連続するイベントシーケンス:
  • イベント列a(1),a(2),...,a(z)があるとして、
  • ∀x: 1 <= x < z: a(x) ->ev a(x + 1)
• 図6.1で言えばe[2][2],e[2][3],e[3][2],e[3][1],e[1][3]が因果パスの例
  • p2 (e[2][3])はp1(e[1][3])に対して直接メッセージを送信することはないが、因果関係にあることが分かる

並行イベント、因果過去、因果未来、平行集合

並行(concurrent):

• 二つのイベントaとbは、因果関係にない場合、__並行関係__にある:
  • __独立(independent)__とも言う。表記はa||b。
  • 具体的な定義はa||b =def not (a ->ev b) and not (b ->ev b)

その他、自然に導出される関係群 (eはあるイベントとする):

• 因果過去(causal past):
  • past(e) = {f | f ->ev e}
• 因果未来(causal future):
  • future(e) = {f | e ->ev f}
• 並行集合(concurrency set):
  • concur(e) = {f | f ∉ (past(e) or future(e))}
  • => eと(過去 or 未来において)因果関係にない全てのイベント群
• 図6.2: e[2][3]に対して上記関係に該当するイベント群の図示

これらの関係が物理時間とは無関係、というのは重要:

• 図6.2では、e[3][1]とe[1][2]はe[2][3]の(物理時間的に)前に実行されている
  • ただし、論理的には上記三つのイベントは並列関係にある
  • (例えば)p[1]は、e[2][3]の発生を、p[3]から(e[1][3])で)メッセージを受信するまで知ることはできない
    • e[2][3], ..., e[1][3]という制御フロー(因果パス)を経る必要がある

カット、整合カット

• カット:
  • Cと表記
  • プロセス履歴のプレフィックス群:
    • [prefix(^h[1]), ..., prefix(^h[n])]
    • prefix(^h[i]): p[i]の履歴のプレフィックス
• 整合カット:
  • 次の条件を満たすカット: ∀ e ∈ C: f ->ev f ∈ C
  • => 因果過去にあるイベント群が全て含まれている
• 図6.3は、カットCと整合カットC'の例
  • "カット"の用語の由来は、空間・時間ダイアグラムを分割する線、として表現可能なため
  • 分割線の左側のイベント群がカットに属する

6.1.4 物理時間を考慮した非同期分散実行

• 分散実行の定義では物理時間に言及していない
• 実時間の分散プログラムを考えない限りは有用
• 物理時間は(計算に)分散プログラムの実行が必要なリソース
  • 個別のプロセスからはアクセスできない
  • 計算の外にいる超越的な観察者のみが取得可能
• つまり、同じイベント集合と部分順序を持つ分散実行同士は、同じ実行と見做せることを意味する
  • どの物理時間にイベント群が生成されたかどうかに関わらず
• 図6.4: 同じ実行の二つのインスタンス
  • 一番下の目盛りが実時間軸
  • 時間・空間ダイアグラムから、イベント間の実時間インターバルやメッセージ転送遅延を抽象化すれば得られる
• 分散実行によって生成されるイベント群の部分順序は、イベント間の因果依存関係のみを補足することを示している
  • プロセスによって知られる"duration"という概念はない
  • => プロセスが環境についての情報を知る唯一の方法は、メッセージ受信しかない、ということを示している
  • => 非同期システムでは、時間の経過は何もプロセスに情報を与えない
  • ! 純粋な非同期システムには(現実のシステムではよくある)"タイムアウト" 的な概念もない (e.g., 「五分経ったからこのノードは死んでいるだろう」とかができない)
• 同期システムでは異なる
  • ラウンドが移れば、全てのプロセスはそれを把握可能
  • ! 全ノードにリクエストをブロードキャスト(round1)して、リクエストを一定時間だけ待つ(round2)、そして計算(round3)、というのも同期システムの一種 (非同期システムとの中間かな？ 厳密な時間内の到達保証はないので)
  • この辺りは９章でも触れるよ

6.2 分散実行はローカル状態群の部分順序

イベントからローカル状態へ

図6.5:

• プロセスp[i]のローカル状態σ[i][x]への遷移:
  • イベントの発生によって、状態が遷移する
  • σ[i][x-1] == e[0][x] ==> σ[i][x]
  • σ[i][x] = δ(σ[i][x-1], e[i][x])と表記することもある

->ev関係の軽微な修正

->ev(因果先行)関係の定義を少し拡張した->ev'を導入:

• ローカル状態同士の関係を簡潔に定義可能にするため
• 再帰性(reflexivity)が加わる:
  • i = j and x < yだったのがi = j and x =< yになる
  • => 同じプロセス内の同じイベント同士でも、因果先行関係が成立する

ローカル状態群の部分順序

• Sをある分散実行で生成された全てのローカル状態の集合とする
• S内の要素群の部分順序->σの定義はσ[i][x] ->σ σ[j][y] =def e[i][x+1] ->ev' e[j][y]:
  • 図6.6は定義の図示:
    • 上の図がプロセスを跨いだ場合で、下の図がプロセスが同じ場合
    • 再帰性の導入により、同じプロセス内での状態遷移(依存関係)も、擬似的なメッセージのsend/recvによるもの、として扱える
• 分散実行^Sの定義は^S = (S, ->σ)

平行ローカル状態

• σ1 || σ2 =def not (σ1 ->σ σ2) and not (σ2 ->σ σ1)が成立するなら、二つの状態は平行(or 独立)関係にある
• 重要な点は:
  • 並行関係にある二つの状態は、同じ物理時間に共存している可能性がある (図6.6のσ[i][x+1]とσ[j][y-1])
  • しかし、因果依存(->σ)関係にある状態同士では、それが成り立つことがない:
    • 原因となった状態は、その結果の状態が開始する前には、必ず終了している

6.3 グローバル状態とグローバル状態の格子

6.3.1 グローバル状態の概念

グローバル状態と整合グローバル状態

グローバル状態(global state):

• Σ: [[σ[1],...,σ[i],...,σ[n]]
• 各プロセスp[i]のローカル状態σ[i]の配列で表す

整合グローバル状態(consistent global state):

• ∀i,j: i != j=> σ[i]||σ[j]が成り立つグローバル状態
• => 因果依存関係にあるローカル状態同士を含んでいない

グローバル状態の到達性

• 以下が成り立つなら Σ2 = [σ'[1],...,σ'[i],...,σ'[n]]は、Σ1 = [σ[1],...,σ[i],...,σ[n]]から 直接到達可能(directly reachable) である:
  • ∀i != j: σ'[j] = σ[j] かつ σ'[i] = δ(σ[i], e[i])
    • => 一回のローカル状態遷移で、遷移可能なグローバル状態
  • ↑が成り立つプロセスおよびイベントが存在するなら、直接到達可能といえる
  • この遷移はΣ2 = δ(Σ1, e[i])と表記する
• Σ[z]がΣ[1]からの複数回の遷移で得られる場合は 到達可能(reachable) であるといえる:
  • Σ[1] ->Σ Σ[z]と表記
  • Σ[1] ->Σ Σ[1]は常に成立する

6.3.2 グローバル状態の格子

以降では、図6.7に示されている、二つのプロセスによる簡単な分散実行について考えてみる:

• 最初にp[1]がp[2]からのメッセージを待機し、受け取ったら処理を行い、p[2]にメッセージを送る

到達性グラフ

(興味深いことに)ある分散実行が通る可能性がある全ての整合グローバル状態を表現することは可能:

• 図6.8:
  • グラフとして表現可能
    • __到達性グラフ(reachability graph)__と呼ぶ
  • 頂点は、(分散実行が通る可能性がある)整合グローバル状態
    • 簡単のために[[σ[1][x], σ[2][y]]は、単に[x,y]と表記する
  • 辺は、遷移に使用したイベント

グローバル状態の格子としての分散実行

図6.7の分散実行は二つのプロセスによるものなので、二次元グラフを生成している:

• 左向きの辺はp[1]による遷移を、右向きの辺はp[2]による遷移を、表している
• 一般的にはnプロセス存在する場合は、n次元のグラフが生成される

到達性グラフは格子構造(lattice structure)を形成する:

• 格子は以下の性質を有する有向グラフ:
  • 任意の二つの頂点には、一意な「最大共通先行者(greatest common predecessor)」および「最小共通後続者(lowest common successor)」が存在する
  • 例: 頂点[1,2]と[0,2]の場合
    • [0,1]が最大共通先行者、[2,2]が最小共通後続者
• この性質は、ある分散実行が特定のグローバル状態性質を満たすかどうかを判定する際に、重要となる
  • 詳細は後述

6.3.3 逐次観察

分散実行の逐次観察

分散実行の__逐次観察(sequential observation)__とは:

• 全てのイベントの部分順序を考慮した(状態遷移の)シーケンス
  • 到達性グラフでいえば、始点から終点に繋がるパスがそれに該当する
  • O = [e[i][x], ..., e[j][y]]といったように、イベントのシーケンスで表現する
• 図6.9: 三つのシーケンス(逐次観察)の例
• 各観察は全順序
• 各観察間の移動は、並行するイベントの交換で行える (例: 6.9の左上の図)
• 全ての観察で共通する部分は、(その計算における)イベント群の部分順序に対応する

注記１

逐次観察のシーケンスはイベント(辺)ではなく、グローバル状態(頂点)のシーケンスでも表現可能

注記２

グローバル状態の到達性を考える際は「一度に一つのイベントが発生するもの」として扱っている:

• 実際には複数同時に発生することもあるのでは？
  • 例えばe[1][1]とe[2][2]なら、異なるプロセスのローカル遷移なので、その可能性はあり得る
• ただし実際には、それが発生したとしても検知する方法がない:
  • あるプロセスが他のプロセスの状態を(メッセージ送受信以外で)知る手段がないため
  • 超越的な外部観察者を除いて
• それなら複数同時発生はないものとして、格子として扱った方がシンプルで良い:
  • これならある分散実行が通ったかもしれないグローバル状態の損失を確実に防ぐことができる

6.4 プロセス状態とチャンネル状態を含んだグローバル状態

6.4.1 チャンネル状態を含んだグローバル状態

• プロセス群の(ローカル)状態だけでなく、チャンネル群の状態も含んだグローバル状態を扱いたいことがある
• 以降の議論では「単方向チャンネル」を仮定する:
  • 逆向きのチャンネルが二本あるものとすれば双方向も扱えるので、一般性は損なわない
  • チャンネルの状態は「転送中のメッセージ群(i.e., p[i]が送信したけどp[j]は受信していないメッセージ群)」によって示される
• グローバル状態はΣとCΣによって構成される:
  • Σ: 各プロセスのローカル状態の配列 (これまでの節と同じ)
  • CΣ: 全てのチャンネルの状態を要素とする集合

6.4.2 チャンネル状態を含んだ整合グローバル状態

表記

図6.10:

• σ[i]: プロセスp[i]のローカル状態
• e ∈ σ[i]: eがσ[i]以前(過去)にp[i]によって生成されたイベントであることを示す
• f ∉ σ[i]: fがσ[i]以降(未来)にp[i]によって生成されたイベントであることを示す

転送中メッセージと孤児メッセージ

転送中(in-transit)と孤児(orphan)の定義:

• ローカル状態の順序付きペアで定義可能
• 前提: p[i]からp[j]にメッセージmが送信されることとする
  • σ[i]とσ[j]は、それぞれのローカル状態
  • s(m)はメッセージ送信元で、r(m)はメッセージの受信先
• 転送中メッセージ:
  • ペア<σ[i], σ[j]>がs(m) ∈ σ[i] and r(m) ∉ σ[j]を満たす場合は転送中メッセージ
  • => p[i]は送信したけど、p[j]は(まだ)受信していない
• 孤児メッセージ:
  • ペア<σ[i], σ[j]>がs(m) ∉ σ[i] and r(m) ∈ σ[j]を満たす場合は孤児(親がいない)メッセージ
  • => p[i]が送信していないのに、p[j]が受信している

図6.11:

• <σ[1], σ[2]>の場合m[5]が転送中メッセージ
  • 両者は並列関係(σ[1] || σ[2])にあるの、共存してもで特に不整合には繋がらない
• <σ[3], σ[2]>の場合m[4]が孤児メッセージ
  • 両者は因果依存関係(σ[3] ->σ σ[2])にある
  • => 整合グローバル状態に、上記二つのローカル状態(= 孤児メッセージ)を含めることはできない (cf. 6.3.1の定義)
• m[1], m[2], m[3]は過去のメッセージ

整合グローバル状態

チャンネル状態の定義:

• チャンネルがFIFOならメッセージ列、非FIFOならメッセージ集合、として表現する
• p[i]からp[j]への有向チャンネル(<σ[i], σ[j]>)の状態はc_state(i,j)と表記する
  • 中身はp[i]からp[j]へ転送中のメッセージ列(or 集合)

グローバル状態(Σ,CΣ)は、任意のメッセージmに対して、以下の二つが成り立つなら整合性があるといえる:

• C1: (s(m) ∈ σ[i]) => (r(m) ∈ σ[j] xor m ∈ c_state(i,j)
  • => 送信されたメッセージは「受信済み」or「転送中」のどちらか
• C2: (s(m) ∉ σ[i]) => (r(m) ∉ σ[j] and m ∉ c_state(i,j))
  • => 未送信のメッセージは存在しない

Σ 対 (Σ,CΣ)

• Σは(Σ,CΣ)を暗黙に含んでいる
  • c_state(i,j)を考えると、
    • σ[i]はp[i]が過去に送信したメッセージ群を暗黙に含んでいる
    • σ[j]はp[j]が過去に受信した(p[i]によって送信された)メッセージ群を暗黙に含んでいる
    • => c_state(i,j)は、σ[i]およびσ[j]から算出可能
• そのため以降では両者を区別なく扱う

6.4.3 整合グローバル状態 対 整合カット

• カットは6.1.3で導入された
• カットCは、プロセス履歴のプレフィックス群 (e.g., [prefix(^h[1]),..,prefix(^h[n])])
• p[i]のカット時点でのローカル状態σ[i]は履歴のプレフィックス(イベント群)を適用することで取得可能
  • σ[i] = δ(σ[i][0], prefix(^h[i]))
  • σ[i][0]はp[i]の初期状態
  • => カット時点でのグローバル状態Σ = [σ[1],...,σ[n]]が算出可能
• ∑が整合な場合にのみ、カットCも整合となる
  • 図6.12:
    • C'は整合カット: m'と分割線がクロスしてるが、これは転送中メッセージなので問題ない
    • Cは整合ではないカット: 分割線がmと逆方向にクロスしているが、これは孤児メッセージ

6.5 グローバル状態のオンザフライ計算

6.5.1 グローバル状態計算は観察問題の一種

目的は、整合グローバル状態を計算するアルゴリズムをデザインすること:

• 対象分散アプリケーションはn個のプロセスで構成される (i.e., p[1], ..., p[n])
• それぞれに対応する制御(or 観察)プロセスcp[i]が存在する:
  • 対応するプロセスp[i]を観察して、アプリケーションの整合グローバル状態を求める
  • p[i]の挙動には影響を与えない
    • => 観察問題(observation problem)の一種
    • (例えば)前章のモバイルオブジェクトとは異なる
      • そこではアプリケーションが明示的にaccquire()等を呼んでいた
• 図6.13: 構造図

6.5.2 問題定義

グローバル状態の計算はx個の制御プロセスによって独立して開始される (1 =< x =< n)。

この問題は以下の性質によって定義される:

• 生存性(liveness):
  • 最低でも一つの制御プロセスが計算を開始したら、何らかのグローバル状態が求められる
• 安全性(safety):
  • (∑,C∑)を計算されたグローバル状態として、
    • 妥当性(validity):
      • ∑startと∑endを、それぞれ計算開始時と終了時のグローバル状態とする
      • ∑は(∑start ->∑ ∑) and (∑->∑ ∑end)である必要がある
      • => ∑の鮮度(freshness)を規定する
        • 「常にアプリケーションの初期状態を返す」とかはダメ
        • 到達可能性があり、かつ、新しいグローバル状態である必要がある
          • 到達可能性である、ということは、整合性がある、ということも示唆している
    • チャンネル整合性:
      • C∑は、∑を関係した、転送中の全てのメッセージを含んでいる
      • => C∑と∑の間で合意が取れていることを規定

6.5.3 計算されたグローバル状態の意味

結果の非決定性について

図6.8のグローバル状態の格子を考えてみる:

• ∑start[0,1], ∑end=[1,2]とする
• 妥当性条件は、求められた∑の値として[0,1], [1,1], [0,2], [1,2]のいずれも許容する
  • 実際に計算されるグローバル状態は、アプリケーションプロセスおよび制御プロセスが生成するイベント群の実行順序に依存する
  • 妥当性条件は、∑は実際に通過した__かもしれない__整合グローバル状態である、としか述べていない
    • 分散実行が、実際に∑を通過したかどうかを知る手段はない
    • 独立したイベント群は、異なる逐次観察者によって、異なる順序で実行されたものとして認識され得るため (see: 図6.9)
• 従って、妥当性条件は、達成可能な内の最高の特性を示している:
  • a) ∑は整合性を保っている
  • b) そのグローバル状態は、分散実行によって通過されることが可能である (これ以上強い主張は無理)

安定性質の場合

安定性質(stable property):

• 一度trueとなったら、永遠にtrueであり続けるような性質
• 分散アプリケーションのグローバル状態上で良く定義される安定性質の例:
  • "アプリケーションは終了した"
  • "デッドロックがある"
  • "分散セルはアクセス不能になった" (?)
  • => 前者二つに関しては後の章で扱う
• より厳密には、
  • pを、ある分散実行のグローバル状態上の性質とする
  • p(∑) => (∀∑': ∑ ->∑ ∑' : p(∑'))ならpは安定性質 (! 冒頭の説明通り)

この性質がどう利用可能か:

• pが安定性質で、∑ ->∑ ∑endなら、p(∑) => p(∑end)が成り立つ:
  • p(∑)がtrueなら、実際に∑を通過したかどうかに関わらず、p(∑end)が成り立つと主張可能
  • 同様のことがp(∑)の全ての未来のグローバル状態に対していえる
• not p(∑)の場合:
  • not p(∑start)であるといえる
  • p(∑end)であるかどうかに関しては何も情報はない
• ! 「特定のグローバル状態を実際に通過したかどうか」に関係なく、未来(or 過去)の状態が特定の性質を満たしていることが保証可能

6.5.4 グローバル状態の計算アルゴリズムの原理

グローバル状態の計算のアルゴリズムは、以下を確実に行う必要がある:

• 各制御プロセスcp[i]は、プロセスp[i]のローカル状態σ[i]を記録する
• 各(cp[i], cp[j])のペアは、c_state(i,j)(p[i]からp[j]への有向チャンネルの状態)の値を計算する

(∑,C∑)を整合にする(= 6.4.3のC1とC2を満たす)ために、制御プロセス群は以下のように協調する必要がある:

• 同期:
  • <σ[j],σ[i]>に、孤児メッセージを存在しないようにしたい
  • そのため、p[j]からメッセージを受信したら、cp[i]はp[i]にメッセージを配送する前に、そのローカル状態を記録するかもしれない
  • ! 配送後の状態の記録、では孤児になる可能性がある (p[j]のどの地点の状態が∑に含まれているか次第)
• メッセージ記録:
  • 転送中メッセージの存在が、対応するチャンネルの状態から分かるようにしたい
  • 制御プロセスは何らかの方法でそれを記録しなければならない

ほとんどのグローバル状態計算アルゴリズムは、同じ同期テクニックを使って∑が整合であることを保証している。

ただし、以下の点は、アルゴリズム毎に差異がある:

• a) 転送中メッセージを記録するために使うテクニック
• b) 通信チャンネルがFIFOか非FIFOか、といった仮定の違い

6.6 FIFOチャンネルに適したグローバル状態計算アルゴリズム

このアルゴリズムの仮定:

• a) チャンネルはFIFO
• b) 通信グラフは強く接続している (任意の二つのプロセスを繋ぐパスが存在する)

6.6.1 アルゴリズムの原則

プロセスのローカル変数と制御メッセージ

gs_state[i]:

• グローバル状態計算のステート管理用ローカル変数
• red(ローカル状態は記録済み) or green(まだ記録されていない)
• 初期値はgreen
• 一度redになったらそのまま

制御プロセスcp[i]は、いつでもp[i]のローカル状態を記録することが可能:

• 記録時にはアトミックに以下を実行する:
  • a) gs_state[i]をredに更新
  • b) 制御メッセージMARKER()を、出力チャンネル群から送信する
• 図6.14:
  • チャンネルはFIFOなので、MARKER()送信前後のアプリケーションのメッセージ群は明確に分割される

cp[i]のメッセージ受信時の挙動はgs_state[i]の値によって変わる:

• gs_state[i] = green:
  • 図6.15
  • cp[i]がMARKER()を受信した場合、グローバル状態の計算が始まったということなので、それに参加:
    • 1. p[i]の受信時の状態σ[i]を記録
    • 2. MARKER()を出力チャンネル群から送信 (して宛先プロセスに計算の開始を通知)
    • 3. <σ[j],σ[i]>を整合性の取れたものにするために、c_state(j,i)は空にする
      • p[j]からp[i]への転送中メッセージは存在しない
• gs_state[i] = red:
  • 図6.16
  • cp[i]は既にσ[i]を記録済み
  • c_state(j,i)を、<σ[j],σ[i]>に対して整合性の維持した値にする必要がある
  • => cp[i]は「ローカル状態の記録 ～ p[j]からMARKER()受信」までにp[j]から受信したメッセージ列を転送中として扱う

性質

生存性:

• 最低でも一つのcp[i]がグローバル状態の計算を始めたとする
• グラフは接続しているので、最終的には全てのプロセスがMARKER()を受信する
  • MARKER()が送信されるのは各チャンネルにつき一度だけ
• ローカル状態が記録されるのも一度だけ
• => いつかはグローバル状態の計算が完了する

安全性:

• プロセスとその送出メッセージをgs_state[i]の値で色付けしてみる:
  • もし、redメッセージがgreenプロセスによって受信されれば、それは孤児メッセージとなる (不整合)
  • しかし、チャンネルはFIFOなので、MARKER()の受信前に、redメッセージが届くことはない
  • => 孤児メッセージは存在しない
• 図6.15と図6.16に示されているルールにより、全ての転送中のメッセージも記録されている
• => 記録されたグローバル状態には整合性がある

6.6.2 アルゴリズム

ローカル変数

p[i]とcp[i]によって既知の静的な変数:

• c_in[i]: p[i]の入力チャンネルに対応するプロセス集合
• in_channel[i][j]: p[j]からp[i]へのチャンネル
• c_out[i]: p[i]の出力チャンネルに対応するプロセス集合
• out_channel[i][j]: p[i]からp[j]へのチャンネル

アルゴリズムの実行によって変わる変数:

• closed[i][c_in[i]]:
  • boolean配列
  • 初期値は全てfalse
  • cp[j]からMARKER()を受け取ったらclosed[i][j] = trueとなる

cp[i]によって実行されるアルゴリズム

! 図6.17を見ながら説明

6.6.3 実行例

アプリケーションプログラムと簡単な実行

アプリケーション:

• 互いにチャンネルを有する二つのプロセス(p[1]とp[2])で構成
• プロセスの状態遷移は図6.18の通り:
  • p[i]はメッセージm[i]の送信で、σ[i][0]からσ[i][1]に遷移
  • 受信で元に戻る
• 図6.19: 実行例(実行のプレフィックス)

グローバル状態計算を上に重ねる

図6.20:

• 図6.19の実行例の上に、グローバル状態の計算処理を重ねたもの
• 計算には以下の４つのタイミングが関わっている:
  • t[0]: cp[1]が計算処理を開始 => ローカル状態σ[1][0]の保存とMARKER()の送信
  • t[1]: p[1]がm[2]を受信 => c_state(2,1)に転送中メッセージとして追記
  • t[2]: cp[2]がMARKER()を受信 => ローカル状態σ[2][1]の保存とMARKER()の送信
  • t[3]: cp[1]がMARKER()を受信 => メッセージの記録をやめる => 計算完了
• 最終的に求められた(Σ,CΣ):
  • Σ = [σ[1][0], σ[2][1]]
  • CΣ = {c_state(1,2)=∅, c_state(2,1)=<m[2]>}

重要な点:

• この計算処理は全くアトミックではない
• 空間・時間ダイアグラムを示しているように、空間(プロセス群)と時間の両方で、分散している

整合カットとラバーバンド変換

• 図6.21は、上で計算されたグローバル状態を反映した、整合カット
  • 実時間軸では、存在(通過)していないグローバル状態、だということが分かる (σ[0][1]とσ[1][2]は共存していない)
• ただし"ラバーバンド変換"を使って、プロセスの軸を伸び縮みさせれば、計算されたグローバル状態を通過するような分散実行を表現可能
  • メッセージの方向が逆転しない範囲なら伸び縮み可能
  • 図6.22
  • => 図6.21と図6.22は、同じ部分順序を定義しており、実際に両者は同じ実行、といえる

6.7 非FIFOチャンネルに適したグローバル状態アルゴリズム

非FIFO版:

• 主にチャンネル状態の保存方法が前節のアルゴリズムと異なっている

6.7.1 アルゴリズムとその原則

ローカル変数:

• 前節と同じ: c_in[i], c_out[i], in_channel[i][k], out_channel[i][k], gs_state[i]
• 追加分:
  • rec_msg[i][c_in[i]]: p[i]が開始後にc_in[k]から受信したメッセージの集合(ログ)
  • sent_msg[i][c_out[i]]: p[i]が開始後にc_out[k]に送信したメッセージの集合(ログ)
  • => 前節のアルゴリズムと異なり、cp[i]は継続的にp[i]を観察(して送受信メッセージを保存)する必要がある

メッセージ:

• MARKER()のような制御メッセージはなくなった
• 代わりに各メッセージが送信元の色(gs_state[i])を示すための1bitの制御ビットを含むようになる

基本ルール:

• greenメッセージは常に消費される
• redメッセージは、受信プロセスの状態がredの場合にのみ消費される
  • => 孤児メッセージを防ぐため
• greenプロセスがredメッセージを受けた場合は、
  • 1. まず、自身のローカル状態を記録する
  • 2. これで、ステートがredに変わるので、その後にredメッセージを消費する

図6.23: アルゴリズム

6.7.2 チャンネルの状態をどうやって求めるか

CΣをどうやって取得するか:

• 各プロセスはローカル計算の完了時点でcp(任意かつ共通の制御プロセス)に(σ[i], rec_msg[i][c_in[i]], send_msg[i][c_out[i]])を送信する
• cpはc_state(j,i)の値をsend_msg[j][i] \ rec_msg[i][j]で求めることが可能
  • 転送中 == 送ったけど受信されていないメッセージ群

このアルゴリズムは孤児メッセージが存在しないことを保証しているので、計算されたグローバル状態((Σ,CΣ))には整合性がある。

例

図6.24: 実行例

• 1. p[1]とp[2]が独立して計算を開始 (ローカル状態を保存)
• 2. p[4]は、p[2]からredメッセージを受け取った時点で、ローカル状態を保存
• 3. p[3]は、p[4]からredメッセージを受け取った時点で、ローカル状態を保存

整合カットは点線で示されている:

• 分割線とクロスしているgreenメッセージは転送中

注記

sent_msg[i][c_out[i]]とrec_msg[i][c_in[i]]は大量のメモリを要求するかもしれないが、どうするか:

• a) ローカルストレージに保存する
• b) アプリケーションによっては送受信の個数だけで十分かもしれない
  • => 特定のチャンネルが空かどうかを判定するだけならこれで十分

6.8 要約

本章では分散実行の性質とそれに関連するグローバル状態(スナップショット)の概念を扱った:

• 分散プログラムの実行に関連する基礎概念群が定義された:
  • イベント、プロセス履歴、プロセスローカル状態、イベント並列性(独立性)、カット、グローバル状態
• 分散実行をモデル化するために三つの手法の導入:
  • イベント群の部分順序、ローカル状態群の部分順序、グローバル状態の格子

次に、整合グローバル状態をオンザフライで求めるアルゴリズムを提示した:

• ベストでも、分散計算が通過したかもしれない、グローバル状態を求めることしかできないことを示した
• 得られたグローバル状態には整合性があるが、プロセスがそれが実行中に実際発生したかどうかを知ることはできない
• この非決定性は非同期分散計算の本質に由来するもの
• この章の目的の一つは、プロセスが自身が生成した分散実行をその場で観察しなければない場合に、こういった相対的な側面があるということ読者に感じてもらうこと

6.9 解題

省略

6.10 演習問題

省略