Skip to content

Instantly share code, notes, and snippets.

@sile

sile/damps-01.md

Last active May 1, 2020 19:36
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sile/fdc613955a77ebf46f5a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sile/fdc613955a77ebf46f5a to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sile revised this gist Aug 7, 2015. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -845,6 +845,8 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    #### 例: An Example

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

    1.5 要約
    --------

  2. sile revised this gist Aug 7, 2015. 1 changed file with 22 additions and 0 deletions.
    22 changes: 22 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -819,8 +819,30 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    #### コスト: 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.5 要約
  3. sile revised this gist Aug 7, 2015. 1 changed file with 12 additions and 1 deletion.
    13 changes: 12 additions & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -799,13 +799,24 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    - 論理リング上での位置関係に従ってトークンが移動可能なようにするためのルーティングテーブル

    図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

    #### 注目: Remarks
  4. sile revised this gist Aug 6, 2015. 1 changed file with 29 additions and 9 deletions.
    38 changes: 29 additions & 9 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -545,7 +545,7 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    - `BACK`メッセージには、bool値(1bit)と`d =< D`が載せられる
    - メッセージサイズ(複雑性)は`2 + log2(D) bits`あれば良い

    メッセージ送信量:
    メッセージ送信数:
    - 最悪ケースとして、通信グラフはフルコネクトとする
    - ルートからの距離が`d`のプロセスは、最大`d`回まで`level(i)`を更新する
    - `level(i)`の更新時には、`n-2`のプロセスに`GO`を送信する (自分と親プロセス以外の全て)
    @@ -560,7 +560,7 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    続いて中央制御有り版の実装を紹介:
    - 各プロセスはローカルにアルゴリズムの終端を検出可能
    - 時間計算量とメッセージ送信量は、どちらも`O(n^2)`
    - 時間計算量とメッセージ送信数は、どちらも`O(n^2)`
    - 前者は`O(n)`から劣化、後者は`O(n^3)`から改善

    #### 基礎原則: Underlying Principle
    @@ -635,7 +635,7 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    #### コスト: Cost

    メッセージ送信量:
    メッセージ送信数:
    - `go()`には対応する`back()`が存在する
    - `e`は通信グラフのチャンネル数
    - 構築された木に属していないチャンネルでは、最大二つの`go()`が交換される
    @@ -658,10 +658,10 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    中央制御無し版とのトレードオフ:
    - 制御なし:
    - 送信量: `O(n^3)`
    - 送信数: `O(n^3)`
    - 時間: `O(n)`
    - 制御あり:
    - 送信量: `O(n^2)`
    - 送信数: `O(n^2)`
    - 時間: `O(n^2)`

    1.4 深さ優先探索
    @@ -703,11 +703,11 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    #### コスト: Cost

    メッセージ送信量:
    メッセージ送信数:
    - `go()`には対応する`back()`がある
    - `go()`は最大で、全てのチャンネルの各方向につき、一度だけ送信される
    - つまり`最大2e = O(e)`
    - チャンネル数は最大で`n^2`なので、送信量の最大は`O(n^2)`となる
    - チャンネル数は最大で`n^2`なので、送信数の最大は`O(n^2)`となる

    メッセージ複雑性:
    - `go()`と`back()`の識別に1bit必要
    @@ -737,7 +737,7 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    - ただし`back()`に`resp`は不要となった (事前に未訪問であることが判明しているため)

    コストの変化:
    - メッセージ送信量:
    - メッセージ送信数:
    - `n-1`の`go()`および`back()`を送信
    - `2e-(n-1)`の`visited()`および`known()`を送信
    - => `O(e)` (以前と変わらず)
    @@ -782,7 +782,27 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    #### 論理リングに沿ったトークンの巡回: 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

  5. sile revised this gist Aug 6, 2015. 1 changed file with 21 additions and 0 deletions.
    21 changes: 21 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -761,8 +761,29 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    #### 基本アルゴリズムの別の改良: 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



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

    #### コスト: Cost
  6. sile revised this gist Aug 6, 2015. 1 changed file with 16 additions and 0 deletions.
    16 changes: 16 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -752,10 +752,19 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

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

    初版と改良版のアルゴリズムの両方は、以下の意味で__ローカル__であった:
    - (a) 各プロセスの初期知識は、以下の三つのみ:
    - 自分の識別子
    - 自分の隣人
    - 各識別子がユニークであること
    - (b) 任意の二つのプロセス間で交換される情報(メッセージ)のサイズには上限がある

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

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

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

    #### コスト: Cost

    #### 注目: Remarks
    @@ -765,6 +774,13 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    1.5 要約
    --------

    この章で取り上げた内容:
    - 分散アルゴリズムの概念の定義
    - いくつかのネットワーク探索アルゴリズムの紹介:
    - 並列、幅優先、深さ優先
    - 通信グラフ上に、スパニング木やリングを構築する方法の紹介
    - 分散探索技法が、逐次環境でのそれ(sequential counterparts)とは異なることも示した

    1.6 解題
    --------

  7. sile revised this gist Aug 6, 2015. 1 changed file with 31 additions and 13 deletions.
    44 changes: 31 additions & 13 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -631,7 +631,7 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    - `to_send(i)`が空になったら、もう各プロセスはやることがないので、離脱可能
    - 自分の終端に達したら`back(stop)`を親に送る (行3,16)
    - ただし、各プロセスのローカルな終端はアルゴリズム全体の終端を意味しない
    - それを検出できるのはルートプロセスのみ (図15)
    - それを検出できるのはルートプロセスのみ (行15)

    #### コスト: Cost

    @@ -720,12 +720,40 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

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


    時間計算量を改良するための簡単な方法:
    - ローカルな情報交換フェーズを追加する
    - `go()`メッセージ受信時に実行する
    - ローカル: `go()`の受信メッセージとその隣人だけでやり取りが完結する
    - `O(n)`の時間計算量が達成可能
    - 各プロセスは`go()`を一回しか受け取らなくなる

    追加の情報交換フェーズの流れ:
    - 1. `go()`を受信
    - 2. 隣人に`visited()`を(並列に)送る
    - 全てから`known()`を受け取るまで待機
    - 3. `visited()`を受信したプロセスは`p(j)`は、`visited(j)`に送信元を追加し、`known()`を返送する
    - ! `go()`の送信元プロセスには`visited()`を送る必要はない
    - 4. 以降は以前と同様: 未訪問の隣人へ`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

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

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

    #### コスト: Cost
    @@ -745,14 +773,4 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    1.7 演習問題
    ------------

    ### 1

    ### 2

    ### 3

    ### 4

    ### 5

    ### 6
    省略 (演習問題をやる方針にするなら、次回に対象に含める)
  8. sile revised this gist Aug 6, 2015. 1 changed file with 45 additions and 0 deletions.
    45 changes: 45 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -667,16 +667,61 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    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



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

    #### ローカルアルゴリズムの概念: The Notion of a Local Algorithm
  9. sile revised this gist Aug 6, 2015. 1 changed file with 65 additions and 0 deletions.
    65 changes: 65 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -593,12 +593,77 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    #### アルゴリズム: `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 深さ優先探索
    ---------------

  10. sile revised this gist Aug 5, 2015. 1 changed file with 29 additions and 0 deletions.
    29 changes: 29 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -558,10 +558,39 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    ### 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)`による起動

    #### 分散同期について: On Distributed Synchronization
  11. sile revised this gist Aug 4, 2015. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -452,7 +452,7 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    - 構築されるスパニング木は一つ
    - `max_id(i)`という追加のローカル変数が必要
    - 初期値は`0`
    - 最終的には、一番大きなプロセス添字の値が、格納される
    - 最終的には、(`start()`を受け取ったプロセス群の中で)一番大きなプロセス添字の値が、格納される
    - その値を持つプロセスが、木のルートとなる
    - アルゴリズム:
    - 1. `start()`を受け取った時に`max_id(i) == 0`なら`go()`に自分の添字を載せて隣人に送る
  12. sile revised this gist Aug 4, 2015. 1 changed file with 36 additions and 0 deletions.
    36 changes: 36 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -516,10 +516,46 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    #### 終端: 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 中央制御有りで構築された幅優先スパニング木

    #### 基礎原則: Underlying Principle
  13. sile revised this gist Aug 4, 2015. 1 changed file with 10 additions and 1 deletion.
    11 changes: 10 additions & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -503,7 +503,16 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    - `parent(i)`と`level(i)`の更新、および、`go(d+1)`の転送、をやり直す
    - ここが図1.7に比べて(計算量的に)余剰の処理

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

    図1.11:
    - 大枠は図1.7と同じ
    - 主要な変更点:
    - 行9~17の距離(近似値)の更新:
    - この更新により、最小値(実際の距離)へと収束していく
    - 内部でやっていること的には、行3~8と同様
    - 行19での古い`BACK`メッセージの破棄
    - `level(i)`更新以前に送った`go()`への応答はもう不要なので無視する

    #### 終端: Termination

  14. sile revised this gist Aug 4, 2015. 1 changed file with 24 additions and 1 deletion.
    25 changes: 24 additions & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -472,14 +472,37 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    - 例: 図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

    #### 終端: Termination
  15. sile revised this gist Aug 4, 2015. 1 changed file with 64 additions and 0 deletions.
    64 changes: 64 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -464,17 +464,69 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル
    1.3 幅優先スパニング木
    --------------------

    この節では__幅優先木__の構築方法を紹介する:
    - 用語:
    - __距離(distance)__: 二つのプロセスをつなぐ最短パスの長さ
    - 幅優先木:
    - ルートと他プロセスの距離が、もともとの通信グラフ上でのそれと等しい木
    - 例: 図1.10
    - 上記制約さえ満たしていれば良いので、木の形は複数あり得る
    - 図1.7のアルゴリズムでは、幅優先木を構築しない(するとは限らない)
    - この節では、幅優先木を構築するための二つのアルゴリズムを紹介する
    - 両方とも反復アルゴリズムに基づく
    - 中央制御の要不要が異なる (最初のものは不要、二番目のものは必要)

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

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

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

    #### 終端: Termination

    #### 簡単な例: A Simple Example

    #### コスト: Cost

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

    #### 基礎原則: Underlying Principle

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

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

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

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

    #### コスト: Cost

    1.4 深さ優先探索
    ---------------

    ### 1.4.1 単純なアルゴリズム

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

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

    #### コスト: Cost

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

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

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

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

    #### コスト: Cost

    #### 注目: Remarks

    #### 例: An Example

    1.5 要約
    --------

    @@ -485,3 +537,15 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    1.7 演習問題
    ------------

    ### 1

    ### 2

    ### 3

    ### 4

    ### 5

    ### 6
  16. sile revised this gist Jul 31, 2015. 1 changed file with 4 additions and 5 deletions.
    9 changes: 4 additions & 5 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -450,17 +450,16 @@ __情報の伝播とフィードバック__ と呼ばれるシンプルなアル

    図1.7は、複数プロセスが並列してアルゴリズムを開始可能なように、用意に修正できる:
    - 構築されるスパニング木は一つ
    - 並列度が上がるので、最短で`2`の時間計算量で構築可能 (! おそらく)
    - `max_id(i)`という追加のローカル変数が必要
    - 初期値は`0`
    - 最終的には、一番大きなプロセス添字の値が、格納される
    - その値を持つプロセスが、木のルートとなる
    - アルゴリズム:
    - 1. `start()`を受け取った時に`max_id(1) == 0`なら`go()`に自分の添字を載せて隣人に送る
    - 2-a. 隣人は、その値が自分の`max_id(i)`よりも小さいなら、メッセージを破棄する
    - 2-b. hoge
    - 1. `start()`を受け取った時に`max_id(i) == 0`なら`go()`に自分の添字を載せて隣人に送る
    - 2-a. 隣人は、その値が自分の`max_id(i)`よりも小さいなら、メッセージを破棄する (! `BACK`応答は返す?)
    - 2-b. 大きいなら`max_id(i)`の値を更新して処理を続ける

    TODO
    ! `start()`を(同時に)受け取ったノード間に序列をつけることで、チャンネルの循環が生じることを防げる

    1.3 幅優先スパニング木
    --------------------
  17. sile revised this gist Jul 30, 2015. 1 changed file with 113 additions and 21 deletions.
    134 changes: 113 additions & 21 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -340,35 +340,127 @@

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

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

    TODO
    `p(a)`をルート(根)としたスパニング木:
    - 図1.5が分かりやすい
    - グラフの頂点(processes)は変わらず、辺(channels)は部分集合となる
    - 各プロセスは単一の親`parent(i)`を有する
    - 便宜上、ルートの親は自分自身
    - 子プロセス群は`children(i)`と表記 (空の可能性もある)

    #### アルゴリズム: Algorithms

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

    ### 1.2.4 スパニング木を構築する

    ! スパニング木は、後続の章でそれなりに使われているので、効率的な構築は結構重要

    #### Local Variables
    図1.6: スパニング木を使ったブロードキャストとコンバージキャスト
    - ブロードキャスト:
    - 子供にメッセージを転送するだけ (図1.4と異なり重複チェックも不要)
    - コンバージキャスト:
    - 子の値を蓄積しつつ、自分の分を加えて親に送るだけ

    #### Algorithm
    ! 経路が一意に定まっているのでシンプル (計算量は木の形状次第)

    #### Cost

    #### An Example

    #### On the Parenthesized Structure of the Execution
    ### 1.2.4 スパニング木を構築する

    #### The Case of Non-FIFO Channels
    __情報の伝播とフィードバック__ と呼ばれるシンプルなアルゴリズムを紹介:
    - ブロードキャストとコンバージキャストを使用
    - これを用いて(`p(a)`をルートとする)スパニング木を構築する

    ! スパニング木は、後続の章でそれなりに使われているので、効率的な構築は結構重要そう

    #### ローカル変数: Local Variables

    - 値が既知の変数:
    - `neigbhors(a)`
    - 実行後に得られる変数:
    - `parent(i)`
    - `children(i)`
    - 実行に必要な一時変数:
    - `expected_msg(i)`:
    - まだ`back()`を送り返してきていないの隣人の数

    #### アルゴリズム: Algorithm

    図1.7:
    - 前提(簡単のため):
    - チャンネルはFIFO
    - アルゴリズム (細部は図を参照のこと):
    - 開始:
    - 1. `p(a)`が外部メッセージ`start()`を受け取る
    - 2. 子に`GO`を送信
    - GO受信:
    - 1. まだ親が決まっていない場合にのみ処理を進める
    - 2. `expected_msg(i)`をセットして、(送信元を除く)隣人全員に`GO`を送信
    - 3. 最終的には送信元に`BACK`を返して、子になったかどうかを通知する
    - BAKC受信:
    - 1. `expected_msg(i)`をデクリメント
    - 2. 送信元が子になるなら`children(i)`に追加
    - 3. 全隣人から応答を受け取ったら、親に`BACK`を送る
    - 4. もしルートなら、ここで処理(木の構築)が完了

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

    #### コスト: Cost

    メッセージ量:
    - `go()`には`back()`が対応
    - `go()`はチャンネルにつき二個(各方向で一個ずつ)送信される
    - => `4e`が必要なメッセージ総数
    - ! 本の`4(e-(n-1))`と`2(2e-n+1)`の対応付けが不明 (両者が等しいと言っているように見えるが...?)
    - 木の構築後は`2(n-1)`個のメッセージでブロードキャスト/コンバージキャストが可能

    #### A Spanning Tree per Process
    時間計算量:
    - 仮定: メッセージ送信は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は、複数プロセスが並列してアルゴリズムを開始可能なように、用意に修正できる:
    - 構築されるスパニング木は一つ
    - 並列度が上がるので、最短で`2`の時間計算量で構築可能 (! おそらく)
    - `max_id(i)`という追加のローカル変数が必要
    - 初期値は`0`
    - 最終的には、一番大きなプロセス添字の値が、格納される
    - その値を持つプロセスが、木のルートとなる
    - アルゴリズム:
    - 1. `start()`を受け取った時に`max_id(1) == 0`なら`go()`に自分の添字を載せて隣人に送る
    - 2-a. 隣人は、その値が自分の`max_id(i)`よりも小さいなら、メッセージを破棄する
    - 2-b. hoge

    #### Concurrent Initiators for a Single Spanning Tree
    TODO

    1.3 幅優先スパニング木
    --------------------
  18. sile revised this gist Jul 29, 2015. 1 changed file with 44 additions and 0 deletions.
    44 changes: 44 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -304,6 +304,7 @@
    - プロセス総数`n`を知っているプロセスは存在しない
    - `p(a)`は、特別な役割を持っているプロセスを示すために使用する
    - ex. ツリーのルート、ブロードキャストの送信元
    - 全てのプロセスは接続している (任意の二点をつなぐパスが存在する)

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

    @@ -322,10 +323,53 @@

    ### 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)`をルート(根)としたスパニング木

    TODO

    #### アルゴリズム: Algorithms

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

    ### 1.2.4 スパニング木を構築する

    ! スパニング木は、後続の章でそれなりに使われているので、効率的な構築は結構重要

    #### Local Variables

    #### Algorithm

    #### Cost

    #### An Example

    #### On the Parenthesized Structure of the Execution

    #### The Case of Non-FIFO Channels

    #### A Spanning Tree per Process

    #### Concurrent Initiators for a Single Spanning Tree

    1.3 幅優先スパニング木
    --------------------

  19. sile revised this gist Jul 29, 2015. 1 changed file with 19 additions and 0 deletions.
    19 changes: 19 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -299,8 +299,27 @@
    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.2.3 ルートスパニング木に基づいたブロードキャスト/コンバージキャスト
  20. sile revised this gist Jul 24, 2015. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -290,7 +290,7 @@
    - 2. 返信を待機
    - 3. `channel(i)[x]`で`id(id(k))`メッセージを受け取ったら、`p(i)`は`channel(i)[x] => id(k)`と紐付けることができる
    - システム全体がスコープな対応付け
    -

    #### ポート名

    - 各チャンネル`channel(i)[x]`がローカル名で定義される時、添字`x`は _ポート_ と呼ばれることがある
  21. sile revised this gist Jul 24, 2015. 1 changed file with 14 additions and 0 deletions.
    14 changes: 14 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -277,6 +277,20 @@

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

    以下のケースを考える:
    - プロセス`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)`は隣人プロセス群の識別子の集合

    計算方法:
    - 以下を準備的な通信フェーズとして実行する
    - 1. `channel(i)[x] (1 =< x= <c(i) )`にメッセージ`id(i)`を送る
    - 2. 返信を待機
    - 3. `channel(i)[x]`で`id(id(k))`メッセージを受け取ったら、`p(i)`は`channel(i)[x] => id(k)`と紐付けることができる
    - システム全体がスコープな対応付け
    -
    #### ポート名

    - 各チャンネル`channel(i)[x]`がローカル名で定義される時、添字`x`は _ポート_ と呼ばれることがある
  22. sile revised this gist Jul 24, 2015. 1 changed file with 3 additions and 0 deletions.
    3 changes: 3 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -279,6 +279,9 @@

    #### ポート名

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

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

  23. sile revised this gist Jul 24, 2015. 1 changed file with 46 additions and 1 deletion.
    47 changes: 46 additions & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -226,10 +226,55 @@
    - 自分の位置の送信
    - 転送と破棄

    #### アルゴリズム: 終端
    #### アルゴリズム: 停止(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)`

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

    #### ポート名
  24. sile revised this gist Jul 23, 2015. 1 changed file with 51 additions and 2 deletions.
    53 changes: 51 additions & 2 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -171,16 +171,65 @@

    #### 初期知識

    #### Forward/Discard原則
    各プロセスが知っていること:
    - プロセス`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`)。

    #### 内部メッセージ 対 外部メッセージ

    #### アルゴリズム: Forward/Discard
    プロセスは外部メッセージ`START()`か内部メッセージ`POSITOIN()`の受信後にアルゴリズムを開始する:
    - 内部メッセージは、アルゴリズムによって生成される
    - 外部メッセージは、外側から送られてくるもの
    - アルゴリズムの起動に使用
    - 最低一プロセスは外部プロセスを受け取る必要がある

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

    図1.3を見ながら説明:
    - アルゴリズムの開始
    - 自分の位置の送信
    - 転送と破棄

    #### アルゴリズム: 終端

    #### コスト

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

    #### ポート名
  25. sile revised this gist Jul 23, 2015. 1 changed file with 23 additions and 1 deletion.
    24 changes: 23 additions & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -161,7 +161,29 @@
    この初期知識では、合計プロセス数をあらかじめ知っているプロセスは存在しない。
    それを知るためにはプロセス間で情報を交換する必要がある。

    ### 1.1.2 導入例: コミュニケーショングラフを学習する
    ### 1.1.2 導入例: 通信グラフを学習する

    非同期アルゴリズムの簡単な例:
    - 各プロセスが自分が参加している通信グラフを学習する
    - 前提:
    - チャンネルは双方向
    - 通信グラフは接続している (任意の二頂点をつなぐパスが存在する)

    #### 初期知識

    #### Forward/Discard原則

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

    #### 内部メッセージ 対 外部メッセージ

    #### アルゴリズム: Forward/Discard

    #### アルゴリズム: 終端

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

    #### ポート名

    1.2 並列探索: ブロードキャストとコンバージキャスト
    --------------------------------------------
  26. sile revised this gist Jul 23, 2015. 1 changed file with 101 additions and 10 deletions.
    111 changes: 101 additions & 10 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -18,7 +18,6 @@
    - 読者に__分散__の感覚を掴んでもらう
    - 逐次アルゴリズムと分散アルゴリズムの比較時に役立つ


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

    @@ -27,8 +26,8 @@
    - 分散システムをグラフに見立てる
    - 頂点=プロセス、辺=通信チャンネル
    - グラフ探索用の分散アルゴリズムを提示
    - parallel traversal, breadth-first traversal, depth-first traversal
    - spannning treeおよびringの構築
    - 並列探索、幅優先探索、深さ優先探索
    - スパニングツリーおよびリングの構築
    - ブロードキャストとコンバージキャスト
    - 分散グラフ探索手法は逐次版のそれとは異なる
    - 分散環境では、一つの種類の探索が複数の方法(アルゴリズム)で実現可能
    @@ -37,39 +36,131 @@
    1.1 分散アルゴリズム
    ------------------

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

    ### 1.1.1 定義

    #### プロセス: Processes

    プロセス:
    - 分散システム上での計算単位(computing unit)
    - プロセス群が協調して、共通の目標を達成する
    - プロセス間で(何らかの手段で)情報を交換する必要があることを意味する
    - 協調および共通目標 => プロセス同士は何らかの手段で情報を交換する必要がある

    プロセスの集合は静的:
    - システムを構成する__n__個のプロセスは`Π ={p1,...,pn}`と表記
    - 各`p1`は個々のプロセスを示す
    - 各プロセスは逐次実行
    - システムを構成する__n__個のプロセスは`Π ={p(1),...,p(n)}`と表記
    - ! 下付き文字がgistで表現しにくいため関数表記にしています
    - 各`p(1)`は個々のプロセスを示す

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

    プロセス添字と識別子:
    - `i`はプロセスの添字
    - 外部の観測者がプロセス群を識別するために利用可能
    - それぞれのプロセス`p(i)`は、識別子`id(i)`を有する
    - プロセス`p(i)`は自分の識別子`id(i)`を知っている
    - ほとんどのケースでは`id(i) = i`

    #### 通信媒体: Communication Medium

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

    #### 通信媒体: 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. アルゴリズムに従いメッセージを処理
    - 3. もしかしたら隣人にメッセージを送るかも

    一つのプロセスが一度に処理するメッセージは一つ:
    - あるメッセージの処理は、別のメッセージの到着によって割り込みされない
    - 受信メッセージはまずキュー(入力バッファ)に格納される
    - キューの前方から順に取り出され、処理されていく
    - 図1.2の右側は非同期実行の例
    - 非FIFOチャンネル: `p(1) => p(2)`のメッセージ到着順が逆転
    - 同期実行の方がより構造化されているのが見てとれる

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

    同期/非同期システム上での問題を解く際に、あるプロセスは以下の二つによって特徴付けられる:
    - 入力パラメータ群 (解くべき問題に関連)
    - 環境に対する _初期知識_
    - 自分の識別子、プロセスの総数、隣人の識別子、通信グラフの構造、etc

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

    この初期知識では、合計プロセス数をあらかじめ知っているプロセスは存在しない。
    それを知るためにはプロセス間で情報を交換する必要がある。

    ### 1.1.2 導入例: コミュニケーショングラフを学習する

    1.2 並列探索: ブロードキャストとコンバージキャスト
  27. sile revised this gist Jul 10, 2015. 1 changed file with 15 additions and 0 deletions.
    15 changes: 15 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -37,8 +37,23 @@
    1.1 分散アルゴリズム
    ------------------

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

    ### 1.1.1 定義

    プロセス:
    - 分散システム上での計算単位(computing unit)
    - プロセス群が協調して、共通の目標を達成する
    - プロセス間で(何らかの手段で)情報を交換する必要があることを意味する

    プロセスの集合は静的:
    - システムを構成する__n__個のプロセスは`Π ={p1,...,pn}`と表記
    - 各`p1`は個々のプロセスを示す
    - 各プロセスは逐次実行

    プロセス添字と識別子:


    #### プロセス: Processes

    #### 通信媒体: Communication Medium
  28. sile revised this gist Jul 10, 2015. 1 changed file with 29 additions and 1 deletion.
    30 changes: 29 additions & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -15,18 +15,46 @@

    目的:
    - 分散グラフアルゴリズムの提示 (分散アプリケーションで利用可能)
    - 読者に__分散__の感覚を掴んでもらうこと
    - 読者に__分散__の感覚を掴んでもらう
    - 逐次アルゴリズムと分散アルゴリズムの比較時に役立つ


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

    要旨:
    - 分散アルゴリズムに関連する基礎定義の導入
    - 分散システムをグラフに見立てる
    - 頂点=プロセス、辺=通信チャンネル
    - グラフ探索用の分散アルゴリズムを提示
    - parallel traversal, breadth-first traversal, depth-first traversal
    - spannning treeおよびringの構築
    - ブロードキャストとコンバージキャスト
    - 分散グラフ探索手法は逐次版のそれとは異なる
    - 分散環境では、一つの種類の探索が複数の方法(アルゴリズム)で実現可能
    - それぞれが時間計算量(time-complexity)とメッセージ複雑性(message-complexity)の間のトレードオフを有する

    1.1 分散アルゴリズム
    ------------------

    ### 1.1.1 定義

    #### プロセス: Processes

    #### 通信媒体: Communication Medium

    #### 構造: Structural View

    #### 分散アルゴリズム: Distributed Algorithm

    #### 同期アルゴリズム: Synchronous Algorithm

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

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

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

    ### 1.1.2 導入例: コミュニケーショングラフを学習する

    1.2 並列探索: ブロードキャストとコンバージキャスト
  29. sile revised this gist Jul 10, 2015. 1 changed file with 18 additions and 1 deletion.
    19 changes: 18 additions & 1 deletion damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,24 @@
    第一部 分散グラフアルゴリズム
    =========================

    第一部は分散グラフアルゴリズムを扱う:
    - 分散システムをグラフと見立てる
    - 頂点はプロセス(ノード)に対応
    - 辺は通信チャンネルに対応

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

    目的:
    - 分散グラフアルゴリズムの提示 (分散アプリケーションで利用可能)
    - 読者に__分散__の感覚を掴んでもらうこと
    - 逐次アルゴリズムと分散アルゴリズムの比較時に役立つ


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

    @@ -46,4 +64,3 @@

    1.7 演習問題
    ------------

  30. sile created this gist Jul 8, 2015.
    49 changes: 49 additions & 0 deletions damps-01.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,49 @@
    第一部 分散グラフアルゴリズム
    =========================

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

    1.1 分散アルゴリズム
    ------------------

    ### 1.1.1 定義

    ### 1.1.2 導入例: コミュニケーショングラフを学習する

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

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

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

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

    ### 1.2.4 スパニング木を構築する

    1.3 幅優先スパニング木
    --------------------

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

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

    1.4 深さ優先探索
    ---------------

    ### 1.4.1 単純なアルゴリズム

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

    1.5 要約
    --------

    1.6 解題
    --------

    省略

    1.7 演習問題
    ------------