sile/damps-01.md

## damps-01.md

      
    Raw
  

              damps-01.md
            
          
    第一部 分散グラフアルゴリズム

第一部は分散グラフアルゴリズムを扱う:

分散システムをグラフと見立てる

頂点はプロセス(ノード)に対応
辺は通信チャンネルに対応


五章構成:

一章: 基礎定義とネットワーク探索
二章: クラシカルなグラフ問題を分散アルゴリズムで解く
三章: プロセスグラフ上でのグローバル関数を計算するための汎用的な技法
四章: リングネットワーク上でのリーダ選出問題
五章: ネットワーク上を航行するモバイルオブジェクト

目的:

分散グラフアルゴリズムの提示 (分散アプリケーションで利用可能)
読者に__分散__の感覚を掴んでもらう

逐次アルゴリズムと分散アルゴリズムの比較時に役立つ


第一章 基本定義およびネットワーク探索アルゴリズム

要旨:

分散アルゴリズムに関連する基礎定義の導入
分散システムをグラフに見立てる

頂点=プロセス、辺=通信チャンネル
グラフ探索用の分散アルゴリズムを提示

並列探索、幅優先探索、深さ優先探索
スパニングツリーおよびリングの構築
ブロードキャストとコンバージキャスト


分散グラフ探索手法は逐次版のそれとは異なる

分散環境では、一つの種類の探索が複数の方法(アルゴリズム)で実現可能
それぞれが時間計算量(time-complexity)とメッセージ複雑性(message-complexity)の間のトレードオフを有する


1.1 分散アルゴリズム

各種用語定義とこの本が想定する分散環境について
1.1.1 定義

プロセス: Processes

プロセス:

分散システム上での計算単位(computing unit)
プロセス群が協調して、共通の目標を達成する

協調および共通目標 => プロセス同士は何らかの手段で情報を交換する必要がある


プロセスの集合は静的:

システムを構成する__n__個のプロセスはΠ ={p(1),...,p(n)}と表記

! 下付き文字がgistで表現しにくいため関数表記にしています


各p(1)は個々のプロセスを示す

各プロセスは逐次実行:

プロセス内では一度に最大一つの処理(ステップ)が実行される

プロセス添字と識別子:

iはプロセスの添字

外部の観測者がプロセス群を識別するために利用可能


それぞれのプロセスp(i)は、識別子id(i)を有する

プロセスp(i)は自分の識別子id(i)を知っている
ほとんどのケースではid(i) = i


通信媒体: Communication Medium

チャンネル:

プロセス同士は チャンネル を通してメッセージを送受信することで通信する

チャンネルへの想定:

信頼できるものである(reliable)

メッセージの生成、修正、複製、がない


容量無制限
FIFO or 順番保証なし (アルゴリズム毎に明記)
双方向 or 単方向 (基本は前者)

隣人(neighbor):

各プロセスp(i)は隣人の集合を有する

neighbors(i)と表記


集合の値は状況に応じて異なる:

"自分と接続しているプロセス群の識別子" or
"自分に接続しているプロセス群と繋がるチャンネル群のローカルな識別子"


構造: Structural View

分散システムは無向グラフとして表現可能:

G = (Π, C)

Πはプロセス集合(上述) - 頂点群
Cはチャンネル集合 - 辺群


三つの種類のグラフが特に興味深い(Fig. 1.1):

リング、ツリー、クリーク

分散アルゴリズム: Distributed Algorithm

分散アルゴリズム:

n個のオートマトンの集積
一つのオートマトンは逐次ステップ列を記述し、それは対応する一つのプロセスによって実行される
チューリングマシンのパワーに加えて、二つの通信操作によってオートマトンは強化される

send() and recv()


同期アルゴリズム: Synchronous Algorithm

分散同期アルゴリズム:

同期分散システム上で実行されるアルゴリズム
システムの進捗は外部のグローバルクロックによって管理される

グローバルクロックの値に対応した ラウンド が存在
プロセス群は ラウンド列 に合わせて処理を実行する


単一ラウンド内でのプロセスの処理:

各隣人に対して最大一つのメッセージを送信可能
ラウンドr内で送信されたメッセージは、全て同じラウンドr内で受信され処理される

同期システムの基本的な特徴


空間/時間ダイアグラム: Space/time Diagram

分散実行は 空間/時間ダイアグラム によって視覚的に表現可能:

各逐次実行は左から右への矢印によって表現
メッセージは、送信プロセスから受信プロセスへの矢印によって表現

この概念は六章でより正確に示される


図1.2の左側は同期実行の例

縦線は各ラウンドを区切っている


非同期アルゴリズム: Asynchronous Algorithm

分散非同期アルゴリズム:

非同期分散システム上で実行されるようにデザインされたアルゴリズム
非同期分散システム:

外部時間の概念がない
そのため、タイムフリーシステム、と呼ばれることがある


非同期アルゴリズムにおけるプロセスの進捗:

自分の処理と受信メッセージによって保証される:


プロセスがメッセージを受信


アルゴリズムに従いメッセージを処理


もしかしたら隣人にメッセージを送るかも


一つのプロセスが一度に処理するメッセージは一つ:

あるメッセージの処理は、別のメッセージの到着によって割り込みされない

受信メッセージはまずキュー(入力バッファ)に格納される
キューの前方から順に取り出され、処理されていく


図1.2の右側は非同期実行の例

非FIFOチャンネル: p(1) => p(2)のメッセージ到着順が逆転
同期実行の方がより構造化されているのが見てとれる


プロセスの初期知識: Initial Knowledge of a Process

同期/非同期システム上での問題を解く際に、あるプロセスは以下の二つによって特徴付けられる:

入力パラメータ群 (解くべき問題に関連)
環境に対する 初期知識

自分の識別子、プロセスの総数、隣人の識別子、通信グラフの構造、etc


例: プロセスp(i)が最初に知っていること

単方向リング上にいる
メッセージを受信可能な左の隣人がいる
メッセージを送信可能な右の隣人がいる
自分の識別子はid(i)
全プロセスの識別子はユニーク、かつ
識別子群は完全に順序付け可能

この初期知識では、合計プロセス数をあらかじめ知っているプロセスは存在しない。
それを知るためにはプロセス間で情報を交換する必要がある。
1.1.2 導入例: 通信グラフを学習する

非同期アルゴリズムの簡単な例:

各プロセスが自分が参加している通信グラフを学習する
前提:

チャンネルは双方向
通信グラフは接続している (任意の二頂点をつなぐパスが存在する)


初期知識

各プロセスが知っていること:

プロセスp(i)の識別子はid(i)
隣人群とその識別子
<id(i), id(j)>で、p(i)とp(j)の間のチャンネルを表す

双方向なので<id(j), id(i)>と等しい


知らないこと:

プロセス総数

転送/破棄原則: The Forward/Discard Principle

アルゴリズムが依っている原則はシンプル:

各プロセスは、最初に自分のグラフ上の位置を隣人に送信する

位置は(id(i), neighbors(i))で表現される


次に、上のメッセージを受け取ったプロセスp(k)は、

一回目(同一メッセージの受信が):

自分のローカルな通信グラフ表現を更新

p(k)はp(i)のグラフ上での位置を把握する
i.e. p(i)の識別子がid(i)であることと、隣人がneighbors(i)であること、を知る


受け取ったメッセージを(送信元を除いた)全ての隣人に転送する

"初めてなら転送する"原則


二回目以降:

メッセージを破棄する
"初めてではないなら廃棄する"原則


通信グラフのローカル表現

グラフは各プロセスp(i)内で、以下のローカル変数によって表現される:

proc_known(i):

p(i)によって知られているプロセスの集合
初期値は{id(i)}


channels_known(i):

p(i)によって知られているチャンネルの集合
初期値は{<id(i),id(j)> such that id(j) ∈ neighbors(i)}


メッセージ(id(j), neighbors(j))の受信後は、以下のそれぞれが集合に追加される

プロセスid(j)
チャンネル群{<id(j),id(k)> such that id(k) ∈ neighbors(j)}


これらに加えて、各プロセスはアルゴリズムを開始しているかどうかを示すpart(i)という真偽値変数を保持する(初期値はfalse)。
内部メッセージ 対 外部メッセージ

プロセスは外部メッセージSTART()か内部メッセージPOSITOIN()の受信後にアルゴリズムを開始する:

内部メッセージは、アルゴリズムによって生成される
外部メッセージは、外側から送られてくるもの

アルゴリズムの起動に使用
最低一プロセスは外部プロセスを受け取る必要がある


アルゴリズム: 転送/破棄

図1.3を見ながら説明:

アルゴリズムの開始
自分の位置の送信
転送と破棄

アルゴリズム: 停止(Termination)

グラフの構造の把握:

通信グラフは接続している
START()やPOSITION()を受け取ったプロセスは自分の位置情報を隣人に送る

隣人はそれを中継する


=> 最終的には全プロセスが、他のプロセスの位置情報を把握し、通信グラフの構造を把握することが可能

さらに、

(a) プロセス数nには上限がある
(b) p(i)は(id(i), neighbors(i))を送り始める唯一のプロセス
(c) 任意のプロセスp(j)は、bのメッセージを一度だけ転送する
=> よって、一定時間経過後に、メッセージ送信は行われなくなる (このアルゴリズムは停止する)

重要な問いは、各プロセスがどうやって停止したことを(ローカルに)知るか:

13行目
通信グラフ全体を把握したタイミングで停止可能

辺の集合に対して、未知の頂点がなければ良い


適切なローカルデータ構造(proc_known(i)とchannels_known(i))を選択したお陰で、停止判定が簡潔になっていて良いね

コスト

定義:

n: プロセス総数
e: チャンネル総数
D: 通信グラフの直径 (二頂点間の最短パス長の最大値)

直径は通信グラフの"幅"を図るためのグローバルな概念


d: 通信グラフの最大次数(degree)

d = max({|neighbors(i)| 1=< i =< n})


b: 識別子id(i)のエンコードに必要なビット数

メッセージ複雑性:

任意のチャンネルに対して、メッセージ(id(i), -)は、最低一回、最大二回(各方向につき一回)送られる

メッセージ複雑性の上限は2ne


時間計算量:

前提:

各メッセージ送受信は一単位を消費
ローカル処理のコストは0


最悪のケース:

単一のプロセスp(k)がstart()を受け取り、かつ
p(k)からD離れたp(l)が存在する
このケースで、

メッセージ(id(k), _)がp(l)に届くまでは、D時間を要する
時間計算量の上限は2D


メッセージ情報量:

一つのメッセージに必要なビット数はb(d+1)

最初にチャンネル群がローカル名しか持っていない場合

以下のケースを考える:

プロセスp(i)は、c(i)個の隣人を有する
各隣人とはc(i)個のpoint-to-pointのチャンネルで接続している

チャンネルはchannel(i)[1..c(i)]と表記される


プロセスp(i)が最初にchannel(i)[1..c(i)]しか知っていない場合でも、簡単にneigbhors(i)は計算可能

neigbhors(i)は隣人プロセス群の識別子の集合


計算方法:

以下を準備的な通信フェーズとして実行する


channel(i)[x] (1 =< x= <c(i) )にメッセージid(i)を送る


返信を待機


channel(i)[x]でid(id(k))メッセージを受け取ったら、p(i)はchannel(i)[x] => id(k)と紐付けることができる


システム全体がスコープな対応付け


ポート名


各チャンネルchannel(i)[x]がローカル名で定義される時、添字xは ポート と呼ばれることがある
つまりプロセスp(i)は、c(i)個の通信ポートを保持する

1.2 並列探索: ブロードキャストとコンバージキャスト

前提:

プロセスp(i)の識別子はi
プロセス総数nを知っているプロセスは存在しない
p(a)は、特別な役割を持っているプロセスを示すために使用する

ex. ツリーのルート、ブロードキャストの送信元


全てのプロセスは接続している (任意の二点をつなぐパスが存在する)

1.2.1 ブロードキャストとコンバージキャスト

ブロードキャストとコンバージキャストは、分散計算で良く遭遇する問題:

ブロードキャスト問題:

一対多通信問題
p(a)が他の全てのプロセスにメッセージを散布する
亜種として、サブセットのプロセス群が対象となるマルチキャスト問題がある


コンバージキャスト問題:

多対一通信問題
各プロセスp(j)が情報v(j)を、ある一つのプロセスp(a)に送信する
集まった情報[v(1),..,v(n)]は、何らかの関数f()によって計算される


ブロードキャストとコンバージキャストは、対になる通信操作と見ることが可能:

良く有る使われ方: p(a)がクエリをブロードキャストして、結果群をコンバージキャストで受け取り、何らかの計算を行う

1.2.2 フローディングアルゴリズム

フローディングアルゴリズム:

ブロードキャストを実装する簡単な方法
図1.4:

アルゴリズム的には「初めての受信なら隣人にも転送する」といっただけのもの
簡単のためにp(a)は最初に自分自身にGO(data)を送信するものとする
各メッセージはsn(a)というシーケンス番号によって識別可能なものとする

プロセス識別子もメッセージに載せるようにすれば、(p(a)以外の)任意のプロセスが同時にブロードキャスト可能


メッセージが(最終的に)全プロセスに伝播するのは自明


1.2.3 ルートスパニング木に基づいたブロードキャスト/コンバージキャスト

前節の実装は非効率:

最大2e - |neighbors(a)|メッセージを使用する (eはチャンネル総数)
p(a)をルートにしたスパニング木を使うのが、簡単な改善策

根付きスパニング木: Rooted Spanning Tree

p(a)をルート(根)としたスパニング木:

図1.5が分かりやすい
グラフの頂点(processes)は変わらず、辺(channels)は部分集合となる
各プロセスは単一の親parent(i)を有する

便宜上、ルートの親は自分自身


子プロセス群はchildren(i)と表記 (空の可能性もある)

アルゴリズム: Algorithms

図1.6: スパニング木を使ったブロードキャストとコンバージキャスト

ブロードキャスト:

子供にメッセージを転送するだけ (図1.4と異なり重複チェックも不要)


コンバージキャスト:

子の値を蓄積しつつ、自分の分を加えて親に送るだけ


! 経路が一意に定まっているのでシンプル (計算量は木の形状次第)
1.2.4 スパニング木を構築する

情報の伝播とフィードバック と呼ばれるシンプルなアルゴリズムを紹介:

ブロードキャストとコンバージキャストを使用
これを用いて(p(a)をルートとする)スパニング木を構築する

! スパニング木は、後続の章でそれなりに使われているので、効率的な構築は結構重要そう
ローカル変数: Local Variables


値が既知の変数:

neigbhors(a)


実行後に得られる変数:

parent(i)
children(i)


実行に必要な一時変数:

expected_msg(i):

まだback()を送り返してきていないの隣人の数


アルゴリズム: Algorithm

図1.7:

前提(簡単のため):

チャンネルはFIFO


アルゴリズム (細部は図を参照のこと):

開始:


p(a)が外部メッセージstart()を受け取る


子にGOを送信


GO受信:


まだ親が決まっていない場合にのみ処理を進める


expected_msg(i)をセットして、(送信元を除く)隣人全員にGOを送信


最終的には送信元にBACKを返して、子になったかどうかを通知する


BAKC受信:


expected_msg(i)をデクリメント


送信元が子になるならchildren(i)に追加


全隣人から応答を受け取ったら、親にBACKを送る


もしルートなら、ここで処理(木の構築)が完了


! val_set(i)変数は過剰では? (集合ではなく、子となるかどうかを示すためのboolean値で十分そう)
! GO(data)のdataも同様 (中途半端に汎用化している感がある)
コスト: Cost

メッセージ量:

go()にはback()が対応
go()はチャンネルにつき二個(各方向で一個ずつ)送信される

=> 4eが必要なメッセージ総数
! 本の4(e-(n-1))と2(2e-n+1)の対応付けが不明 (両者が等しいと言っているように見えるが...?)


木の構築後は2(n-1)個のメッセージでブロードキャスト/コンバージキャストが可能

時間計算量:

仮定: メッセージ送信は1時間ユニットを消費、ローカル計算コストは0
構築時の計算量は2D (Dはグラフの直径)
構築後のブロードキャスト/コンバージキャストの計算量は2D(a)

D(a)は、p(a)から他のプロセスへの距離で最も長いもの


例: An Example

図1.8:

左: 基となる通信グラフ
右: スパニング木

図1.9:

図1.8の木を構築するための実行例
図1.7の説明通りなので細部は省略

実行の括弧構造について: On the Parenthesized Structure of the Execution

注意点とか特徴とか:

構築される木の構造はgo()メッセージの速度に依存する:

同じアルゴリズムの別の実行では、図1.8と異なるものが出来得る


go()とback()は括弧対応と見做せる (前者が開き括弧で、後者が閉じ括弧)

アルゴリズム全体のメッセージフローは、ネストした括弧群


非FIFOチャンネルの場合: The Case of Non-FIFO Channels

非FIFOでも上手く行く:

ex. 図1.9でgo(1,2)()がback(1,2)()の後に届いても大丈夫
ただし、これまでのように全てのBACKを受け取ったことで、アルゴリズムをローカルで終了させることはできなくなる (行16)

全ての隣人からのGOを受け取ったこともチェックする必要がある


プロセス毎のスパニング木: A Spanning Tree per Process


図1.7のアルゴリズムは、n個の木を構築するために汎用化可能

効率的なブロードキャスト/コンバージキャストを行いたいプロセスp(i)は、対応する専用のスパニング木が必要


以下の二つの変更を行う:

各変数の次元を一つ深くして、ルートプロセス毎に独立した値を保持可能にする
送信メッセージに、ルートプロセスの識別子を載せる


一つのスパニング木のための並列開始者: Concurrent Initiators for a Single Spanning Tree

図1.7は、複数プロセスが並列してアルゴリズムを開始可能なように、用意に修正できる:

構築されるスパニング木は一つ
max_id(i)という追加のローカル変数が必要

初期値は0
最終的には、(start()を受け取ったプロセス群の中で)一番大きなプロセス添字の値が、格納される

その値を持つプロセスが、木のルートとなる


アルゴリズム:


start()を受け取った時にmax_id(i) == 0ならgo()に自分の添字を載せて隣人に送る


2-a. 隣人は、その値が自分のmax_id(i)よりも小さいなら、メッセージを破棄する (! BACK応答は返す?)
2-b. 大きいならmax_id(i)の値を更新して処理を続ける


! start()を(同時に)受け取ったノード間に序列をつけることで、チャンネルの循環が生じることを防げる
1.3 幅優先スパニング木

この節では__幅優先木__の構築方法を紹介する:

用語:

距離(distance): 二つのプロセスをつなぐ最短パスの長さ


幅優先木:

ルートと他プロセスの距離が、もともとの通信グラフ上でのそれと等しい木
例: 図1.10

上記制約さえ満たしていれば良いので、木の形は複数あり得る


図1.7のアルゴリズムでは、幅優先木を構築しない(するとは限らない)
幅優先木を構築するための二つのアルゴリズムを取り上げる:

両方とも反復アルゴリズムに基づく
中央制御の要不要が異なる (最初のものは不要、二番目のものは必要)


1.3.1 中央制御無しに構築された幅優先スパニング木

アルゴリズムの原則: Principle of the Algorithm

特徴:

通信グラフの並列探索に基づいている
基本部分は図1.7の簡易アルゴリズムと同様

forward/discard原則に基づいたスパニング木の構築
ローカルの距離近似値が更新された場合に再計算は行われるので、より重い


ローカル変数:

前節と同様: parent(i), children(i), expected_msg(i)
新規分:

level(i):

ルートからの距離の近似値を表す
go()メッセージは、送信元プロセスの現在のレベルの値も運ぶようになった

go(d)と表記: dはレベル(距離=distance)の値


p(i)がgo(d)メッセージを受信した際の挙動:

基本的に図1.7と同様:

送信元を親に設定して、メッセージを転送する
ただし、その際にlevel(i)の値をd+1に設定し、転送メッセージもgo(d+1)にする


より短い距離が見つかった場合は、更新する:

level(i) > d+1の場合
parent(i)とlevel(i)の更新、および、go(d+1)の転送、をやり直す
ここが図1.7に比べて(計算量的に)余剰の処理


アルゴリズムの記述: Description of the Algorithm

図1.11:

大枠は図1.7と同じ
主要な変更点:

行9~17の距離(近似値)の更新:

この更新により、最小値(実際の距離)へと収束していく
内部でやっていること的には、行3~8と同様


行19での古いBACKメッセージの破棄

level(i)更新以前に送ったgo()への応答はもう不要なので無視する


終端: Termination


ルートは、全ての隣人からBACKを受信したらアルゴリズムが終端したと判定可能
非ルートはそうはいかない:

全隣人からBACKを受信しても、その後により小さなレベルを含むGOを受け取る可能性が残る
各プロセスの知識は、ローカルなので事前に、どのタイミングで変数群が最終値に収束したかを知ることは不可能


でも各プロセスもアルゴリズムの終端を知りたい場合は？

ルートに、終端検出後に、その旨をブロードキャストして貰う


簡単な例: A Simple Example

例: 図1.12

左: 通信グラフ
右: 構築された幅優先スパニング木 (スター型)
真ん中: 最悪実行時のメッセージの流れ

i < j となるp(i)からp(j)へのGOメッセージの表記j
近似距離が長くなるメッセージが先に届いてしまっているため、無駄な再転送が必要となっている


コスト: Cost

時間計算量:

Dは通信グラフの直径 (再掲)
木の構築に掛かる時間はO(D)

最悪時はD = nとなるので、最悪計算量もO(n)となる


メッセージ複雑性:

レベルの最大値はD (log2(D) bitsで表現可能)
BACKとGOの識別に、1bitのタグが必要
BACKメッセージには、bool値(1bit)とd =< Dが載せられる

メッセージサイズ(複雑性)は2 + log2(D) bitsあれば良い


メッセージ送信数:

最悪ケースとして、通信グラフはフルコネクトとする
ルートからの距離がdのプロセスは、最大d回までlevel(i)を更新する
level(i)の更新時には、n-2のプロセスにGOを送信する (自分と親プロセス以外の全て)

ルートの場合はn-1


GOには対応するBACKが存在する
式(erlang): (n - 1) + (n - 2) * lists:sum([i || i <- lists:seq(1, n-1)])

= (n - 1) * (n*n - 2*n + 2) / 2
=> O(n^3)
! ベースとなった図1.7はO(n^2)なのでだいぶ重くなっている


1.3.2 中央制御有りで構築された幅優先スパニング木

続いて中央制御有り版の実装を紹介:

各プロセスはローカルにアルゴリズムの終端を検出可能
時間計算量とメッセージ送信数は、どちらもO(n^2)

前者はO(n)から劣化、後者はO(n^3)から改善


基礎原則: Underlying Principle

p(a)によって進捗が管理される分散反復が基礎:

__波(wave)__と呼ぶ
図1.13:

最初の反復では(p(a)からの)距離1までのプロセスが対象
次の反復は距離2までのプロセスが対象
その次は3、その次は4、...、を距離D(a)まで繰り返す


各プロセスは初めてのGO(d)受信時に、dを自分の距離として設定可能
d+1番目の波の際には、距離dまでの木の構造は確定しているので、GOの伝送にそのスパンニング木を利用可能

送信メッセージを減らすことができる


アルゴリズム: ローカル変数

これまでと共通:

neighbors(i)
parent(i)
children(i)

このアルゴリズム固有:

distance(i):

p(a)からの距離確定時に、一度だけ書き込まれる


to_send(i):

次の波で、ルートからのメッセージの転送先となるプロセス群 (隣人のサブセット)
ここには自分よりも距離が遠いであろうプロセスのみが含まれる


waiting_from(i):

GOを送ったが、BACKをまだ返送してきていないプロセス群


アルゴリズム: p(a)による起動

起動処理:

前提: 最低二つのプロセスがいる
p(a)が図1.14のコードを最初に実行して、アルゴリズムを始める

各種ローカル変数の初期化
隣人にgo(d=0)を送る

dは送信元プロセスのルートからの距離


go()およびback()の受信時の処理:

図1.15
コードをベースに説明。以下はメモ書き。
GO(d)受信時:

初めての受信(= 親が未設定)なら、各種変数初期化 (自分の距離はd+1)

隣人がいないならBACK(stop)を親に返す


二回目以降は、親からのメッセージならto_send(i)に転送する(距離は自分のものに更新)


BACK(resp)受信時:

必要(resp ∈ {continue,stop})ならchlidren(i)に追加
今後送る必要がないなら、to_send(i)から除去
to_send(i)が空なら、自プロセスの処理(アルゴリズムの実行)は完了

ルートならアルゴリズム全体が終了
それ以外ならBACK(stop)を親に返して、以降の反復からは離脱する


空ではないなら、

ルートなら次の反復を始める
それ以外ならBACK(continue)を返送する


分散同期について: On Distributed Synchronization

このアルゴリズムは二種類の同期を提示している:

(1) グローバルな同期:

波のシーケンスを制御するルートプロセスによるもの(行20~21)


(2) 各プロセスにローカルな同期:

親プロセスへのback()メッセージの返送によるもの(行3,16,22)


ローカル終端 vs グローバル終端: Local Versus Global Termination

前節のアルゴリズム(図1.11)とは、異なり各プロセスがアルゴリズムの終端をローカルに検出可能:

to_send(i)が空になったら、もう各プロセスはやることがないので、離脱可能
自分の終端に達したらback(stop)を親に送る (行3,16)
ただし、各プロセスのローカルな終端はアルゴリズム全体の終端を意味しない

それを検出できるのはルートプロセスのみ (行15)


コスト: Cost

メッセージ送信数:

go()には対応するback()が存在する
eは通信グラフのチャンネル数
構築された木に属していないチャンネルでは、最大二つのgo()が交換される

最悪は2e - (n-1)


木に属しているチャンネルでは:

n-1のチャンネルが存在
波の数の最大はn (通信グラフの形が完全に直列になっている場合)
最悪はO(n^2)


eの上界はO(n^2)
上記を考慮すると、やりとりされるメッセージ数の上限はO(n^2)となる

時間計算量:

アルゴリズムの流れ:

最初の波は、二単位時間、を消費 (ルートの隣人へのgo()送信とback()の返送)
次の波は、四単位時間、を消費（ルートの隣人の隣人への...)

つまり、波の回数 * 2、を要する


波は最大でD回発生する (Dは通信グラフの直径)
時間計算量は 2(1 + 2 + ... + D) => O(D^2) となる

最悪のケースではD = nなのでO(n^2)


中央制御無し版とのトレードオフ:

制御なし:

送信数: O(n^3)
時間: O(n)


制御あり:

送信数: O(n^2)
時間: O(n^2)


1.4 深さ優先探索

次は、分散深さ優先ネットワーク探索、を見ていく:

p(a)から始める
一度に訪問するプロセスは一つ
初めにシンプルなアルゴリズムを紹介し、その後に二つの改良を施す
最後は、任意の接続通信グラフから、論理リングを構築する分散アルゴリズムを示す

1.4.1 単純なアルゴリズム

アルゴリズムの説明: Description of the Algorithm

図1.16:

コードをもとに説明。以下はメモ書き。
start()受信時:

ルートプロセスのみが受信し、これによりアルゴリズムの実行が始まる
各種ローカル変数初期化
隣人の中の一つにgo()を送信


go()受信時:

初めての受信(= 親が未設定)なら処理を続ける

探索すべきノード(隣人)が無いならback(yes)を送信元(親)に返す
(ローカルな知識で)未探索な隣人がいるなら、その中の一つにgo()を送信


back(resp)受信時:

go()への応答を受信
resp=yesなら子に追加
送信元を探索済み集合(vidited(i))に追加

全ての隣人を探索したなら、ローカルなアルゴリズムの実行は完了

ルートならアルゴリズム全体が終了、それ以外なら親プロセスにback(yes)を通知


まだ(ローカルな知識で)未探索な隣人がいるなら、その中の一つにgo()を送信


構築された木について: On the Tree That Is Built

構築される木の形について:

メッセージの到達時間には依存しない
隣人へのgo()の送信順(選択順)に依存する (行7,18)

コスト: Cost

メッセージ送信数:

go()には対応するback()がある
go()は最大で、全てのチャンネルの各方向につき、一度だけ送信される

つまり最大2e = O(e)
チャンネル数は最大でn^2なので、送信数の最大はO(n^2)となる


メッセージ複雑性:

go()とback()の識別に1bit必要
back()は真偽値respを運ぶので、さらに1bit必要
最大で2bitあれば良い

時間計算量:

go()は、各チャンネル上を一度に一つずつ巡回していく
つまり要する時間の上界はO(e)であり、最悪ケースでO(n^2)となる

基本アルゴリズムの簡単な改良: An Easy Improvement of the Basic Algorithm

時間計算量を改良するための簡単な方法:

ローカルな情報交換フェーズを追加する

go()メッセージ受信時に実行する
ローカル: go()の受信メッセージとその隣人だけでやり取りが完結する


O(n)の時間計算量が達成可能

各プロセスはgo()を一回しか受け取らなくなる


追加の情報交換フェーズの流れ:


go()を受信


隣人にvisited()を(並列に)送る


全てからknown()を受け取るまで待機


visited()を受信したプロセスはp(j)は、visited(j)に送信元を追加し、known()を返送する


! go()の送信元プロセスにはvisited()を送る必要はない


以降は以前と同様: 未訪問の隣人へgo()を逐次送信


ただしback()にrespは不要となった (事前に未訪問であることが判明しているため)


コストの変化:

メッセージ送信数:

n-1のgo()およびback()を送信
2e-(n-1)のvisited()およびknown()を送信
=> O(e) (以前と変わらず)


時間計算量:

go()およびback()で2(n-1)を消費
visited()およびknown()は隣人に並列して発行可能なので2n

ただし隣人が一つのプロセスでは、そもそもこのフェーズが不要
n(1)を、隣人が一つのプロセスを表すとすると、2n(1)が減算される


=> 2(n-1)+2n-2n(1) => O(n)


1.4.2 適用: ロジカルリングの構築

ローカルアルゴリズムの概念: The Notion of a Local Algorithm

初版と改良版のアルゴリズムの両方は、以下の意味で__ローカル__であった:

(a) 各プロセスの初期知識は、以下の三つのみ:

自分の識別子
自分の隣人
各識別子がユニークであること


(b) 任意の二つのプロセス間で交換される情報(メッセージ)のサイズには上限がある

基本アルゴリズムの別の改良: Another Improvement of the Basic Depth-First Traversal Algorithm

ローカルではないが、メッセージと時間の計算量がO(n)、のアルゴリズムを紹介する:

前節のvisited()とknown()を使ったローカルな同期を、グローバルな制御情報を用いたものに置き換える
具体的にはgo()とback()に、既に訪問済みのプロセス群の情報(visited)の載せるようにする

! 逐次版での循環があるグラフにおける深さ優先探索の実現方法に近そう


実装: 図1.17

上述の通りvisitedをプロセス間で持ち回している


コスト:

時間計算量:

go()およびback()は、構築されるスパニング木上の各チャンネル(n-1だけ存在)を一度だけ通る
各メッセージは直列的にやり取りされる
=> 2(n-1)


メッセージサイズ:

このアルゴリズムはローカルではなくvisitedをメッセージで伝送する必要がある
visitedは、最終的には全てのプロセスの識別子を含むようになる

最大でnlog2(n)bit必要


go()とback()の識別に1bit必要
=> nlog2(n) + 1が最大メッセージサイズ


論理リングに沿ったトークンの巡回: A Token Travelling Along a Logical Ring

トークン:

ネットワークを航行(navigate)するメッセージ
論理単方向リングを使えば簡単に実現可能:

トークンはリング上のプロセスを順々に訪問する
トークンを永遠に専有するプロセスはいないと仮定すると、全てのプロセスにトークンを取得する機会がある


問題は、任意の接続ネットワーク上にどうやって論理リングを構築するか

=> 以降では、その方法(アルゴリズム)を扱う


アルゴリズムで使用するローカル変数:

succ(i):

論理リング上で、次に位置するプロセスの識別子


routing(i)[j]:

p(j)からメッセージを受信した場合の転送先プロセス(の識別子)、が格納される

routing(i)[メッセージ送信元プロセス] = メッセージ転送先プロセス


論理リング上での位置関係に従ってトークンが移動可能なようにするためのルーティングテーブル


図1.18:

上記二つの変数の計算完了後(リング構築後)に、トークンが航行するためのアルゴリズム
次の目的プロセスはsucc(i)から取得
そこに辿り着く(ローカルな)経路はrouting(i)[j]から取得

一回のメッセージ送信で到達できるとは限らない


論理リングを構築するための分散アルゴリズム: A Distributed Algorithm Building a Logical Ring

深さ優先探索を用いた構築方法:

図1.19が実装
図1.17の深さ優先探索のコードがスケルトンになっている

succ(i)およびrouting(j)[j]の計算処理が追加
構築時の探索順を、逆に辿るリングが得られる

図1.20
routing(i)[j]には、深さ優先探索の経路(の逆)を記録
succ(i)には、一つ前に訪問した(新規)プロセスを設定

プロセス群はgo()の到着順に従い、リング上での位置が順序付けられる(total order)


! コードを追いながら軽く説明

コスト: Cost

メッセージ送信数:

go()とback()をそれぞれn-1ずつ
=> 2(n-1)

リング：

構築後はn個の仮想チャンネルができる: vc(1),...,vc(n)
チャンネルvc(x)の長さl(x)は:

1 =< l(x) =< (n-1)
全てのl(x)の合計は2(n-1)


つまり、リングの構築と、構築後にリングが一周するには、どちらも 2(n-1) のメッセージが順々に送信される必要がある

! 逐次的な処理になるため時間計算量も2(n-1)


! 任意のネットワークに対応可能になっているため必ずしも(グローバルな観点から見て)最適なルーティングではないことがある (ex. クリークの場合はsucc(i)に直接送れば良い => それでも O(n) )
注目: Remarks

リング上での位置:

リング上で(論理的に)隣接する二つのプロセスの位置の決定は、構築時の探索順に依存する

次に訪れる隣人をどう決定するか


go()およびback()に、よりたくさんの情報を載せることを許容するなら、リングの長さをxに減らすことが可能

情報: 既に訪問済み(or 未訪問)のネットワークの情報
x ∈ [n...2(n-1)]
xの値は、通信グラフの構造と、探索時の隣人選択方法、依存する


例: An Example

省略 (軽く口頭で、図1.21と表1.1、に触れるくらい)
1.5 要約

この章で取り上げた内容:

分散アルゴリズムの概念の定義
いくつかのネットワーク探索アルゴリズムの紹介:

並列、幅優先、深さ優先


通信グラフ上に、スパニング木やリングを構築する方法の紹介
分散探索技法が、逐次環境でのそれ(sequential counterparts)とは異なることも示した

1.6 解題

省略
1.7 演習問題

省略 (演習問題をやる方針にするなら、次回に対象に含める)