Distributed Algorithms for Message-Passing System: 第八章

damps-08.md

第八章 非同期分散チェックポイント

• 非同期分散システム上でのチェックポイントを扱う章
• 最初に以下を提示:
  • ローカル及びグローバルチェックポイントの概念
  • 同じ一貫グローバルチェックポイントに属するローカルチェックポイント群のための必要条件と十分条件を述べた定理
• 次に、ローカルチェックポイントによって拡張された分散計算に関連する 以下の二つの一貫性条件を考える (後者の方が強い):
  • 1. Zサイクルフリーダム: 任意のローカルチェックポイントが、一貫グローバルチェックポイントに属することを保証する
  • 2. ロールバック依存追跡性: 一貫グローバルチェックポイントが、オンザフライで各ローカルチェックポイントに紐付け可能なことを示す
• 取り上げるチェックポイントアルゴリズム:
  • 協調的: 分散計算上に付け足して、対応する一貫性条件を確実に満たすようにするアルゴリズム
  • 非協調的: メッセージロギングに基づくアルゴリズム

8.1 定義と主要な定理

8.1.1 ローカルおよびグローバルチェックポイント

六章の復習:

• 分散計算の部分順序による表現: ^S = (S, -σ->)
  • S: プロセス群によって生産された全てのローカル状態の集合
  • σ: ローカル状態間の因果先行関係
• 一貫グローバル状態:
  • ∑ = [σ[1],...,σ[n]]というグローバル状態があるとする
  • 任意の異なるiおよびjにおいてσ[i] || σ[j]が成り立つなら∑には一貫性がある、と云える
    • 上記は全てのローカル状態が互いに依存関係にないことを示している

チェックポイント:

• 大半のアプリケーションは、自身の全てのローカル状態に、ではなくそのサブセットにのみ興味がある
• 各プロセスは、自身のどのローカル状態(群)に関心があるのかを定義する
  • 例えば:
    • グローバル状態上での性質群を検出するため
      • あるローカルチェックポイントでは、あるローカル状態がいくつかの性質を満たしている
    • 一貫性のあるリカバリのためのローカル状態群を定義するため
• そのようなローカル状態は ローカルチェックポイント と呼ばれる
• グローバルチェックポイント: n個(i.e., 各プロセスにつき一つ)のローカルチェックポイントの集合によって表現されたグローバル状態
• 記法:
  • c[i][x]: ローカルチェックポイント
    • iは対応するプロセス識別子、xはそのプロセス内でのシーケンス番号
  • C: 全てのローカルチェックポイントの集合

図8.1:

• ローカルチェックポイント付きの分散実行の例
• チェックポイントおよび通信パターン :
  • ローカルチェックポイントは灰色の矩形の箱で表現
  • 他の関心のないローカル状態は省略される
• 通常、全てのプロセスの「初期ローカル状態」および「最終ローカル状態」はローカルチェックポイントであると仮定される
• グローバルチェックポイント[c[i][1], c[j][1], c[k][1]]には一貫性があり、[c[i][2], c[j][2], c[k][1]]にはないことが、容易に見て取れる

8.1.2 Z依存、ジグザグパス、Zサイクル

用語:

• I[i][x]: インターバル
  • プロセスp[i]の隣接するチェックポイントc[i][x-1]とc[i][x]の間で発生した内部および通信イベント群の呼称
  • 図8.1にも例がある

ジグザグ依存関係とジグザグパス

Z依存:

• -σ->の拡張で、ローカルチェックポイント同士の関係を表す
  • ! 制約をより緩くした感じ
• c[i][x] -zz-> c[j][y]: 以下のいずれかが成立するなら「c[i][x]は、c[j][y]にZ依存している」と云える
  • a) 同じプロセス内のチェックポイント(i.e., i = j)であり、c[i][x]がc[j][y]に先行する (i.e., x < y)
  • b) 以下を満たすメッセージ列<m[1];...;m[q]>が存在する:
    • NOTE: q >= 1, s(m) = mの送信イベント, r(m) = mの受信イベント
    • メモ: 考え方としては、メッセージの送受信に基づく因果関係と同様。ただし依存判定が点ではなくインターバルに広がっている。
    • s(m[1]) ∈ I[i][x+1]:
      • i.e., m[1]はc[i][x]の直後のインターバルの中で送信されている
    • r(m[q]) ∈ I[j][y]:
      • i.e., m[q]はc[j][y]の直前のインターバルの中で受信されている
    • q > 1の場合は、∀ l:1 =< l < qに関して、以下が成立する:
      • 前提: I[k][t]はr(m[l])が発生したインターバル
      • s(m[l+1]) ∈ I[k][t']
      • t' >= t
      • => m[l+1]はp[k]によって、m[l]を受信した(or それ以降の)インターバルで送信された
        • NOTE: m[l]を受信する前に、m[l+1]が送信されている可能性もある (同じインターバルの場合)
      • => このようなメッセージ列は ジグザグパス と呼ばれる
  • c) c[i][x] -zz-> cかつc -zz-> c[j][y]となるcが存在する

例(図8.1):

• メッセージ列<m[5]; m[4]>(or <m[5]; m[6]>)ならc[i][2] -zz-> c[k][2]となる
  • c[i][2] -σ-> c[k][2]も成り立つ
• メッセージ列<m[3]; m[2]>ならc[k][0] -zz-> c[i][2]となる
  • c[k][0] -σ-> c[i][2]は成立しない

定義:

• 「ローカルチェックポイントc[i][x]は、ジグザグパス<m[1];...;m[q]>に属している」:
  • このパスが、次のような隣接する二つのメッセージm[l]とm[l+1]を含む場合:
    • m[l]はp[i]によってc[i][x]の前で受信され、m[l+1]はp[i]によってc[i][x]の後で送信された
  • 例: c[i][2]は、ジグザグパス<m[3];m[2];m[5]>に属している
• 「ローカルチェックポイントcは、ジグザグサイクルに属している」:
  • c -zz-> cの場合
  • 例: c[k][2] -zz-> c[k][2]; <m[7];m[5];m[6]>内のr(m[7])とs(m[5])が同一のインターバルI[i][3]の中で発生しているため

ジグザグパターン

ジグザグパターン (ZZパターンとも表記):

• メッセージ列<m[1];...;m[q]>があるとして:
  • もし以下の両方が成り立つなら、２つの隣接するメッセージm[l]およびm[l+1]は、ジグザグパターンを定義する:
    • a) m[l]の受信とm[l+1]の送信が同じインターバル内で発生している
    • b) m[l+1]の送信は、m[l]の受信の前に発生している
  • 例(図8.1):
    • <m[7];m[5]>、<m[3];m[2]>、<m[5];m[4]>はジグザグパターン
• ジグザグパスを因果パスの差異は、前者にはジグザグパターンがあること
  • 全ての因果パスはジグザグパスでもあるが、逆は真ではない
  • c[1]とc[2]を任意の異なるローカルチェックポイントとすると(c[1] -σ-> c[2]) => (c[1] -zz-> c[2])は常に成り立つ
  • ただし(c[1] -zz-> c[2]) and not(c[1] -σ-> c[2])も可能
    • 例(図8.1): (c[k][0] -zz-> c[i][2]) and not(c[k][0] -σ-> c[i][2])
  • Z依存関係-zz->の方が、因果先行関係-σ->よりも弱い(より包含範囲が広い)、とも云える

8.1.3 主要な定理

ローカルおよびグローバルチェックポイントに関する根本的な質問:

• 以下が与えられたとする:
  • チェックポイントと通信パターン
  • ローカルチェックポイントの集合であるLC
    • 各プロセスにつき最大で一つまでのチェックポイントを含む
• 一貫グローバルチェックポイントを獲得するために、LCを拡張することは可能か？
  • 拡張 = LCに含まれないプロセスのチェックポイントを補填

何が難しいか

問題点を示すために図8.1を再度見てみる:

• 1. LC[1] = {c[j][1]}とする:
  • これを拡張して一貫グローバルチェックポイントを得ることは可能
  • [c[i][1], c[j][1], c[k][0]] や [c[i][1], c[j][1], c[k][1]]
• 2. LC[2] = {c[i][2], c[k][0]}とする:
  • c[j][t] when t =< 1とc[j][t] when t >= 2のどちらも一貫グローバルチェックポイントに属せないことが見て取れる
    • c[i][2]による制約上
  • => LC[2]は拡張不可
• 3. LC[3] = {c[k][2]}とする:
  • c[i][2]とc[i][3]のどちらもc[k][2]と一貫性がない
  • => LC[3]は拡張不可

六章で、もし２つのローカルチェックポイントの間に因果パス関係がある場合には、 それらは同一の一貫グローバルチェックポイントに属することができないことを学んだ。

ただし、因果関係の捕捉だけでは(必要条件ではあるが)十分ではない (! ここが難しさ)。

図8.2:

• LC = {c[i][σ], c[k][γ+1]}とする
• 上の２つには因果関係はない
• ただしc[j][β]ないしc[j][β+1]を加えると、グローバルな一貫性はなくなる
  • 図中のカットラインを参考
• この例は、因果先行に加えて、ローカルチェックポイント間に隠れた依存があることを示している
  • それはチェックポイント群が同じ一貫グローバルチェックポイントに属することを妨げる
• その隠れた依存とは、ジグザグパターンによって作成される
  • 因果先行と共に-zz->関係によって捕捉される

次の定理は、一貫グローバルチェックポイントに拡張可能なローカルチェックポイント群の特徴、を示している。

定理9

• LCをローカルチェックポイントの集合とする
• LCが一貫グローバルチェックポイントに拡張可能なのは、以下が成り立つ場合のみ(if and only if)、
  • ∀c[1],c[2] ∈ LC, we have not (c[1] -zz-> c[2])

証明: "if"部分

• ∀c[1],c[2] ∈ LC, we have not (c[1] -zz-> c[2])が前提
• 証明の流れ:
  • 1. LCを一つ拡張(= ローカルチェックポイントを追加)して、一貫グローバルチェックポイントΣを構築する
  • 2. Σに一貫性があることを証明する
  • => 全プロセスがLCに含まれるまで、これを繰り返す

グローバルチェックポイントΣは以下の様に構築される:

• LET: p[j]はLCにローカルチェックポイントが含まれていないプロセス
• ケース1: ∃ e ∈LC : c(j) -zz-> c
  • p[j]がLCに対してZ依存関係となるローカルチェックポイントc(j)を有する場合
  • Z依存関係がない最初のc'(j)を選択して、LCに追加する
  • 「プロセスの最後の状態はチェックポイントである」という前提により、c'(j)は常に存在する
• ケース2: not(∃ e ∈LC : c(j) -zz-> c)
  • p[j]がLCに対してZ依存関係となるローカルチェックポイントc(j)を有さない場合
  • p[j]の最初のチェックポインtのを選択して、LCに追加する
  • 「プロセスの最初の状態はチェックポイントである」という前提により、そのようなローカルチェックポイントは常に存在する
• => 要するに「LCに対してZ依存関係のない最初のローカルチェックポイントを追加する」というルール

リマインド:

• グローバルチェックポイント(グローバル状態)Σは-σ->関係に基づいている
• Σに一貫性があると証明するためには∀c[1],c[2] ∈ Σに関してc[1] -σ-> c[2]が成立しない必要がある

構築されたΣに一貫性があることを背理法によって証明する:

• (棄却される)仮定: ∃c[1],c[2] ∈ Σ : c[1] -σ-> c[2]
• LET: LC~: Σには含まれるが、LCには含まれないローカルチェックポイントの集合
• c[1] -σ -> c[2]が成立するとしたら、以下の４つのケースがあり得る:
  • 1. c[1], c[2] ∈ LC:
    • LCの定義上not (c[1] -zz-> c[2])となっており、-σ-> ⊆ -zz->なので、`c[1] -σ-> c[2は不可能
  • 2. c[1] ∈ LC~, c[2] ∈ LC:
    • これはc[1] -zz-> c[2]を示唆する
    • => LC~は構築ルール上not (c[1] -zz-> c[2])となるc[1]からなるので、これは不可能
  • 3. c[1] ∈ LC, c[2] ∈ LC~:
    • c[2]は初期ローカルチェックポイントではあり得ない
      • 初期状態(チェックポイント)に因果先行する状態は存在しないため
      • => c[2]は、ケース1によって追加されたチェックポイントだと云える
      • => c[2]は、LCに対してジグザグパスを持たない最初のローカルチェックポイント
    • LET: c[2]'は、p[j]内でc[2]の直前に位置するローカルチェックポイント
    • c[2]'はc[3] ∈ LCに対するジグザグパスを有する (定義上)
    • 以下の２つの組み合わせによりc[1] -zz-> c[3]が成立する(図8.3も参照):
      • a) c[2]' -zz-> c[3]
      • b) c[1] -σ-> c[2]を成立させるメッセージ群
      • => これはc[1],c[3] ∈ LC: not(c[1] -zz-> c[3]) という前提に矛盾する
    • => このケースも不可能
  • 4. c[1], c[2] ∈ LC~:
    • 図8.3のc[1] ∈ LCをc[1] ∈ LC~に置き換えて考えてみる
    • c[1]からLC内のチェックポイント(図だとc[3])へのジグザグパスが存在することになる
    • => これはc[1]の定義(「LC内のいずれのローカルチェックポイントに対してもジグザグパスを持たない最初のチェックポイント」))に矛盾する
    • => このケースも不可能
  • => いずれのケースも矛盾を孕んでいるので、Σがc[1] -σ-> c[2]となるローカルチェックポイント群を含む、という仮定は棄却される

c[1],c[2] ∈ LC: not (c[1] -zz-> c[2])なら、一貫性のあるΣが構築可能、ということは証明された (if部分)。

証明: "only if"部分

∃c[1],c[2] ∈ LC : c[1] -zz-> c[2]なら一貫性のあるΣが構築不可能、ということを示す必要がある。

c[1]とc[2]が同じプロセスの場合の証明は自明なので省略 (c[1] -σ-> c[2]が常に成り立つため)し、別プロセスの場合のみを考える。

• c[1]の後に始まりc[q]の前に終わる<m[1]; ...; m[q]>というジグザグパスが存在することになる

このパス内のメッセージ群の数の帰納によって証明する:

• ベースケース) q = 1:
  • ジグザグパスは一つのメッセージのみを含んでいる
  • メッセージが一つの場合には、ジグザグパス=因果パス、となる必要がある
    • => c[1] -σ-> c[2]が成り立つ
  • => Σは構築不可
• 帰納ケース) q > 1:
  • 帰納的な仮定: 「最大q個のメッセージから成るジグザグパスが２つのチェックポイントを繋いでいる場合、それらは同じ一貫グローバルチェックポイントに属することはできない」
  • 証明:
    • c[1]とc[2]が、q + 1個のメッセージ(<m[1]; ...; m[q]; m[q+1]>)から成るジグザグパスで接続されている場合に、同じ一貫グローパルチェックポイントに属せないこと、を証明
    • 背理法を使う (上の条件の逆が成り立つものと仮定する)
    • c[1] = c[2]の場合には、ジグザグパスはジグザグサイクルとなる
  • LET: c[3]をm[q]の受信の直後に位置するローカルチェックポイントとする
    • ! 本だと"preceding"と記載されているが、図8.4と証明の展開的に、"succeeding"と読み替えるのが正しそうだったのでそう記載
    • p[j]は受信プロセス
  • これは、c[1]とc[3]がジグザグパス<m[1]; ...; m[q]>によって接続されていることを意味する (図8.4)
    • 帰納的な仮定によりc[1]とc[3]は同じ一貫グローバルチェックポイントに属することはできない
    • より一般的には、c[3]の後ろに出現するp[j]内の任意のc[3]'に関して、同様のことが云える
  • つまり、c[1]とc[2]が同じ一貫グローバルチェックポイントΣに属するなら、Σはc[3]に先行するp[j]内のローカルチェックポイントを含んでいなければならないことになる
    • ジグザグパスの定義上m[q + 1]は、c[3]の直前のチェックポイントの後で送信される必要がある
    • 図8.4のc[3]''が条件を満たすローカルチェックポイント
    • => p[j]内でc[3]に因果先行する全てのローカルチェックポイントは、c[2]にも因果先行することが分かる
  • => c[2]は、c[3]に先行するp[j]内のいずれのローカルチェックポイントとも、同じ一貫グローバルチェックポイントに属することはできないことになる
  • => p[j]内のいずれのローカルチェックポイントも、c[1]とc[2]の両方との一貫性は満たせない
  • => 証明完了

以上により、ローカルチェックポイント群LC内にZ依存が存在しない場合にのみ(if and only if)グローバルチェックポイントには一貫性があることが分かる。

無用なチェックポイント

• いずれの一貫グローバルチェックポイントにも属することができないローカルチェックポイントを 無用(useless) と呼ぶ
• 具体的にはZサイクル(c -zz-> c)に属しているローカルチェックポイントが該当する
• 例えば図8.1ではc[k][2]が無用

8.2 一貫チェックポイント抽象

復習:

• ^S: 分散計算; (S, -σ->)
• C: ある分散計算^Sの間に定義された全てのローカルチェックポイントの集合
• (C, -zz->)は、この分散計算のチェックポイント抽象を構成する

非同期チェックポイント問題に対する基本的な疑問:

• (C, -zz->)は、分散計算^Sに対する一貫性のあるチェックポイント抽象であるか？

二つの異なる一貫性条件が、この疑問に対する答えとして考えられる。

8.2.1 Zサイクルフリーダム

定義

• 抽象(C, -zz->)は、Zサイクルに属するローカルチェックポイントを含まない場合に Zサイクルフリー といえる
  • ∀c ∈ C: not (c -zz-> c)
• Zサイクルフリーダムは、無用なローカルチェックポイントが存在しないことを保証する
  • => 全てのローカルチェックポイントが最低でも一つの一貫グローバルチェックポイントに属することになる

ドミノ効果

ドミノ効果:

• 一貫グローバルチェックポイントを探す際に発生する可能性のある現象
• 簡単な例:
  • ローカルな失敗の後に回復可能にするためのローカルチェックポイントを定義するプロセス群を考える
  • 計算を正しく行うためには、再起動プロセスが、他のプロセスを以前のチェックポイント遅延にまで巻き戻して再起動する必要があるかもしれない
  • 図8.5:
    • p[2]のc[2][1]地点から再開:
      • => c[1][3]とc[1][2]のどちらともグローバルな一貫性がない
      • => 前方に戻る、の繰り返し
      • => 初期状態にまで戻ってしまった
    • このような巻き戻り(の連鎖)を ドミノ効果 と呼ぶ
• もしローカルチェックポイント群がZサイクルフリーダムを満たしているなら、ドミノ効果は発生し得ない
  • 上の例なら∑ = [c[1], c[2][1]]となる一貫グローバル状態が常に存在し、そこから再開可能
• これは"可能な限り新鮮(as fresh as possible)"な性質を持つグローバル状態でもある
  • 他の再開可能な一貫グローバルチェックポイント∑'で右の性質が成り立つ: ∑' -∑-> ∑

8.2.2 ロールバック依存追跡性 (RDT)

定義

ロールバック依存追跡性(Rollback-dependency trackability; RDT):

• Zサイクルフリーダムよりも強い一貫性条件
• 抽象(C, -zz->)が「因果先行関係はないが、ジグザグパスでのみ関係づけられるチェックポイントの組」を有するとする:
  • そのような組であるc[1]とc[2]に関してc[1] -zz-> c[2] and not(c[1] -σ-> c[2])が成り立っていることになる
    • この場合、ジグザグパスはジグザグパターンを含むことになる
  • Zサイクルフリーでは、このケースは許容される (のでより弱い)
• RDTでは、ジグザグパターンによって形成される隠れた依存性は全て、因果パスによって"二重化”されている
  • 抽象(C, -zz->)で以下が成立する場合に、RDT一貫性条件を満たしていると云える
  • ∀c[1],c[2] ∈ C : (c[1] -zz-> c[2]) => (c[1] -σ-> c[2])
  • => ローカルチェックポイントと一致する状態だけを考慮した場合 -zz-> ≡ -σ-> となることを意味する
• これはジグザグパスの不在を意味する訳ではない
  • もしジグザグパスによって接続されている二つのローカルチェックポイントがあったとしても、それらを繋ぐ因果パスが別に存在することを意味する
  • そのような"二重化"の例 (図8.1):
    • c[i][2] -zz-> c[k][2]はジグザグパターン[m[5]; m[4]]を有するが、因果パス[m[5]; m[6]]によって"二重化"されている
    • c[k][0] -zz-> c[i][2]の場合には、そのような因果パスは存在しない

なぜRDTが重要か

分散実行のチェックポイントベースの抽象がRDT一貫性条件を満たす場合:

• 任意のローカルチェックポイント間の隠れた依存は、因果パスによって二重化されている
• そのような文脈では定理9を以下のように簡略化できる (Z依存の不在、から、因果先行の不在、へと制約が変わる):
  • 「集合LCは、因果関係にあるローカルチェックポイント同士を含まない場合に、一貫グローバルチェックポイントへと拡張可能」
  • 因果依存は、ベクタークロックを使えば容易に追跡可能
  • そのため、RDT一貫性条件は、以下のようなチェックポイントベースのアプリケーションのデザインを簡略化することができる:
    • a) グローバル性質の検出
    • b) 失敗回復のためのグローバルチェックポイントの定義
• RDTの特筆すべき性質:
  • 各ローカルチェックポイントcを、それを含む最初の一貫グローバルチェックポイントに関連付けることを許す
    • 「オンザフライ、かつ、関連プロセス群の追加の協調」は不要
  • この性質は、以下のようなケースで特に興味深い:
    • ソフトウェアのエラーを追跡しなければならない
    • デッドロックの検出後に回復しなければならない

8.2.3 分散チェックポイントアルゴリズムについて

自然発生 対 強制されたローカルチェックポイント

• アプリケーション依存の理由で、各プロセスp[i]はローカル状態の中のいくつかをローカルチェックポイントとして定義するものとする
  • このようなチェックポイントは 自然発生(spontaneous) チェックポイント、と呼ばれる
  • => これから得られる抽象(C, -zz->)が、前述の一貫性条件を満たす保証はない
• 一貫性条件を保証したいなら、チェックポイントアルゴリズムを分散実行の上に重ねて、追加のローカルチェックポイントが自動で定義されるようにする必要がある:
  • このようなチェックポイントは 強制された(forced) チェックポイント、と呼ばれる
• p[i]のあるローカル状態がローカルチェックポイントとして定義された場合、それは"p[i]はローカルチェックポイントを獲得する"と言われる
• アプリケーション次第で、関連するローカルチェックポイントは、ローカルの揮発メモリに保持されるかもしれないし、ローカルの安定スストレージに保存されるかもしれないし、予め決められたプロセスに送信されるかもしれない

チェックポイントアルゴリズムのクラス

使用する下位の調整メカニズムに従って、分散チェックポイントアルゴリズムは二つのクラスに分類可能:

• a) 協調型(coordinated)チェックポイントアルゴリズム
  • アプリケーションメッセージ上に載せられた制御情報に加えて、特定の(アプリケーションには属さない)制御メッセージを用いる
  • そのためこのクラスのアルゴリズムは、 明示的な同期 に基づいている
    • 6.6節のアルゴリズムがその一例 (「A Global State Algorithm Suited on FIFO Channels」)
• b) 通信導出型(communication-induced)チェックポイントアルゴリズム
  • このクラスのチェックポイントアルゴリズムは 暗黙的な同期 に基づく
  • プロセスは、制御情報をアプリケーションメッセージ上に追加することのみが行える
    • 制御メッセージは許されない
  • その制御情報は、受信プロセスによって、そのメッセージ受信がローカルチェックポイントの強制を引き起こすかどうかを判断するために使用される

8.3 Zサイクル防止を保証するチェックポイントアルゴリズム

この節では以下を行うチェックポイントアルゴリズムを提示する：

• a) Zサイクルフリーダム性質の保証
• b) 各ローカルチェックポイントを、それが属する一貫グローバルチェックポイントに紐づける

8.3.1 Zサイクルフリーダムの操作的な特徴

用語:

• c: ローカルチェックポイント
• c.date: チェックポイントの(操作的な観点から見た)論理時刻を示す整数値
• (C, -zz->): チェックポイント抽象

定理10

(∀ c[1], c[2] ∈ : (c[1] -zz-> c[2]) => (c[1].date < c[2].date)) <=> ((C, -zz->) is Zサイクルフリー)

証明

• =>方向に関して:
  • Zサイクルc -zz-> cが存在すると仮定する(背理法)
  • => 前提からc.date < c.dateが成立することになるが、これが不可能であることは自明
• <=方向に関して:
  • (定義により)(C, -zz->)は循環を含まない(acyclic)
  • => 頂点群に対するトポロジカルソートが存在する
  • => 各頂点cに対してc[1] -zz-> c[2] => c[1].date < c[2].dateを満たすように整数値c.dateを割り当てることが可能

---

• この定理は、Zサイクルフリーダムを保証するすべてのアルゴリズムは、ローカルチェックポイント群の一貫論理日付を実装していることを示している
  • 明示的 or 暗黙的、に
• 明示的にそのような一貫日付システムを実装するアルゴリズムを考えた場合、以下が言えることになる
  • 同じ日付を有するローカルチェックポイント同士は、同じ一貫グローバルチェックポイントに属している

8.3.2 特定の日付システムの性質

チェックポイント抽象(C, -zz->)に対して、Zサイクルフリーダムを満たす以下の日付システムを考えてみる:

• c.date = max{c'.date | c' -zz-> c} + 1:
  • 各ローカルチェックポイントcに対して、可能な範囲で一番小さな一貫日付を紐づけている
• この日付システムは興味深い性質を有している:
  • 各ローカルチェックポイントcを、それが属する一貫グローバルチェックポイントに、システマティックに紐づけ可能にする
  • この日付システムを実装する全ての通信導出型(communication-induced)チェックポイントアルゴリズムは、この性質を有することになる
• 次の定理は、この日付システムについて述べている

定理11

• 前置き:
  • LET: (C, -zz->)を、Zサイクルフリーのチェックポイント・通信パターン抽象、とする
  • 各プロセスのローカルチェックポイントの日付c.dateの決定ルール:
    • 最初のものは0
    • それ以外はmax{c'.date | c' -zz-> c} + 1
  • LET: 各ローカルチェックポイントcを、グローバルチェックポイントΣ(c) = [c[1][x[1]], ..., c[n][x[n]]に紐づける
    • c[i][x[i]]は、c[i][x[i]].date =< c.dateを満たす、p[i]内での最後のチェックポイント
• 本題:
  • 上記の方法により構築したΣ(c)は、cを含んでおり、かつ、一貫性がある

証明

Σ(c)の構築方法により、cがΣ(c)に属することは自明。

Σ(C)に一貫性があることは背理法によって証明する:

• 棄却される仮定: ∑(c)には一貫性がない
• LET: σを、cの日付、とする (i.e., c.date = σ)
• LET: next(x)を、同じプロセス内で時刻xの直後に現れたローカルチェックポイントとする (もしあれば)
• 証明:
  • R1: 定理の仮定により ∀γ∈Σ(c) : γ.date =< σ が成り立つ
  • R2: もしγ∈Σ(c) and next(γ)が存在するなら、γ.dateの定義により、next(γ).date > σが成り立つ
  • R3: (仮定により)Σ(c)には一貫性がないので、∃a,b∈Σ(c) : a -zz-> bとなるローカルチェックポイントが存在する (図8.6)
  • R4: 「R3、日付の定義方法、R1」により a.date < b.date =< σ が成り立つ
  • R5: プロセスの最後の状態はローカルチェックポイントであり、これは他のいずれにもZ依存しないのでnext(a)は常に存在する
    • R3により a -zz-> b となっているので、aはプロセス内の最後のチェックポイントではないことが確実なため
  • R6: R5とR2により next(a).date > σ と言える (! R5はnext(a)の存在を、R2はその日付がσより大きいこと、を示している)
    • さらに、下位の日付システムの性質により next(a).date = max{c'.date | c' -zz-> next(a)} + 1 > σ と言える
    • => max{c'.date | c' -zz-> next(a)} >= σ
  • R7: a -zz-> next(a)およびa.date < σ(R4)より、以下を結論する:
    • R6内で使われる最大の日付は、ローカルチェックポイントgに紐づけられる:
      • gは、aとは別のプロセスによって生成されたローカルチェックポイント
      • ! もしgとaのプロセスが同一の場合、(以下の)「σ以上の~」という条件が成り立たなくなるので (a.date < σにより)
    • g.date = max{c'.date | c' -zz-> next(a)} >= σが成り立つ
  • R8: R7よりg -zz-> next(a)が成り立つ
    • a -zz-> bなので、g -zz -> bも成り立つ (図8.6)
    • 日付システムによりdate(g) < date(b)
  • R9: R7とR8を結合するとdate(b) > σが成り立つ
    • b ∈ Σ(c)なので、これはR1(i.e., date(b) =< σ)と矛盾する
    • => 定理の証明完了

8.3.3 Zサイクル防止を保証する二つの簡単なアルゴリズム

以下の二つのアルゴリズムは両方とも定理10および定理11に基づいている：

• どちらもZサイクルフリーダムを保証しており、定理11の方法で日付をローカルチェックポイントに紐づけている
• => 任意のローカルチェックポイントcに対して、それが属する一貫グローバルチェックポイントが決定可能

実装の話:

• プロセスp[i]は、ローカル変数clock[i]を管理する:
  • このスカラ値は、ローカルチェックポイントに日付を割り当てるために使用される
• 各プロセスは、初期ローカル状態を最初のローカルチェックポイントして定義する
  • 日付は1
  • 全てのローカルクロックも1に初期化される

簡単なアルゴリズム

実装 (図8.7):

• 実装ベースに説明。以下メモ書き:
  • 自発的なローカルチェックポイントの取得前にクロックを増加させる
    • このクロック値が、保存されるローカルチェックポイントの日付となる
  • メッセージ送信時には、現在のクロック値も一緒に送る
  • メッセージ受信時には、送信側のクロックの方が進んでいる場合には、自分のクロックをそれに合わせて、強制的にローカルチェックポイントを保存する

メッセージ受信時の挙動は、以下の観察に基づいている:

• プロセスp[i]によって受信されたメッセージmは、ZZパターンを生み出す可能性がある
  • 図8.8のc[j]からc[k]
• 二つのケースを考える:
  • clock[i] >= sd:
    • (図8.8のように)mがZZパターンを作成したとしても、定理10が要求する以下の(Zサイクルフリーダムを満たすための)不変項は維持されるので問題ない
    • ∀c[1],c[2] : (c[1] -zz-> c[2]) => (c[1].date < c[2].date)
    • => Z依存がある場合、依存先の日付(i.e., clock[i])の方が大きな値になる
  • clock[i] < sd:
    • そのままだと定理10が満たせない
      • 受信プロセス内で、次に自発的に取得されるチェックポイントの日付が、Z依存元以下になってしまう
    • => 図8.8の点線矩形のように、(日付を受信元に合わせた上で)強制的にローカルチェックポイントを取得するようにすれば解決

簡単な改善

観察および改善:

• 観察:
  • clock[i]およびsdの値が何であれ、p[i]が、最後のローカルチェックポイント以後にメッセージを送信していない場合には、ZZパターンは生じ得ない
• 改善:
  • sent[i]という真偽値変数を導入し、上記の"no-send"パターンを認識可能にする
  • 図8.7のアルゴリズムは以下のように修正される
    • sent[i]は、ローカルチェックポイント保存時(行1)にfalseに、メッセージ送信時(行4)にtrueに、設定される
    • 強制的なローカルチェックポイント取得判定(行6)にif (sent[i])が加わる

図8.9:

• 図8.7にsent[i]を追加したアルゴリズムの実行例
• 図8.1の分散実行がベース
  • p[j]の日付5の自発ローカルチェックポイント、および、m[8]メッセージ、が新たに追加されている点が異なる
• 強制ローカルチェックポイントは白の矩形で表現されている
• LET: c(x,y)を、日付がyであるp[x]のローカルチェックポイント、とする
• 例1:
  • 強制ローカルチェックポイントc(j,3)は、<m[5], m[4]>がZZパターンを形成することを防ぐためのもの
  • もしp[j]がm[5]の受信時に、clock[j]の値が3より大きかった場合には、この強制ローカルチェックポイントは取得されなかった
• 例2:
  • 例1とは異なり、p[j]は<m[3], m[2]>によるZZパターンを防ぐ必要はない
    • m[3].date = 1であり、clock[j] = 2以下のため
  • これはc(j,2)が、c(k,1)と同じ一貫グローバルチェックポイントに所属可能なことを意味する
  • なお、c(k,2)に関しても同様のことが言える
    • 定理11によって、(c(j,2)と同じグローバルチェックポイントへの割り当てが)要求されるチェックポイントはこちらとなる
    • c(k,2)の日付(i.e., 2)以下で、一番大きな日付を有するチェックポイントがこれになるため
• 例3:
  • 強制ローカルチェックポイントc(i,4)は、c(k,4)によるZサイクルの形成を防ぐために取得された
• 例4:
  • c(k,5)は、Zサイクル形成の可能性を防ぐために取得された
    • この分散実行では、実際にはそのようなZサイクルは存在していない
  • 加えてc(k,5)は、(定理11のルールに従いつつ)一貫グローバルチェックポイントにc(i,5)を紐づけるためにも必要
  • もしc(k,5)が取得されないとしたら:
    • a) clock[k]がm[8]の受信時に更新された場合：
      • (定理11のルールにより)c(i,5)は、c(j,5)およびc(k,4)と同じグローバル状態に属することになるが、これには一貫性がない
      • c(k,4) -σ-> c(i,5)のため
    • b) clock[k]がm[8]の受信時に更新されない場合:
      • 図8.9のc(k,6)の日付が5となる (c'(k,5)と表記)
      • (定理11のルールにより)c(i,5)は、c(j,5)およびc'(k,5)と同じグローバル状態に属することになるが、これには一貫性がない
      • c(j,5) -σ-> c'(k,5)のため

8.3.4 Zサイクル防止のための最適なアルゴリズムという概念について

Zサイクルを防止する最適な通信導出型チェックポイントアルゴリズムをデザインする際に関係する重要な問題:

• ここでの"最適"とは、アルゴリズムは可能な限り少ない強制ローカルチェックポイントを取得しなければならない、ことを意味する
• 六章・七章で見てきたように、あるプロセスがアクセス可能な知識は、その因果過去のものに制限される
  • プロセスはメッセージ受信によってのみ、新しい知識を学ぶため
• 因果過去に含まれる通信およびメッセージパターン、という点に関して最適な、通信導出型のZサイクル防止アルゴリズムをデザインすることは可能
  • 章末の参考文献も参照
• ただし、このアルゴリズムが全体の計算に対して最適である必然性はない:
  • プロセスp[i]は、因果過去から得られた情報に基づいて、メッセージm受信時には、ローカルチェックポイントを強制しないかもしれない
  • しかし(その時点では不明の)未来のメッセージ交換パターンによっては、m受信時にチェックポイントを強制することは、未来の(p[i] or 他プロセスの)強制ローカルチェックポイント群の節約に繋がるかもしれない
  • => この意味で、Zサイクルを防止する最適なアルゴリズム、は存在しないと言える

8.4 ロールバック依存追跡性を保証するチェックポイントアルゴリズム

8.4.1 ロールバック依存追跡性 (RDT)

定義のリマインダ

8.2.2節の復習:

• RDT: Rollback-Dependency Trackability (ロールバック依存追跡性)
• 通信およびチェックポイントパターン用の一貫性条件の一つ
• Zサイクルフリーダムよりも強い
• 条件:
  • (c[1] -zz-> c[2]) => (c[1] -σ-> c[2])
  • => 因果先行関係の観点から見て、ローカルチェックポイント間に隠れたZ依存関係は存在しない
• RDTの注目に値する性質:
  • 任意のローカルチェックポイントcに対して、それが属する一貫グローバル状態をオンザフライで決定可能
  • その際にプロセス間での追加の通信も発生しない

RDT用のベクトルクロック

因果関係の追跡はRDTにとって関心のある話題であり、操作的なレベルでいえば、ベクトルクロックシステムがその目的に適している。

RDT用のベクトルクロックtdv[i][1..n](transitive dependence vector)は図8.10のようにして管理可能:

• ! 図をベースに説明(時刻の加算タイミング以外は通常のベクトルクロックと同様)
• tdv[i][i]は、p[i]の現在のインターバルのシーケンス番号となる
  • つまり、次のローカルチェックポイントのシーケンス番号と等しい

ベクトル日付:

• 各チェックポイントに紐づけられている
  • c.tdv
• その値は、対応するローカルチェックポイントを取得したプロセスp[i]の現在のtdv[i][1..n]の値

図8.11の例:

• I[j][x+1]は、c[j][x]とc[j][x+1]を分離するインターバル
  • c[j][x]の直後では、tdv[j][j] = x + 1となる
• I[j][x+1]からp[i]への因果パスを形成するメッセージは、tdv[j] > xとなる値を運ぶ
  • => 受信以後はc[i][y].tdv[j] > xとなる

つまり、RDTは、操作的な方法で次のように再定義が可能:

• LET:
  • c[1]とc[2]は任意の異なるローカルチェックポイント
  • c[1]は、p[i]に属している
• 定義:
  • (c[1] -zz-> c[2]) <=> (c[1].tdv[j] < c[2].tdv[j])

もし通信およびチェックポイントパターンがRDT一貫性条件を満たす場合:

• 前述のベクトルクロックシステムは、プロセスp[i]が、各チェックポイントcを、それを含む最初の一貫グローバル状態に、オンザフライに関連付けることを可能にする
• このグローバルチェックポイントΣ = [c[1],...,c[n]]は、以下のように定義される:
  • a) c[i]は、c (p[i]のtdv[i]番目のローカルチェックポイント)
  • b) i != jとなるc[j]は、p[j]のc.tdv[j]番目のローカルチェックポイント
  • ! bのルールは、aを包含している

8.4.2 簡単な力づくのRDTチェックポイントアルゴリズム

RDTを保証するために、全てのZZパターンの形成を防止する、とてもシンプルなアルゴリズムがある:

• その目的のために、このアルゴリズムは、通信およびチェックポイントパターンに、以下を強制する:
  • 図8.12のようなパターン
  • "Russell's pattern(ラッセルのパターン)"と呼称される
  • 正規表現的に表すなら、一つのプロセス内では(メッセージ受信* メッセージ送信* ローカルチェックポイント+)*といったパターンが要求される
  • => メッセージ送信の後に続くメッセージ受信は、必ず間がローカルチェックポイントによって区切られている

図8.13は上述のアルゴリズムの実装:

• 簡潔性と各プロセスにつき一つの真偽値しか必要としない点が興味深い
• 図8.10のアルゴリズムを使えば、各チェックポイントcにベクトルクロックを紐づけることも可能

8.4.3 送信後の確定した依存(FDAS)に基づくRDTチェックポイントアルゴリズム

強制ローカルチェックポイントのための述語について

プロセスによって管理されアプリケーションメッセージに運ばれる制御データ次第で、強制チェックポイントのためのより強い述語をデザインすることが可能:

• "より強い(stronger)"の意味:
  • P1とP2を強制チェックポイントを取得するために使われる二つの述語とする
    • 適用結果がtrueの場合には、チェックポイントを取得しなければならない
  • 以下が成り立つ場合には、P1はP2よりも強い、といえる:
    • 同じ文脈で評価された場合にP1 => P2が常に成立する
    • P2がtrueでも、P1がfalseとなるケースがあり得る
      • その場合、P2はチェックポイントの取得を強制するが、P1はしない
    • => P1の方が強制チェックポイントの数が少なくて済む、といった意味合いで、より強い、といえる
• ローカルチェックポイントの取得は高価かもしれないので、より強い述語(i.e., 可能な限り少ない強制チェックポイント)を探すのは重要
  • ディスクに保存する必要がある場合には特に
• この節では、図8.13のアルゴリズムよりも強い述語を提示する:
  • "fixed dependency set after send"(FDAS)と呼ばれる述語

FDAS述語とFDASアルゴリズム

この述語は二つのローカル変数を用いる:

• sent[i]: 図8.13(Russell's checkpointing)のアルゴリズムと同様
• tdv[i][1..n]: プロセスp[i]のベクトルクロック
  • tdv[1..n]としてメッセージに乗せて運ばれる

実装は図8.14:

• 基本的には図8.13と図8.10(RDT用のベクトルクロック)を組み合わせたもの
• sent[i] and (∃k : tdv[k] > tdv[i][k])が、メッセージ受信時に強制チェックポイントを取得するかどうか、を決める述語:
  • sent[i]に関して:
    • 既に見たように、最後のチェックポイント取得以後にメッセージを送信していないなら、メッセージmの受信によってZZパターンが生成されることはない
    • => sent[i] = falseなら、強制チェックポイントは不要
  • ∃k : tdv[k] > tdv[i][k]に関して:
    • もし∀k : tdv[k] =< tdv[i][k]なら、ローカルチェックポイントの観点からは、p[i]は、mの送信者が把握していることは、全て知っていることになる
      • このメッセージはp[i]に、ローカルチェックポイント間の依存に関して、新しい情報は提供しない
      • => p[i]にとって未知のままとなるローカルチェックポイント依存を作成することはできない
    • => ∃k : tdv[k] > tdv[i][k]がfalseなら、隠れた依存が存在しないことが確実なので、強制チェックポイントは不要

FDASという名前の由来:

• 任意のプロセスに関して、あるインターバルの最初のメッセージ送信以後、推移的な依存ベクトルは、次のローカルチェックポイントまで変わらないまま、という事実から来ている
• ! というか、もし依存ベクトル(i.e., tdv)に更新がある場合には、強制チェックポイントが取得される (ので上の事実が常に成立する)

8.4.4 強制されたローカルチェックポイントの数をさらに削減する

プロセスが、その実行中のいくつかのポイントで、強制ローカルチェックポイントを取得する、という事実は、 アプリケーションプログラムによって定義される通信およびチェックポイントパターンに、直接的な影響を持っている:

• 通信パターンは修正できないが、チェックポイントパターンは可能
  • => 現在で追加の強制ローカルチェックポイントを取得することで、未来の強制ローカルチェックポイントの数を減らせるかもしれない
• 成し得る最高のことは、（アルゴリズムが自由に使える)制御情報をもとに可能な限り少ない強制ローカルチェックポイントで済むような、述語を探すこと
• この節では、BHMRという述語、および、それに対応するチェックポイントアルゴリズムを提示する
  • これは前節のFDASよりも強い述語
  • ! "BHMR"は、提案者達の頭文字に由来している？

追加の制御変数

この述語(および関連アルゴリズム)のデザインの根底にあるアイディア:

• 以下を補足するために、制御変数群が追加されている:
  • 因果先行関係、と、各プロセスによって取得された最後のローカルチェックポイント、の相互作用
• tdv[i][1..n]に加えて、三つの制御変数が追加されている
  • いずれも真偽値の配列 (一次元 or 二次元)

追加制御変数:

• sent_to[i][1..n]:
  • p[i]が、最後のローカルチェックポイント以降にp[j]に対してメッセージを送信している場合には、sent_to[i][j] = true、となる
  • 初期値は全てfalse
• causal[i][1..n, 1..n]:
  • causal[i][k,j]は、以下の場合にのみ(if and only if)trueとなる:
    • p[i]の知識で、以下の因果パスが存在する:
    • FROM: p[k]によって取得された最後のローカルチェックポイント (p[i]にとって既知)
    • TO: p[j]によって取得されるであろう次のローカルチェックポイント
      • p[i]が知っているp[j]の最後のローカルチェックポイントの、次に来る(p[j]の)ローカルチェックポイント
  • 初期値:
    • 対角線上(e.g., causal[i][j,j])の値に関してはtrue、それ以外は全てfalse
  • 例: 図8.15
    • μ、μ'、μ''は因果パス
    • p[i]がメッセージmを送信する時点で、causal[i][k,j]およびcausal[i][k,i]およびcausal[i][j,i]、の値はtrueとなっている
    • causal[i][k,j]:
      • p[i]はμ''により、p[k]からp[j]への因果パスμの存在、を知っている
    • causal[i][k,i]:
      • μ'と<μ; μ''>の両方の因果パスによるもの
    • causal[i][j,i]:
      • 因果パスμ''によるもの
• pure[i][1..n]:
  • pure[i][j]は、以下の場合のみ(if and only if)trueとなる:
    • p[i]の知識で「p[j]の最後のローカルチェックポイントから始まり、間に何らかのローカルチェックポイントを挟み、p[i]で終わる」といった因果パスが存在しない
  • 例: 図8.16
    • あるプロセスから自分自身への、間に別のローカルチェックポイントを挟まない、因果パスはpureと呼ばれる
    • 左がpureで、右がimpure
  • 初期値:
    • pure[i][i]はtrue (以後も常にtrueとなる)
    • それ以外(i.e., j != iのpure[i][j])はfalse

強制されたローカルチェックポイントを取得するためのBHMR述語

メッセージ:

• MSG(m, tdv, pure, causal)は、p[i]によって受信されるメッセージ
• p[j]が送信者だとした場合、m以外は、メッセージ送信時の対応する変数の値となる (e.g., tdvならtdv[j])

この述語は二つのパートから構成される (p[i]は受信者、p[j]は送信者、i != j):

• 第一パート:
  • p[j]からp[i]への因果パスに関与している
  • 述語: ∃(k,l): sent_to[i][k] and ((tdv[k] > tdv[i][k]) and not causal[k,l])
    • ! 前の二つは「ZZパターンが存在する可能性があるか」を、最後の一つは「因果パスが存在するか」を判定している
    • => ZZパターンが存在する可能性があったとしても、因果パスによって二重化されているなら、問題にはならない
  • ∃k: sent_to[i][k] and (tdv[k] > tdv[i][k])の部分は、単一プロセスベースのFDAS述語、となる:
    • これがtrueの場合、
      • a) p[i]は最後のローカルチェックポイント以後に、p[k]に対してメッセージm'を送信しており、かつ、
      • b) p[j]はp[i]よりも多く、p[k]のローカルチェックポイントを知っている
      • => 隠れたZZパターンが(メッセージ受信により)生じる可能性がある
  • しかし(上の前半部分がtrueでも)、causal[k,l] = trueの場合：
    • p[j]は、p[k]の最後のローカルチェックポイントからp[l]への因果パスが存在すること、を知っている
      • ! つまりmの受信により、p[k] -σ-> p[j] -σ-> p[i]といった因果パスが作られている
    • => p[i]は、強制ローカルチェックポイントを取得する必要はない
      • メッセージmの受信、および、p[i]からp[k]に以前に送られたメッセージm'、によって生じるZZパターンは、因果パスによって二重化されているため
      • 参考: 図8.15のジグザグパス<μ'; m; m'>は、因果パスμによって二重化されている
        • ! 本文に記載のケースと完全に一致している訳ではない
  • 結果として、p[i]は保守的にnot causal[k,l]の時にのみローカルチェックポイントを取得する
• 第二パート:
  • p[i]の最後のローカルチェックポイント以後の、自分自身への因果パスに関与している
  • 述語: (tdv[i] = tdv[i][i]) and not pure[i]
  • 例: 図8.17
    • p[i]のあるインターバル内で開始および終了している因果パスが、別のローカルチェックポイントcを含んでいる
    • => 強制ローカルチェックポイントを取得しないと、Zサイクルが形成されてしまう

! 二つのパートはor結合される

BHMRチェックポイントアルゴリズム

図8.18: 前述の制御データ及び述語に基づくアルゴリズム

• LET: 自プロセス=p[i]、相手プロセス=p[j]
• take_local_checkpoint():
  • 現在のベクトルクロックをチェックポイントと一緒に保存 (c.tdv = tdv[i][1..n])
  • 変数リセット:
    • sent_to[i][k] <- false
    • pure[i][k] <- false (k != i)
    • causal[i][k] <- false (k != i)
  • ベクトルクロックの更新: tdv[i][i] += 1
• メッセージ送信時:
  • 各種制御変数を乗せる
  • sent_to[i][j]の値をtrueに設定
• メッセージ受信時:
  • 前述の述語を用いて判定を行いtrueの場合には、強制ローカルチェックポイントを取得する
  • 制御変数の更新:
    • tdv[i][1..n]:
      • 通常のベクトルクロックを同様の更新 (受信側と送信側で新しい方の値を採用)
    • pure[i][1..n]:
      • 送信側と受信側でkに関する知識が等しい場合: pure[i][k] and pure[k]の値を採用
      • それ以外は、kに関する知識が新しい方の値を採用
    • causal[i][k,l]:
      • 送信側と受信側でkに関する知識が等しい場合: causal[i][k,l] or causal[k,l]の値を採用
      • それ以外は、kに関する知識が新しい方の値を採用
    • causal[i][l,i]:
      • causal[i][l,i] or causal[l,j]の値を採用
      • => メッセージ受信によりl => j => iという因果パスが新たに加わった場合のハンドリング

このアルゴリズムは、強制ローカルチェックポイントの数を削減する:

• コスト: 制御データとアプリケーションメッセージに相乗りする情報、がより多くなる
  • n^2 + nビット(for causal and pure 配列)とn個の整数(for 論理日付ベクトル)、を運ぶ必要がある
• また、8.3.4節でZサイクル防止に関して見たのと同様に、RDTを保証する"最適な"通信導出型のチェックポイントアルゴリズムは存在しない

8.5 非協調的チェックポイントのためのメッセージロギング

8.5.1 非協調的チェックポイント

非協調的チェックポイント:

• 各プロセスが独立して自分のローカルチェックポイントを定義する
  • 強制チェックポイント、という概念は存在しない
• このアプローチは、ドミノ効果に対して脆弱:
  • プロセスが定期的、かつ、少数のローカルチェックポイントを取得する、ようなアプリケーションにとっては興味深くなり得る
  • e.g., 失敗発生後のバックワードリカバリ
• 一貫グローバルチェックポイントは、リカバリアルゴリズムによって、計算されなければならない
  • この目的のためにアルゴリズムは、チャンネル状態も計算しなければならないかもしれない
    • チャンネル状態も、計算されたグローバルチェックポイントに対して一貫性があるようなものである必要がある
    • => そのためには、プロセスは実行中に__安定ストレージ上にメッセージを保存__する必要がある

悲観的 対 楽観的メッセージロギング

手法の分類。

送信者ベース or 受信者ベース:

• メッセージが送信者によって保存されるなら__送信者ベース__
• メッセージが受信者によって保存されるなら__受信者ベース__

悲観的ロギング or 楽観的ロギング:

• 悲観的ロギング:
  • メッセージは安定ストレージに、送信(or 受信)のタイミングで保存される
  • 失敗フリーな実行では高いオーバヘッドを招く
    • 各メッセージが追加のI/Oを引き起こすため
• 楽観的ロギング:
  • メッセージは最初に__揮発ログ(volatile log)__に保存される
  • この揮発ログは、プロセスがローカルチェックポイントを取得する際に、(ローカル状態と一緒に)安定ストレージに保存される

この節の内容

• 楽観的な送信者ベースのメッセージロギングアルゴリズムを提示している
• このアルゴリズムの主要な特徴は、安定ストレージに保存する必要があるのは、揮発ログに保存されたメッセージ群のサブセットのみ、という点
• 簡単のために、チャンネルはFIFOを仮定

8.5.2 安定ストレージにメッセージを保存するべきか

基本原理

• LET: c[i][x]: プロセスp[i]によるx番目のチェックポイント
• p[i]は、メッセージmを送信する際、それをローカルの揮発ログに保存する　
• その後、p[i]が次のローカルチェックポイントc[i][x+1]を取得する時には、以下を行う:
  • a) c[i][x+1]と揮発ログの中身を、安定ストレージに保存する
  • b) 揮発ログを空に再初期化する
  • => メッセージ群は、個別にではなく、まとめて安定ストレージに保存される
  • => I/Oの数(つまり、メッセージロギングに付随するオーバヘッド)を削減可能
• 例: 図8.19
  • m[1]、m[2]、m[3]が揮発ログに一時的に保存されるよ、といった話

保存するかしないか、それが問題だ

問い:

• p[i]が次のローカルチェックポイントc[i][x+1]を取得する際に、揮発ログ内のメッセージ群のどれを安定ストレージに保存すべきか？

答え:

• 図8.20を参照
• 左側の図:
  • c[j][y]とc[i][x+1]は平行なので、同じ一貫グローバル状態に属することが可能
  • p[i]からp[j]へのチャンネル状態には、転送中のメッセージmを含む
  • => そのためmは、(p[j]の)安定ストレージに保存される必要がある
• 右側の図:
  • c[j][y]とc[i][x+1]を繋ぐ、μという因果パスが新たに追加された
  • 両者は平行ではなくなったので、同じ一貫グローバル状態に属することはできない
  • => mを安定ストレージに保存する必要はなくなった (ただしp[j]はそれを認識できない)
    • mが転送中として、ある一貫グローバル状態に含まれる可能性はなくなったため
• 下側の図:
  • (右側の図とは異なり)p[j]が、mを安定ストレージに保存する必要がないことを認識できているケース
  • => 同じインターバル内に、自分から始まり自分で終わる因果パスがある場合には、最初に送信したメッセージを安定ストレージに保存する必要はない

チェックポイントアルゴリズム: ローカルデータ構造

つまりp[i]は、一貫グローバルチェックポイントに属する可能性のある送信メッセージ群、のみを安定ストレージに保存する必要がある。

このアイディアの実装に必要な制御データ構造:

• volatile_log[i]:
  • p[i]の揮発ログ
  • 初期値は空
• sn[i][1..n]:
  • シーケンス番号の配列
  • sn[i][j] = σは、p[i]がσ個のメッセージをp[j]に送信したことを意味する
• rec_known[i][1..n,1..n]:
  • シーケンス番号の(二次元)配列
  • p[i]が把握している、各プロセスの間で交換されたメッセージの数、を表現している
  • rec_known[i][j,k] = βは、p[i]が「p[j]がp[k]から、β個のメッセージを受信済みである」ことを(因果パスにより)知っている、ことを意味する
  • ! チャンネルがFIFOなので、シーケンス番号=受信メッセージ数、となる
• ckpt_vc[i][1..n]:
  • ローカルチェックポイントに対応するベクトルクロック
  • ckpt_vc[i][j] = γは、p[i]が「p[j]がγ個のローカルチェックポイントを取得済み」であることを知っている、ことを意味する
  • この制御データは、チェックポイントアルゴリズムによって管理され、リカバリアルゴリズムによって一貫グローバル状態を計算するために使用される

チェックポイントアルゴリズム: プロセスの振る舞い

実装: 図8.21

• メッセージ送受信時の挙動は、コードの通り
• 自発的なローカルチェックポイント取得の際の補足:
  • 揮発ログから不要なエントリを間引く:
    • <m,sn,dest> ∈ volatile_log[i] : sn =< rec_known[i][dest, i]なら不要と判定
    • => 図8.20の下側の図の通り「(同じインターバル内で)自分の送信メッセージが相手に受信されたことを知った」場合には、その送信メッセージの保存は不要
  • (リカバリのために)揮発ログを含めた制御データを安定ストレージに保存する:
    • <σ[i], volatile_log[i], sn[i][1..n], ckpt_vc[i][1..n], rec_known[i,1..n]>を保存
      • sn[i][1..n]: 各プロセスに対する送信メッセージ数
      • rec_known[i][i,1..n]: 各プロセスからの受信メッセージ数
    • サイズ: ローカル状態 + 揮発ログ + n要素の配列*3

8.5.3 リカバリアルゴリズム

前述の非協調チェックポイントアルゴリズムに対応する、リカバリアルゴリズム。

失敗が発生した際に、リカバリアルゴリズムは、下記の手順を実行する:

1. 失敗していないプロセス群は、最初にローカルチェックポイントを取得することが要求される
2. 最近のn個の平行ローカルチェックポイントが、反復的に計算される:

• コードメモ:
  • 1. 各プロセスの最後のローカルチェックポイントを集める
  • 2. あるローカルチェックポイント間に依存(i.e., c[i] -σ-> c[j])がある場合には、平行となる最初のc'[j]を求める
  • 3. 全てが平行になるまで繰り返す
• 定理6(TODO: 引用する)のお陰で、c[i] -σ-> c[j]およびnot (c[i] -σ-> c'[j])は、c[i].chpt_vcのベクトル日付から効率的に求めることが可能
• 各プロセスの最初のローカル状態はローカルチェックポイントである、という仮定により、前述のループはいつかは終端し、最終的に一貫性のあるΣが得られる

3. p[i]からp[j]へのチャンネルの状態は、p[i]の安定ストレージから、以下のように抽出できる:

• NOTE: この計算に関わるのは送信者であるp[i]のみ
  • ! その割にはp[j]も登場している (rk(j,i)の箇所で)
  • ! 実際に、p[i]の知識だけでは、p[j]の受信状況の完全は把握は無理なので、正確なチャンネル状態の復元は不可能 (英文の解釈が間違っている？)
• LET: (c[i],c[j])を、p[i]からp[j]に対して転送中のメッセージの集合、とする (= チャンネル状態)
• LET: sn(i,j)を、p[i]によってc[i]とともに安定ストレージに保存されたsn[i][j]の値(シーケンス番号)、とする
  • i.e., c[i]を取得する前のp[i]からp[j]への送信メッセージ数
  • => c[i]の後に、p[i]からp[j]に送信されるメッセージは、sn(i,j)より大きなシーケンス番号を持っている
• LET: rk(j,i)を、p[j]によってc[j]とともに安定ストレージに保存されたrec_known[j][j,i]の値(シーケンス番号)、とする
  • i.e., c[j]を取得する前に、p[j]がp[i]から受信したメッセージ数
  • => c[j]の前に、p[j]がp[i]から受信したメッセージは、rk(j,i)以下のシーケンス番号を持っている
• チャンネルはFIFOなので、rk(j,i) < sqnb =< sn(i,j)を満たすsqnbを有するメッセージ群は、(c[i],c[j])に対して転送中である、といえる
  • 参照: 図8.22
• 図8.12の行12の述語(= 不要な揮発ログエントリ判定)より、このような転送中のメッセージ群は、p[i]の揮発ログから削除されない
  • c[i]とともに、p[i]の安定ストレージ内の保存されている (ので回復可能)
  • ! p[i]の知識による保守的な(?)述語なので「実際にはp[j]によって受信済みだけど、p[i]によって転送中と判定される」メッセージはあり得る

8.5.4 いくつかの改善

強制チェックポイントを加える

基盤となるチェックポイントアルゴリズムが非協調な場合でも、ドミノ効果の影響を削減するために、定期的に少数の強制チェックポイントを取得することは可能。

空間の再利用

一貫グローバルチェックポイントΣが決定されるとすぐに、安定ストレージに保持されている(その地点以前の)制御データは不要で破棄可能となる。

各プロセスの安定ストレージを節約するために、バックグランドタスクで、定期的に最近の一貫グローバルチェックポイントを計算することも可能。

コスト

• p[i]によって送信される各メッセージは、マトリックスrec_known[i][1..n,1..n]の現在の値を運ばなければならない
  • => 効率性を削減し、アプリケーションプログラムをペナルティを課し得る
• 実際には、アプリケーションプログラムのチャンネルに対応する、マトリックス内のエントリのみが、考慮される必要がある
  • もし通信グラフが有効リングの場合には、マトリックスはベクトルに縮小する
  • 通信グラフが双方向チャンネルからなる木の場合でも、同様の利益が得られる
• さらに、チャンネルはFIFOなので、p[i]からp[j]に送信される連続する二つのメッセージでは、(後者に関しては)差分のみを送れば良い

同期システムの場合

同期システムでは、ドミノ効果の被害を被ることなく、非協調チェックポイントの恩恵を受けることが容易にできる:

• 各プロセスが、ある決まったラウンドの終わりにローカルチェックポイントを取得すれば十分

8.6 要約

• この章では、非同期分散チェックポイントを扱った
• 各プロセスが互いに独立してローカルチェックポイントを取得すると仮定のもとで、二つの一貫性条件を提示した：
  • a) Zサイクルフリーダム
  • b) ロールバック依存追跡性
• それから、一貫性条件を満たすために、プロセスに追加のローカルチェックポイントを強制する分散アルゴリズムを提示した
• また、ジグザグパスやローカルチェックポイント間のZ依存関係、といった重要な概念も導入した
• 最後に、非協調的チェックポイントに適したメッセージロギングアルゴリズムを提示した

8.7 解題

省略

8.8 演習問題

省略