第五章ネットワークを航行するモバイルオブジェクト

概要:

モバイルオブジェクト:
- ユーザプロセスのリクエストに応じて、プロセスからプロセスへと移動する
この章では、モバイルオブジェクトがネットワークを航行するためのアルゴリズム、を扱う:
- 性質の異なる三つの分散アルゴリズムを取り上げる
- 全てのアルゴリズムは、以下を保証する:
  - 整合性: オブジェクトは同時に複数プロセスに存在しない
  - 要求したプロセスは、いつかはオブジェクトを獲得する

5.1 プロセスグラフ内のモバイルオブジェクト

5.1.1 問題定義

モバイルオブジェクト:

何らかのオブジェクト: ファイルとかデータ構造とか
異なるプロセス群によって逐次的にアクセスされる:
- ネットワーク内のプロセス間を移動
- オブジェクトが現在位置しているプロセス == 所有者、となる
  - 所有者は、そのオブジェクトを専有的に使うことが可能
  - 使い終わったら解放する

航行サービスが必要:

プロセス群に、以下の二つの操作を提供:
- acquire_object()
- release_object()
プロセスp[i]がオブジェクトを使いたい場合は、以下のようにする:
- acquire_object(); use of the object by p[i]; release_object();

オブジェクトの整合性を維持するためには、以下の二つの性質が守られる必要がある:

安全性: いかなる時でも、オブジェクトは最大で一つのプロセスに属する
生存性: acquire_object()を呼び出したプロセスは、いつかはオブジェクトの所有者となる

5.1.2 モバイルオブジェクト対相互排他

この問題は、特定のケースでは、相互排他問題の一種に他ならない:

「モバイルオブジェクトの所有が、所有者に特別な権利(e.g. リソースへのアクセス権)を与える」ようなケース
この場合、モバイルオブジェクト自体はステートレスとなる
- 「トークン」と呼ばれる

分散相互排他アルゴリズムには、二つの主要な実現方法がある(! 本とは若干ニュアンスが異なる):

トークンベース: 本章で紹介
許可ベース: 10章で紹介

5.1.3 集中的(ホームベース)アルゴリズム

モバイルオブジェクトの航行に対する簡単な解法:

ホームベース構成をとる:
- 静的に特定のプロセスpをオブジェクトに関連付けておく (ホームプロセスにする)
- 非所有状態のオブジェクトは、常にpに位置している
acquire_object()呼び出し時には、要求プロセスとpとの間で、スリーウェイハンドシェイクが行われる

スリーウェイハンドシェイク

REQUEST(i)、OBJECT(obj)、RELEASE(i,obj)、の三つのメッセージを使用する: (! 名前や引数は本の表記とは若干異なる)

When p[i].acquire_object():

p[i]はREQUEST(i)をホームプロセスpに送る

When p receives REQUEST(i):

pはローカルキューにメッセージを追加する
もしキューの先頭がこのメッセージだったら、p[i]にOBJECT(obj)を送る

When p[i] receives OBJECT(obj):

オブジェクトを使用し、終わったらrelease_object(i,obj)を呼び出す
RELEASE(i,obj)がpに送られる

When p receievs RELEASE(i,obj):

pは更新されたオブジェクトを保存する
次にローカルキューから、p[i]のメッセージを削除する
キューが空ではないなら、先頭のプロセスに対してOBJECT(obj)を送る
=> 3 へ進む

図5.1は実行例

議論

ホームプロセスpは、ローカルキューにFIFOやその他の優先順序キューを使うことができる
- アプリケーションの要求次第
小さなシステムでは上手く動くが、スケーラビリティや局所性に乏しい:
- オブジェクトの使用頻度が高いと、ホームプロセスがボトルネックになり得る
- 解放時に常にホームに戻るのも非効率
  - 次の利用者がいるなら、直接そこに送った方が良い

5.1.4 この章で紹介するアルゴリズム

三つのアルゴリズムを取り上げる。

いずれでもホームベースは使わない:

上述の欠点は当てはまらない
以降で扱うアルゴリズムでは「ホームが動的に変わる」と見做すこともできる:
- モバイルオブジェクトの「ホーム」は、その最後の使用者(プロセス)
- 解放時に次の使用者がいない場合は、オブジェクトは現在位置から移動しない
- => 同じプロセスが再度オブジェクトを使う場合は、メッセージ送受信が不要

アルゴリズム間での相違点:

ネットワークの形状(構造)に対する仮定が異なる:
- アルゴリズムのコストや性質は、この形状に依存する
- 主に、モバイルオブジェクや要求メッセージのルーティング方法が変わる

5.2 完全ネットワーク用の航行アルゴリズム

この節では完全ネットワーク上での航行アルゴリズムを扱う:

全てのノードのペアは非同期チャンネルで直接通信可能
チャンネルがFIFOであることは要求されない

5.2.1 基本原理

静的に決定されるホームプロセスは存在しない:

問題: 「p[i]がオブジェクトをリリースする際に、次はどこに送信すれば良い？」

モバイルオブジェクトに埋め込まれた制御データ

オブジェクトはobtained[1..n]という制御データを保持する:

p[i]が所有した回数がobject[i]に保持される (獲得する度にインクリメント)
初期値は全ての0

ローカルデータ構造

各プロセスはrequest_by[i][1..n]というローカル変数を有する:

プロセス毎のオブジェクト要求リクエスト数を保持するための変数
使われ方:
- p[i]がオブジェクトを獲得したい場合、REQUEST[i]というメッセージをブロードキャストする
- それを受け取ったp[j]は、request_by[j][i]をインクリメントする

要求プロセスを決定する

obtainedとrequest_byを使うことで、オブジェクトを要求しているプロセス群をローカルで計算可能:

p[i]がオブジェクトを解放しようとしているプロセスとする
(p[i]の視点から見て)オブジェクトを要求しているプロセス集合S[i]は、以下の式で計算可能:
- S[i] = {k | request_by[i][k] > obtained[k]}
- => 要するに「要求回数が取得回数よりも多いプロセス集合」を求めているだけ
p[i]は、S[i]が空でなければ、要求プロセスがいると判断可能
- 要求プロセス集合の中のどれかはオブジェクトを取得可能
- => デッドロックフリーダム性質を満たしている

飢餓フリーダムを保証する

飢餓には気をつけなけばいけない:

例えばp[1]とp[2]とp[3]が常にプロセスの要求と解放を繰り返しているとする
この場合、オブジェクトがp[1]とp[2]の間を往復し続けて、p[3]は永遠に獲得できない可能性がある
=> p[3]は飢餓状態

簡単な解決方法:

競合が高い状況で、オブジェクトが限定された範囲内で循環しないように、各プロセスが次に送るプロセスの優先度付けを工夫する
具体的には、p[i]にとっての送信先プロセスの優先度は以下のようになる
- i+1, i+2, ..., n, 1, ..., i-1
- つまり、正方向で自分にIDが近い順にオブジェクトが送信されることになる (仮想的なリングがあるイメージ)
- => 競合が高い場合、p[i]はp[i-1]からオブジェクトを受け取るが、p[i-1]はp[i]にとって優先度が最低なので、次の送信先には選ばれず、オブジェクトが送り返されることはない

5.2.2 アルゴリズム

追加のローカル変数

各プロセスはrequest_by[i][1..n]に加えて、以下の二つのローカル変数を有する:

interested[i]:
- オブジェクトを要求中(or 獲得中)ならtrueになる
- 初期値はfalse
object_present[i]:
- オブジェクトを保持している場合はtrueになる
- 初期値は、最初にオブジェクトが配置されたプロセスはtrueで、それ以外はfalse
- => 初期状態が非対称なのが特徴的

構造的なビュー

図5.2:

! この図を必要性がいまいち分からないので省略 (これまで出てきた以上の話はない)

アルゴリズム

図5.3をベースに説明:

注釈: 各関数内のコードはアトミックに実行される
- 相互排他的に実行される (! このアルゴリズムに限った話ではなく、分散アルゴリズムはたいてい同じ)
- プロセスがオブジェクトの使用中にREQUEST()の受信による割り込みが入ることはある

アルゴリズムのコスト

オブジェクト取得に必要なメッセージ数:

a) オブジェクトが手元にある場合は0
b) オブジェクトが別プロセスにある場合:
- REQUEST(i)のブロードキャストでn - 1
- OBJECT()の受信用に1
- => 合計: n

メッセージサイズ:

REQUEST(): プロセスIDを保持するのでO(log2 n)
OBJECT():
- ! 本に記載がないけど軽く概算
- obtained[1..n]を保持するのでO(n log2 m)くらい
- mは、オブジェクトの要求回数の最大値 (実際には最大nだけあれば、何とかやりくりできそう)
- オブジェクト本体の情報は定数項として考慮から外した

時間複雑性(オブジェクトの獲得までに要する時間ユニット。一つのメッセージ送信で一ユニット消費)

a) オブジェクトが手元にある場合は0
b) オブジェクトが別プロセスにある場合:
- 注意:
  - オブジェクトが使用中の場合は、REQUEST()の転送時間は計算量にカウントされない
  - 理由:オブジェクト獲得までの経過時間がREQUEST()の転送時間によって遅延させられることがないため
- 所要時間は、負荷(競合度)に応じて1か2のどちらかとなる:
  - 低負荷の場合は2: REQUEST()が所有プロセスに届く時間 + OBUJECT()が送り返される時間
  - 高負荷の場合は1: (上述に理由によりREQUEST()の時間は無視できるので)OBJECT()が送られるまでの時間

早期の更新は望ましいか？

非同期性によりobtained[k] > request_by[i][k]という状況が発生し得る:

図5.4: p[j]からp[i]に(直接的に or 間接的に)送られた二つのメッセージ到着が逆転
チャンネルがFIFOであるかどうかに関わらず発生し得る
- 間接経路を経た時点でFIFOの意味は薄くなる

obtained[k] >= request_by[i][k]という不変項を維持したいなら早期更新が可能ではある:

現状はREQUEST()受信時にのみrequest_byを更新している
それを以下のように変更する:
- 1. オブジェクト受信時にobtainedに基づいてローカル変数を(早期)更新する
  - 行15: for k ∈ {1,...,n} do request_by[i][k] <- max(request_by[i][k], obtained[k]) end for
- 1. REQUEST()の送信側は、自分の要求発行数をメッセージに乗せるようにする
  - 行4: for k ∈{1,...,n} \ {i} do send REQUEST(i,request_by[i][i]) to p[k] end for
  - ※ 以前のように単にREQUEST()受信時にインクリメントするだけでは、不整合が生じる可能性があるため
- 1. REQUEST(k,rnb)の受信側は、自分と相手が通知した要求発行数の内の大きい方を採用する
  - 行16: request_by[i][k] <- max(request_by[i][k], rnb)
これは有用か？
- この修正による現実的なメリットは存在しない
- 加えて、以下のように、必要なメッセージサイズと処理の両方が増えてしまう:
  - a) REQUEST()にシーケンス番号(request_by[i][i])を付与する必要がある
  - b) request_byの更新処理が増える(オブジェクト受信時)

結論: 直観には反するが、早期更新はこの航行アルゴリズムには望ましくない

5.3 スパニング木に基づく航行アルゴリズム

5.2の航行アルゴリズムは、リクエストのブロードキャストと上限無しのカウンタ、に基づいていた:

この節では静的に定義されたスパニング木に基づいたアルゴリズムを取り上げる
- 各プロセスは自分の隣人のみと通信する (purely local)
- 変数群の値にも上限がある

5.3.1 アルゴリズムの原理: 木の不変項とプロキシ振る舞い

木の不変項

不変項: モバイルオブジェクトを所有するプロセスが木のルートとなる
- 図5.5のp[a]がルート
各プロセス(から送信されたメッセージ)は、親を辿っていくことで、モバイルオブジェクトに行き着けるルートへとつながる隣人
- 各プロセスはルートに至る経路をローカルに知ることが可能
不変項を維持する方法:
- オブジェクトを送信する時にエッジの向き(親子関係)を反転させれば良い
  - オブジェクトの受信側が常に親になる
    - 受信プロセスは、常に第二レベルに位置しているので、これによりルートとなる
  - 「エッジ反転(edge reversal)」と呼ばれるテクニック
- 図5.6: p[a]からp[c]にルートが変わった例

プロキシの概念

ルート以外のプロセスが、オブジェクト獲得リクエストを受け取ったらどうするか:
- 以下を再帰的に繰り返す:
  - 1. 自分が代わりに、親に対してリクエストを送信する
  - 1. オブジェクトを受信したら、要求元に転送する
あるプロセスにリクエストが複数来たらどうするか:
- ローカルキュー(FIFO)を管理:
  - 1. リクエストが来たら、まずキューに入れる
    - 自分自身が要求者の場合も同様
  - 1. 最初のリクエストだけを(プロキシ的に)親に送る
  - 1. オブジェクトを受信したら、最初の要求元に転送
  - 1. キューの先頭要素を取り除いて、次のリクエストを処理する
- 図5.7: p[b]のローカルキューの状態

5.3.2 アルゴリズム

ローカル変数と初期化

interested[i]: 前節と同様の意味
queue[i]:
- ローカルキュー
- 初期値は空
- キューのサイズには上限がある:
  - 最大でd(入力エッジ数 + 自分自身)個のプロセスIDを保持
  - d log2 nビットで表現可能
parent[i]:
- スパニング木上での親ノード
- parent[i] == iで所有者判定が可能なので、前節にあったobject_present[i]は不要となった

プロセスの振る舞い

図5.8のコードを元に説明

5.3.3 議論と性質

メッセージに関して

オブジェクトは、リクエストメッセージが辿った経路を逆転しつつ辿る
REQUEST()は送信者の識別子を含む
- => bounded
- 全てのローカル変数もbounded

非FIFOチャンネル

(前節と同様に)FIFOであることは要求されない
以下のような問題が発生しないか？
- 1. p[i]が、リクエストをp[j]に送信
- 1. リクエストを受信したp[j]は「まずオブジェクト」を「次に自分のリクエスト」をp[i]に送信
- 1. 両者の到着順が逆転して、リクエストが先にp[i]に届く
- => p[i]は(自分にとっての)親のp[j]に、p[j]から来たリクエストをプロキシ的に転送するのか？
図5.9に書かれているように、実際には問題にはならない:
- p[i]は自分が送ったリクエストに対応したオブジェクトまだ受け取っていない
- つまり、ローカルキューには要素が一つ以上残っている
- p[j]からリクエストが来ても、単にキューに積まれるだけ
  - p[j]のリクエストが処理される時には、既にp[i]にとっての親ではなくなっている

木の不変項に関して

このアルゴリズムで使われているチャンネル群自体は、無向木を構成している
変数parent[i]によって決められるチャンネルの向きを考慮すると、以下が得られる:
- 最初は、(この変数は)オブジェクトが初めに位置しているプロセスをルートとした有向木を定義する
- それから、リクエストやオブジェクトの移動によっては、p[i]とp[j]が相互を親として認識することがあり得る
  - ex. 図5.9でREQUEST[j]が転送中に停止した場合(?)
  - これが起こるには以下の状況が必要(! 図5.9のケースを言葉にしただけ):
    - parent[j]はp[i]で、p[j]はp[i]にオブジェクトを送信した
    - parent[j]はp[j]で、p[i]はp[j]にREQUEST[i]を送信した
  - オブジェクトp[i]に届いたら、parent[i]は自分自身になる
  - => スパニング木のエッジの向きもp[j]からp[i]に変わり、通常の木に戻る
これを考慮して、以下のように抽象スパニング木を定義する:
- 基本はparent[k]の値が(抽象木を構成する)エッジの向きを決定する
- 上記のケースの場合は、p[j]からp[i]へのエッジがあるとする
- つまり、すべてのエッジは「オブジェクトを所有しているか、送信先となっているプロセス」の方向を向いている、と定義する
- => これにより任意のタイミングで一意な抽象木が得られるようになる

アルゴリズムのコスト

最善ケース: 前節と同様に要求者と所有者が同じならコストはゼロ
最悪ケース:
- 最も距離が離れた二つのプロセスの片方が要求者で、もう片方が所有者の場合に発生
- コストは木の直径Dに依存する:
  - リクエストが所有者に届くまでに、D個のメッセージと時間が必要
  - オブジェクトが要求者に届くまでも同様
  - => 計算量は両方ともO(D)となる

プロセス識別子に関して

p[i]が関心を持つのは、自分のローカルキューに格納されるプロセスの識別子だけ:
- 自分自身と隣人群
距離が2以上離れているプロセスの識別子には関与しない:
- それらとは識別子が重複していても、アルゴリズムは正しく動く
- グラフ彩色問題の要件を満たしていれば良い
この性質はスケーラビリティおよびローカリティの観点から、特に興味深い

優先度に関して

ローカルキューはFIFO
- 全ての要求者がいつかはオブジェクトを取得可能
アプリケーションの要件次第で、別の優先順位付けを採用しても良い
- ex. 特定のプロセスを優遇する

5.3.4 アルゴリズムの証明

定理3

図5.8で述べられているアルゴリズムは「オブジェクトが同時に複数の場所に位置しないこと(safety)」と「オブジェクトを要求したプロセスはいつかはそれを獲得可能なこと(liveness)」を保証する。

証明

! 当たり前のことが詳細に書かれているだけなので、ざっくりまとめます

安全性(safety)の証明

初期状態では、オブジェクトは一つのプロセスp[i]に位置する
以降は「オブジェクトの送信」と「親の更新」が常にセットで行われる
- 送信先がp[j]ならparent[i] = p[j]とする
- オブジェクトの所有プロセス(parent[i] == i)は、最大で一つなので安全性は満たされる

生存性(liveness)の証明

二つのパートから構成される:

デッドロックフリーダムの証明
飢餓フリーダムの証明

デッドロックフリーダム:

前提: 不変項を満たす抽象スパニング木が維持されている
a) 到達性:
- 要求者が送ったREQUESTは、いつかは(木のルートに位置する)所有者に届く
- 所有者が送ったOBJECTは、いつかはいずれかの要求者に届く
b) 所有者はいつかはオブジェクトを解放(and キューの先頭プロセスに送信)する
=> デッドロックフリー

飢餓フリーダム (!論の展開方法が本とは結構異なっている):

a) 各プロセスのローカルキューはFIFO
b) ローカルキューのサイズはbounded (辺の数 + 1)
c) 最悪のケース:
- 1. 要求者からルートに至るパス上のものを除いた全てのローカルキューが満杯
- 1. 要求者がルートにREQUESTを送ったことで、全てのローカルキューが満杯になった
  - 要求者は(仮想的な)全体キューの末尾に位置していることになる
- 1. 所有者がオブジェクトを解放する度に、要求者の全体キュー内の位置は前に進む
- 1. FIFOなため位置が後ろに進むことはないので、いつかは全体キューの先頭に到達する
=> 飢餓フリー

5.4 適応的な航行アルゴリズム

この節は分散FIFOキューを実装するためのアルゴリズムを紹介:

enter()で自プロセスをキューの末尾に追加
キューの先頭になったらexit()でキューから抜ける

以下の二つを仮定:

完全非同期ネットワーク
基礎となるスパニング木
- 木の構造はenter()およびexit()によって、動的に変化していく

モバイルオブジェクトの観点からは:

acqure_object()は、enter()に対応
所有権の獲得は、「キューの先頭に到達」に対応
release_object()は、exit()に対応

5.4.1 適応的な性質

この節で取り上げる分散ありごリズムは__適応的(adaptive)__:

オブジェクトに関心のないプロセスがアルゴリズムに参加しないなら「適応的」といえる
- そういったプロセスは有限時間経過後に、アルゴリズムに関連する一切にメッセージを受信しなくて良くなる
図5.3(完全ネットワークベース)と図5.8(スパニング木ベース)は適応的ではない　
- 前者ではREQUESTのブロードキャストがあり、後者ではプロキシとして動作する必要がある

5.4.2 実装原理

分散キュー

キューの実装のために、各プロセスp[i]は、二つのローカル変数を管理する:

interested[i]:
- キューに入っている(or 入ろうとしている)ならtrue
- 実装的には、enter()を呼んでからexit()を呼ぶまで、がtrue
next[i]:
- 初期値は⊥
- キュー内の次のプロセスを指す
- exit()時には、次のプロセスp[next[i]]にモバイルオブジェクトを送る
- 一般的なリンクリストの話と特に変わるところはない

キューにどうやって入るか: メッセージをルーティングするためのスパニング木

p[l]をキュー内の最後のプロセスとする (つまりinterested[l] ∧ next[l] = ⊥)。

問題は、p[i]がキューに入りたい場合に、それをどうやってp[l]に通知するか:

p[i]の要求を、キューの末尾プロセス(p[l])に通知するための分散ルーティング構造が必要
- かつ、この構造はプロセスの要求とそれによる末尾の変化に応じて、発展していく必要がある
答えは簡単:
- 動的に発展していくスパニング木があれば良い
- 木のルートはキュー内の末尾プロセス
図5.11: 動的スパニング木の例
- 1. 初期状態は左のグラフ (p[4]がルート)
- 1. p[2]がenter()を実行
- 1. REQUESTがp[1]を経由(真ん中のグラフ)して、p[4]に届く(右のグラフ)
- 1. p[2]が新しいルート(= キューの末尾)となった
この例で分かるように、一度に複数の木が存在し得る(真ん中のグラフ):
- ただし、閉路は存在しない
- かつ、全ての制御メッセージが処理された後は、一つのスパニング木となる
図5.8(前節)のアルゴリズムとの違い:
- 図5.8のアルゴリズムは、静的に構築されたスパニング木の"エッジ逆転"に基づいていた
- 今回は全てのチャンネルをスパニング木の一部として利用可能:
  - 要求元プロセスを直接指すように辺が入れ替えられる (右のグラフ)
  - 木の形は動的に変化する

アルゴリズムで使用されるヒューリスティック

スパニング木を管理するためにparent[i]というローカル変数が必要:

REQUEST(j)を受け取った場合は、p[j]が新しい親に設定される
p[i]がキューに入りたい場合は、p[j]に要求を送信する
- p[i]の観点からはp[j]がキューの末尾プロセス

空のキューの場合

オブジェクトを保持しているかどうかの識別用にobject_present[i]というローカル変数もある。

キューが空であることは、どうやって判定するか？

要素が一つ(自分自身)だけ、ということはobject_present[i] ∧ (parent[i] == i)で判定可能
要素が空かどうかは￢ interested[i] ∧ object_present[i] ∧ (parent[i] == i)で判定可能

5.4.3 分散キューに基づいた適応的アルゴリズム

アルゴリズムの構造と初期化

構造:

お決まりの図5.2の話 (省略)
以前のアルゴリズムと比較しやすいようにenter|exitではなく、(acquire|release)_objectの用語を使う

初期状態:

p[k]にオブジェクトが位置しているとする
- p[k]は空のキューの先頭に架空的に位置していることになる
ローカル変数の初期値:
- object_present[k] = true
- ∀i!=k: object_present[i] = false
- ∀i: parent[i] = k, interested[i] = false

プロセスの振る舞い

図5.12の実装コードを元に説明

5.4.4 性質

変数とメッセージサイズ、メッセージ複雑性

サイズ:

ローカル変数:
- object_present[i]: 1bit
- interested[i]: 1bit
- parent[i]: ceil(log2 n)bit
- next[i]: ceil(log2 n+1)bit
メッセージ:
- REQUEST(): OBJECT()との識別用に1bit、プロセスIDを運ぶのでもうceil(log2 n)bit
- OBJECT(): アプリケーションデータを除けばREQUEST()との識別用の1bitのみ

メッセージ数:

最善:
- 0
- オブジェクトが既に自プロセスに位置している場合
最悪:
- n-1個のREQUEST()と一個のOBJECT()の転送が必要
- スパニング木がチェーンになっている場合
- 図5.13の左: p[i]からp[j]にREQUEST()送信
  - ただし、これにより次はoptimalな木ができる (右のグラフ)
  - 一回の転送でREQUESTがキューの末尾に届く
  - => 最悪ケースが連続することはなく、平均するとO(log n)で済む

適応性

適応性:

もしp[i]がacquire_object()を呼ばなくなったら、有限時間後に、REQUEST()を受け取ることがなくなり、結果としてアルゴリズムに参加することを止める。

そのようなプロセスp[i]について考える:

p[i]が発行した全てのREQUEST(i)が受信され処理された後のことを考える
K = {k[1], k[2], ...}を、その時点で、p[i]を親とするプロセスの集合とする
- この集合はbounded
1. p[i]は、新規にREQUEST(i)を送ることはない
- => Kのサイズが増えることはない
1. p[i]は、K内のプロセスp[k]から受け取ったREQUEST(k)を転送するものとする
- これによりp[i]の親がkになる (p[k]の親は自分自身)
- 集合Kからkが抜ける
- => これを繰り返すとKはいずれ空になる
- => Kはboundedなので空になるまでの時間にも上界がある
- => Kが空になれば、もうメッセージを受信することはないので、アルゴリズムに参加しなくなる
適応性は、スケーラビリティの観点から特に興味深い
- ACQUIRE_OBJECT()を呼ばないプロセス群は無視され、アルゴリズムのコストも削減される

5.4.5 実行例

図5.14:

1. 最初はp[1]がルート
1. p[2]とp[3]が同時にenter
1. p[2]が先にオブジェクトを取得
1. p[3]がキューの末尾に追加される
1. p[4]がenter => キューの末尾に追加
1. p[2]がexit => p[3]にオブジェクトが渡る
1. p[2]がenter => キューの末尾に追加
NOTE: 最後の構成を考えるとp[1]とp[5]は決してメッセージを受け取らない (適応性)

5.5 要約

口頭で軽く触れる

5.6 解題

省略

5.7 演習問題

省略

legokichi/damps-05.md

第五章 ネットワークを航行するモバイルオブジェクト

5.1 プロセスグラフ内のモバイルオブジェクト

5.1.1 問題定義

5.1.2 モバイルオブジェクト 対 相互排他

5.1.3 集中的(ホームベース)アルゴリズム

スリーウェイハンドシェイク

議論

5.1.4 この章で紹介するアルゴリズム

5.2 完全ネットワーク用の航行アルゴリズム

5.2.1 基本原理

モバイルオブジェクトに埋め込まれた制御データ

ローカルデータ構造

要求プロセスを決定する

飢餓フリーダムを保証する

5.2.2 アルゴリズム

追加のローカル変数

構造的なビュー

アルゴリズム

アルゴリズムのコスト

早期の更新は望ましいか？

5.3 スパニング木に基づく航行アルゴリズム

5.3.1 アルゴリズムの原理: 木の不変項とプロキシ振る舞い

木の不変項

プロキシの概念

5.3.2 アルゴリズム

ローカル変数と初期化

プロセスの振る舞い

5.3.3 議論と性質

メッセージに関して

非FIFOチャンネル

木の不変項に関して

アルゴリズムのコスト

プロセス識別子に関して

優先度に関して

5.3.4 アルゴリズムの証明

定理3

証明

安全性(safety)の証明

生存性(liveness)の証明

5.4 適応的な航行アルゴリズム

5.4.1 適応的な性質

5.4.2 実装原理

分散キュー

キューにどうやって入るか: メッセージをルーティングするためのスパニング木

アルゴリズムで使用されるヒューリスティック

空のキューの場合

5.4.3 分散キューに基づいた適応的アルゴリズム

アルゴリズムの構造と初期化

プロセスの振る舞い

5.4.4 性質

変数とメッセージサイズ、メッセージ複雑性

適応性

5.4.5 実行例

5.5 要約

5.6 解題

5.7 演習問題

第五章ネットワークを航行するモバイルオブジェクト

5.1.2 モバイルオブジェクト対相互排他