Distributed Algorithms for Message-Passing Systems: 第四章

damps-04.md

第四章 リーダー選出アルゴリズム

抜粋

• リーダー選出問題を扱った章
• リーダー選出:
  • 分散システムを構成するプロセス群中から一つを選ぶ
  • 通常、選ばれたプロセスは、調整/制御を目的とし、特別な役割を果たすことが要求される
• リーダー選出は分散システムの対称性を崩す
• この章では、
  • まず、無名ネットワークでリーダーを選出することが不可能なことを示す
  • その後、名前有りリングネットワークを対象とした、いくつかのリーダー選出アルゴリズムを紹介する

4.1 リーダー選出問題

4.1.1 問題の定義

各プロセスp[i]は、以下の変数を有する:

• elected[i]:
  • 初期値はfalse
  • リーダーに選出されたプロセスのみがtrueになる
• done[i]
  • 初期値はfalse
  • アルゴリズムの実行完了を把握した時点でtrueになる

記法:

• var[i][t]: ローカル変数var[i]の時間tでの値

形式的な定義: 満たすべき性質

安全性プロパティ:

• 1. (ALL{i} : elected[i][t] => (ALL{t' >= t} : elected[i][t'])) and (ALL{i} : done[i][t] => (ALL{t' >= t} : done[i][t']))
  • => elected[i]およびdone[i]は安定: 一度trueになったら、それが永続する
• 2. ALL{i,j,t,t'} : (i != j) => !(elected[i][t] and elected[j][t'])
  • => 最大でひとつのプロセスのみが選出され得る
• 3. ALL{i} : done[i][t] => (SOME{j,t' =< t} : elected[j][t'])
  • => 各プロセスは、リーダーが選出されるまでは、ローカルアルゴリズムを完了することができない

終了プロパティ(生存性プロパティの一種):

• 1. SOME{i,t} : elected[i][t]
• 2. ALL{i} : SOME{t} : done[i][t]
• => 最終的には「リーダーが選出」されて、その事実を「全てのプロセスが(いつかは)認識する」ことを述べている

4.1.2 無名システム: 不可能な事柄

この節での仮定:

• プロセスは識別子を持たない:
  • p[i]とp[j]の見分ける方法は存在しない
  • 全てのプロセスは「同じ数の隣人」、「同じコード」、「同じ初期状態」を有する
    • それらの差異は、プロセス群を識別可能とする要因となり得るため
  • => 無名システム
• 簡単のためにネットワークの形はリングであるものとする

定理2:

n > 1 個のプロセスが存在する(無名な)単方向/双方向リングで、リーダー選出を決定論的に行えるアルゴリズムは存在しない

証明:

• ざっくりと
• 無名システムでは、安全性プロパティ(一意なリーダーの選出)と終了プロパティ、のどちらも満たせない
• なぜなら、
  • 1. 全てのプロセスの初期状態は同じ (全てのプロセスは対称的)
  • 2. コードが同じなので、次の遷移する状態も全て同じ
  • 3. リーダー選出には非対称性が必要 (i.e., リーダーと他のプロセスは状態が異なる)
    • => 無名システムでは、非対称な状態に辿りつけないので、安全性プロパティは満たせない
  • 4. リーダーが選出されないと、プロセスの実行が停止できないので、終了プロパティも満たせない
  • => 証明完了

4.1.3 選出における基本的な仮定と原則

基本的な仮定

前節の定理があるため、この章の残りでは、以下を仮定する:

• 全てのプロセスは一意な識別子を有する
• 識別子は<,=,>といった演算子で比較可能 (全順序)

選出アルゴリズムの基本的な原則

選出アルゴリズムの基本的なアイディアは「識別子が極値なプロセスを選出」すること:

• 最小値 or 最大値
• 識別子は「一意」かつ「比較可能」なので、必ず一つ極値となる識別子が求められる

4.2 計算量がO(n^2)なシンプルなリーダー選出アルゴリズム(単方向リング用)

4.2.1 文脈および原則

文脈

• ネットワークの構成は単方向リング
• チャンネルはFIFOであることは要求されない
• プロセスの初期知識: 「自分自身の識別子(id[i])」および「それが全体で一意であること」
  • プロセスの総数は知らない

原則

アイディア:

• 1. 各プロセスp[i]は、自分の識別理をリング上に送信する
• 2. 自分のid[i]より小さなid[j]を受信したら、その進行(中継)を停止する
• 3. 一番大きな識別子のみが、誰にも止められずに、リング上を一周する
  • => この識別子を持つプロセスがリーダーに選出される

4.2.2 アルゴリズム

• 図4.1: アルゴリズム
  • 口頭で説明
• ローカル変数:
  • id[i]
  • elected[i]
  • done[i]
  • part[i]: ローカルアルゴリズムを開始しているかどうか
  • leader[i]: 選出されたプロセスの識別子

4.2.3 アルゴリズムの時間コスト

• 前提: 一回のメッセージ送信は、一タイムユニットを消費するものとする
• elected()メッセージは、常にn回送信される(リングを一周する)
  • n: プロセス数
• election()メッセージについて考える:
  • 最善のケース:
    • 1. 一番大きな識別子を持つプロセスp[i]のみがstart()を受け取る
    • 2. id[i]がリングを一周して終わり
    • => n掛かる
  • 最悪のケース:
    • 1. 二番目に大きな識別子を持つプロセスp[j]のみがstart()を受け取る
      • かつ、一番大きな識別子を持つプロセスp[i]は、p[j]の前方に位置する
    • 2. id[j]が、p[i]に到達するまではn - 1掛かる
    • 3. id[i] > id[j]なので、p[i]が(id[j]を破棄して)id[i]の送信を行う
    • 4. id[i]がリングを一周するまではn掛かる
    • => 2n - 1掛かる

結論: 時間計算量はO(n)

4.2.4 アルゴリズムのメッセージコスト

最善及び最悪のケース

最善のケース:

• 時間計算量での最善ケースと同様
• 一番大きな識別子を持つプロセスのみがstart()を受け取る
• election()がリングを一周して終わる
• => n個のメッセージ

最悪ケース:

• 以下の状況で発生し得る:
  • a. 全てのプロセスがstart()を受け取る (parrt[i] = falseの状態で)
  • b. 全てのメッセージは一タイムユニットを消費
  • c. プロセスがリング上に「識別子の降順」で並んでいる (図4.2)
• つまり、 -「一番大きな識別子はn回送信」、「二番目に大きな識別子はn-1回送信」、etc
• 合計: sum(1..n) = (n * (n + 1)) / 2
• => O(n^2)個のメッセージ

平均ケース

• P(i,k):
  • p[i]の識別子id[i]が、k個先のプロセスまで転送される確率
    • p[i]は、i番目に小さな識別子を持つプロセス
  • 式: ({i-1, k-1} / {n-1, k-1}) * (n-i / n-k)
    • {a,b}: サイズaの集合の中からb個の選ぶ際に可能な組み合わせ数
    • 前半部分:
      • 「iより小さいプロセス群からk個の組み合わせ数」 / 「iを除いたプロセス群からk個の組み合わせ数」
      • => k-1個、より小さいプロセスが隣接する可能性
    • 後半部分:
      • 「iより大きいプロセスの個数」 / 「kより後ろの隣接プロセス数」
      • => k番目の隣接プロセスの識別子がid[i]よりも大きい確率
• id[i]を保持するメッセージが転送される期待回数
  • i == n:
    • 常にリングを一周するので n
  • i != n:
    • ! kindleは誤植がある (シグマの初期値の設定部分が = ではなく - になっている)
    • ! 書籍の方が適切そうだがE[i](k)ではなくE[i]では？ (引数のkは使っていなさそう)
    • E[i]: sum({k * P(i,k) || k <- 1..(n-1)})
• 全てのメッセージの期待転送回数は、
  • E: n + sum({E[i]() || i <- 1..(n-1)})
• 上の式を単純化すると、
  • E: n + sum({ n / (k + 1) || k <- 1..(n-1) })
  • => n * (1 + 1/2 + 1/3 + ... + 1/n)
• 上のharmonic series (1 + 1/2 + ...) の上界はc + log(e, n) (cは任意の定数)
  • => 平均計算量はO(n log n)

;; 参考: CommonLispでの各式の実装
(defun ways (n x)
  (cond ((= n 0) 0)
        ((= x 0) 1)
        (t (* n (ways (1- n) (1- x))))))

(defun p (i k n)
  (let ((a (ways (1- i) (1- k)))
        (b (ways (1- n) (1- k)))
        (c (- n i))
        (d (- n k)))
    (* (/ a b) (/ c d))))

(defun e-i (i n)
  (assert (and (> i 0) (<= i n)))
  (if (= i n)
    n
    (loop FOR k FROM 1 BELOW n SUM (* k (p i k n)))))

(defun e (n)
  (+ n (loop FOR i FROM 1 BELOW n SUM (e-i i n))))

4.2.5 簡単な変種

• 図4.1では、全てのプロセスの中から、最大の識別子を持つものをリーダーにしていた
• それを「(election()の受信前に)start()を受け取ったプロセスのみがリーダー候補になり得る」ように修正したのが図4.2
• idmax[i]というローカル変数を導入して、election()受信時に自動でアルゴリズムを開始しないようになっている以外は、以前とほぼ同様

4.3 計算量がO(n log n)なリーダー選出アルゴリズム(双方向リング用)

4.3.1 文脈と原則

文脈

この節では双方向リングを扱う:

• 前節は単方向リングだった
• left[i]とright[i]は、それぞれp[i]の左右の隣人を表す
• 左右の概念はグローバル:
  • メッセージが右(あるいは左)方向で転送され続ければ、いずれリングを一周する

原則

アイディア:

• プロセスは非同期ラウンドを実行する
• 各プロセスは各ラウンドrで左右の2^rだけ離れたプロセスと競争する:
  • プロセスIDが大きい方が勝者
  • 勝者は次のラウンドに進む:
    • ラウンドが進むたびに、競争者は(少なくとも)半分になっていく
    • 最後に一人残ったプロセスがリーダーとなる
• 図4.4、図4.5

4.3.2 アルゴリズム

図4.6を見ながら説明:

• 簡単のために全てのプロセスは事前にstart()を受け取っているものとする

4.3.3 時間とメッセージの複雑性

メッセージ複雑性

• p[i]をラウンドrでの競争者とする:
  • rでの競合相手は、左右それぞれ2^r以内のプロセス
  • p[i]が競争者でいるということは、
    • 前ラウンドr-1で、左右の2^(r-1)のプロセスには勝っている、ということ
    • => 多くても、2^(r-1) + 1個の連接するプロセスの内の一つのみが、rでの競争者になり得る
• それを踏まえると、以下が成り立つ:
  • 各ラウンドで、最大でceil(n / (2^(r-1) + 1))個のプロセスが競争者になり得る
  • ! r=0,1,2,nの場合の例 (本を参照)
• 一つのプロセス(競争者)で見た場合、各ラウンドで転送されるメッセージの最大数は4 * 2^r:
  • 4: election()とreply()が左右それぞれに送られる
  • 2^r: 単一方向の距離の最大長
• つまり、
  • 一回のラウンドのグラフ内の最大メッセージ転送量:
    • 4 * 2^r * ceil(n / (2^(r-1) + 1))
    • => 4 * 2 * n
    • => 8 * n
  • ラウンドは最大で1 + log2(n)だけあるので、アルゴリズム全体での上界は:
    • 8 * n * (1 + log2(n))
    • => 8 * n + 8 * n * log2(n)
    • => O(n log2 n)

時間複雑性

簡潔性のための仮定:

• n = 2^k
• 全てのプロセスは同時にアルゴリズムを開始するものとする
• 一つのメッセージ転送は、一タイムユニットを消費する

一番高いIDを有するプロセス(= リーダー)を考えると:

• kラウンドまで競争に参加
• 各ラウンドで2 * 2^rタイムユニットを消費する (election()とreply()が、距離分だけ往復する)
• つまり、選出されるまでに最大で2 * (1 + 2^1 + 2^2 + 2^r + ... 2^k)だけの時間が掛かる
• 最善のケースでは:
  • 2 * (2^k + 1) / (2 - 1)が上界
  • => 4 * n - 2
  • => O(n)
  • ! なぜ最初の式になるか:
    • 2^0 + 2^1 + 2^2 + ... + 2^rは、2^(r+1) - 1となる
    • rの上限はk = log2(n)
    • 合わせると、
      • 2 ^ (log2(n) + 1) - 1
      • ! a^(b + c) = a^b * a^c
      • => 2^log2(n) * 2^1 - 1
      • ! 2 ^ log2(n) = n
      • => n * 2 - 1
    • 最後に2を掛けて2 * (n * 2 - 1)
    • => 4 * n - 2
• 最悪のケースもO(n)
  • ! n != 2^kでは無い時の話っぽい
  • 詳しくは演習問題3を参照
• => 時間複雑性はリングのサイズに対して線形

4.4 計算量がO(n log n)な選出アルゴリズム(単方向リング用)

4.4.1 文脈と原則

文脈

この節では(再び)単方向リングを扱う:

• チャンネルはFIFO
• p[i]は、自分の識別子とそれがユニークであることのみを知っている
  • プロセス数nは知らない

原則

前節と同様に各プロセスは、ラウンドを実行する。

論理的な構造も前節とほぼ同様で、各ラウンドで左右それぞれの2^rの隣接プロセスと競争する:

• ラウンド数の上限も同様で、1 + ceil(log2(n))

ただし、単方向リングなので、後方に位置する隣人(競争者)の情報を取得する方法に工夫がある。

具体的には、

• 前提: p[h] <- p[i] <- p[j]、と並んでいるものとする (図4.7)
• 目的: p[i]が左右の隣接(競争者)プロセスに比べて、高いIDを持っているかを知りたい (持っているなら競争に勝つ)
• 問題点: p[i]はp[h]のIDを、定数時間で知ることができない
• ではどうするか？
  • p[h]は、p[i]とp[j]の両方のIDを定数時間で取得可能
  • => p[h]がp[i]の代わりに、p[i]が左右のプロセスよりも高いIDを持っているかを判定してあげれば良い
    • つまり各プロセスは、二つ分の前方のプロセスのIDを受信し、一つ前のプロセスの代わって、勝敗判定を行う
    • 勝っているなら、次のラウンドに進む (そこでは、一つ前にプロセスの代理者として、振る舞う)

ラウンドが進むと、前回に敗北したプロセスは勝負には参加しなくなり、メッセージの転送のみを担うようになる:

• 図4.8:
  • 実線がr=0での競争者プロセス群の(論理的な)位置関係
  • 点線がr=1での競争者プロセス群の(論理的な)位置関係
    • r=0で負けたプロセスが間引かれている

自分もIDを持つメッセージを受信したら(メッセージが一周したら)、リーダー選出が完了するのは、これまでと同様。

4.4.2 アルゴリズム

図4.6を見ながら説明:

• 簡単のために全てのプロセスは事前にstart()を受け取っているものとする

4.4.3 議論: メッセージ複雑性とFIFOチャンネル

! 時間複雑性は、4.2節と同じ話になるので省略されている？ (2n - 1 => O(n))

メッセージ複雑性

最後を除いた各ラウンドで、

• 各プロセスは二つのメッセージを送信する
  • election(1,-)とelection(2,-)
  • 最後のラウンドではelection(1, -)のみ
• ラウンド数は最大でlog2(n) + 1
• => 2 * n * log(n) + nが全体の上限

チャンネルの種類

チャンネルはFIFO:

• 各プロセスはelection(1,-)の後にelection(2,-)を受け取ることが分かっている
  • 1と2の情報は冗長
  • プロセスIDだけ分かれば十分
  • => 最低限n個の異なるelection()があれば良い

4.5 二つの特別なケース

任意のネットワーク上でのリーダー選出

一つの方法として、一章で取り上げたネットワーク探索アルゴリズムが利用可能:

• 1. 各プロセスp[i]は、id[i]をタグとして持たせて、探索(メッセージの転送)を開始する
• 2. 各プロセスは、受信したメッセージが、これまで既知の最大IDよりも大きい場合にのみ、次に転送する
• 3. グラフ全体の探索を完了できるのは、最大IDを持つプロセス(のメッセージ)のみ
• => そのプロセスがリーダーとなる

インデックスが識別子の場合

プロセスID(識別子)がインデックスと一致し、かつ全体のプロセス数nが知られている場合、選出は容易:

• 特定のインデックスのプロセスをリーダーにすると決めておけば良いだけ

欠点は、同じプロセスが常に選出されること (! 最大IDを使う場合も同様では？)。

簡単な解決策はある:

• 乱数を使う
• 図4.10:
  • 1. 各プロセスがn以内の数値を無作為に選択する
  • 2. 他のプロセスにブロードキャスト
  • 3. 各プロセスは受け取った全ての数値を合計してn+1のmoduloを取る
  • => そのインデックスを持つプロセスがリーダー
• コスト:
  • メッセージ数: O(n^2)
  • 所要時間: O(1)

4.6 要約

• リング上でのリーダー選出アルゴリズムに焦点を当てた
• 最初は、無名ネットワーク上で選出が行えないことを証明
• 次は、双方向と単方向のリングのそれぞれでO(n log n)でリーダーを選出可能なことを示した
  • このオーダーは最適(optimal) (! optimalであることの証明は本文中になかった?)
• => 双方向か単方向かは、(直感に反して)選出アルゴリズムのオーダーには影響がない

4.7 解題

省略

4.8 演習問題

省略