J72 j IEICE 1999 2 最近の更新履歴 Hideo Fujiwara J72 j IEICE 1999 2

論 文

分散移動シ ステムのための前後関係保存放送プ ロト コル

大堀 力

井上美智子

増澤 利光

藤原 秀雄

A Causal Broadcast Protocol for Distributed Mobile Systems

Chikara OHORI^†∗, Michiko INOUE^†, Toshimitsu MASUZAWA^†, and Hideo FUJIWARA^†

あらまし 本論文では ，分散移動シ ステムのための前後関係保存放送プ ロト コルを提案する．移動計算機は 一 般に 不特定多数であり，計算能力，通信能力が 固定計算機に 比べて著し く劣っているため ，複雑度が 移動計算機 数にできるだけ 依存せず，移動計算機の実行する計算量と通信量の小さいアルゴ リズムが 求められ る．また ，移 動計算機の移動に 伴うハンド オフへ対処するために 行われ る処理のより小さいアルゴ リズムが 求められ る．本論 文は 移動計算機と移動支援局の階層構造に 着目し た ，効率の良い前後関係保存放送アルゴ リズムを提案する．提 案手法は ，メッセージ オーバヘッド（ 各 メッセージに 追加する情報量 ）が 移動計算機数に依存し ていない．更に ， 既知の手法に 比べて ，メッセージオーバヘッド が 小さく，移動端末移動時のハンド オフに 対処するための遅延時 間と メッセージ 数が 小さい点で優れている．

キーワード 分散アルゴ リズム，移動通信，放送，前後関係

1. _{ま え がき}

小型計算機の高性能化と無線通信技術の進歩によっ て ，移動計算機が 無線通信を利用し てネット ワークに 接続す るこ とが 可能に なった ．分散移動シ ステ ムは ， 固定ネット ワー クに 移動計 算機（mobile host, MH^） を付加し たシ ステムである．_MHは 計算の実行中に移 動することができ，無線機能をもつ固定計算機と無線 通信が 可能である．無線機能をもつ固定計算機を特に 移動支援局（mobile support station, MSS^{）と呼び ，} 各_MSSの地理的，あ るいは ，論理的な 無線通信可能 領域を その_MSSのセル と 呼ぶ ．あ る_MSSのセル 内 に 存在する_MHが 別の_MSSのセルに 移動すると ，移 動元の_MSSと_MHとの間の無線通信チャネルが 切断 され ，移動先の_MSSと_MHとの間に 無線通信チャネ ルが 開かれ る．この移動し た_MHの無線通信チャネル の切換動作を_MHのハンド オフと 呼ぶ．また ，移動元 の_MSSから 移動先の_MSSへ_MHが ハンド オフされ るともい う．

MHを 含 まな い 分 散シ ステ ムで 問 題を 解 くプ ロト コル に ついて は ，これ まで 数 多 くの 研 究が な され て

†奈良先端科学技術大学院大学情報科学研究科 ，生駒市

Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma-shi, 630–0101 Japan

∗

現在，（ 株 ）_NTTデ ータ

いる_[2]∼_{[4], [6]}．し かし ，これらはハンド オフに 伴う ネット ワークの形状の動的な変化に 対応できず，分散 移動シ ステ ムに 適用で きな いこ とが 多い．そのた め ， 分散移動シ ステムのためのプ ロト コルの設計が 必要で あり，さまざ まな 研究が 行われ ている_[7]∼_[9]．更に ， 分散移動シ ステム上のプ ロトコルの設計には ，次の三 つの 目標を考慮し なければ ならない．

1. MSS^{に 比べ て}MHは 性 能（ 記 憶の 容 量と 信 頼 性 ，処理能 力 ，使用可能 電力量など ）が 低い ．更に ， MH-MSS間の無線通信チャネルは ，_MSS間の有線通

信チャネルに比べて通信帯域が 著し く小さい．よって， MH^{で 記憶する情報量，}MH^{の計算量，}MH^の通信量

をできるだけ小さくする必要がある．

2.シ ステ ム 内に 存 在す る_MHの 数は_MSSの 数に

比べは るかに 大きいと 考えられ る．また ，_MHの数が プ ロト コル 開始時に 既知でないことや ，実行中に 変化 することもある．よって ，プ ロト コル 全体のコストが MHの数にできるだけ 依存し ないことが 望まれ る．

3.ハンド オフ発生時に ，プ ロトコルの実行を正し く

継続するため特別の処理が 必要となる場合がある．ハ ンド オフに よって 引き 起こ され る特別な 情報交換や ， プ ロト コル 実行の遅延操作など をできるだけ 少なくす る必要がある．

本論文では ，上記の三つの目標を達成する分散移動

シ ステム上の前後関係保存放送プ ロト コルを提案する． 任意の計算機から 送信され た メッセージ 間に 何らかの 因果関係がある場合，その順序に 従って受信するよう な メッセージ 交換を ，前後関係保存 メッセージ 交換と 呼ぶ ．前後関係保存 メッセージ 交換は ，シ ステムの監 視，資源割当て ，電子ニュース，電子会議など ，分散 シ ステムのさまざ まな 場面において 利用され る．_MH 間前後関係保存放送とは ，放送 メッセージ のあて 先が 常にすべての計算機である前後関係保存 メッセージ 交 換のことを指す．

しかし ，非同期式分散システムでは，計算機の処理の 非同期性と通信の非同期性から ，異なる計算機におけ る イベント の生起し た順序（ 実時間に 基づいた前後関 係 ）を決めることは不可能である．そこで ，_Lamport は イベント 間の 因果関係に 基づいた前後関係（_causal relation (→)^{）を提案し ている}[1]．ここで ，任意の イ

ベント a，bについて ，a_{→ b}が 成り立つのは 以下の いずれかの条件が 成り立つ場合である ．₍₁₎同一計算 機内で_a，_bの順に イベントが 生起し た ．₍₂₎あるメッ セージの送信と受信に対応する イベントがそれぞれ_a， b^{である ．}(3) a → c^{か つ}c→ bが 成り立つよ うな ， ある イベント cが 存在する．

この_Lamportの前 後関係を 利用し て ，さまざ まな 前 後 関 係 保 存 メッセ ージ 交 換プ ロト コ ルが 提 案され ている．まず，_MHを含まない分散シ ステムにおいて 前後関係保存マルチキャ スト（ 任意の複数の計算機を あ て 先と す る メッセ ージ 交 換 ）が 提 案され た_[3]．文 献_[3]のプ ロト コルは 各 メッセ ージ に それ 以前に 送信 された メッセージを添付する方法を用いている．この， 各 メッセージに 何らかの情報を メッセージ ヘッダ とし て添付する方法は ，その 後のさまざ まな前後関係保存 メッセ ージ 交換プ ロト コル[4], [6], [7], [9]^{で も利 用さ} れており，ヘッダ の大きさ（ メッセージ オーバヘッド ） がプ ロト コル の重要な 評価尺度とな る．文献_[3]のプ ロト コルは ，過去の メッセージをすべてヘッダに 含む ので 非常に メッセージ オーバヘッド が 大きい．そこで ， RST^{プ ロト コル}[6]では ，ベクト ル 時計_[2]のア イデ

アを利用し メッセージ オーバヘッド を削減し た．シ ス テム内の総計算機数を_N とすると，_RSTプ ロト コル で 使用する メッセ ージ ヘッダ は _N 個の_N 次ベ クト ルだけでよい．つまり，_RSTプ ロト コルの メッセージ オーバヘッド は_Θ(N²₎である ．また ，文献_[4]では ， RSTプ ロト コル を 放送に 特化することで ，使用す る

メッセージ ヘッダ は₁個の _N 次ベ クト ルとし ，メッ

セージ オーバヘッド を_{Θ(N )}とし ている．

近年，分散移動シ ステムにおいても，ベクトル 時計 のア イデアを用いた_MH間の前後関係保存メッセージ 交換プ ロト コルが 多数提案され ている．文献_[7]では ， メッセージ オーバヘッド が _O(N²₎である前後関係保 存マルチキャストプ ロト コルが 提案され ている．この プ ロト コルは ，メッセージのあて先_MHの数が 多いほ ど 使用する メッセージヘッダ は 小さくなり，特に 放送 に適用し た場合，メッセージ オーバヘッド は_{Θ(N )}と な る ．また ，_MHの 処理を その_MHと 接続し て いる MSSが 代理することで ，_MHで 必要な 記憶量 ，計算

量，通信量を小さく抑えており，目標₁を満たし てい る．し かし ，このプ ロト コルの メッセージ オーバヘッ ド は すべての計算機数_N に 依存し ているため ，目標 2^{を満たさない．文献}[9]では メッセージ オーバヘッド が_MHの 数に 依存し な い目 標₂を 満た す前後関係保 存マルチキャストプ ロト コルを提案し ている．シ ステ ム内の_MSSの数を _Nmssとすると ，このプ ロト コル の メッセージ オーバヘッド は ，_Θ(Nmss²₎である．ま た ，文献_[7]と 同様に_MHの 処理を_MSSが 代理する ことで ，目標₁も満たし ている．し かし ，このプ ロト コルでは ，前後関係を保証するために ，_MHのハンド オフが 生じ たときに ，その_MHをあて先とする伝送中 の メッセージが あるかど うかをすべての_MSSに 問い 合わせる．このため ，ハンド オフ 発生時の処理に 必要 な メッセージ 数が 多く，その遅延時間も大きい．この ため ，目標₃を満たし ているとはいえない．

本論文では ，分散 移動シ ステムに おけ る_MH間の 前後関係保存放送を 実現するプ ロト コル を 提案する ． 提案す るプ ロト コルは ，分散移動シ ステムの_MHと MSSによる階層構造を利用し ，放送の メッセージオー

バヘッド を_MHの数に 依存し ない_Θ(Nmss)とし てい る．また ，文献_{[7], [9]}と 同様に ，_MHの 処理を_MSS が 代理することで ，_MHで 必要な記憶量，計算量，通 信量を小さく抑えている．ハンド オフが 発生し た場合， 提案するプ ロトコルでは ，_MHをハンド オフする二つ の_MSS間で 情 報を 伝 達す るの みで あ り，文 献_[9]の プ ロト コルのよ うな_MSS全体にかかわ る情報交換を 必要とし ない ．更に ，文献_{[7], [9]}のプ ロト コルでは ， MH^{をハンド オフする}MSS^間でそのMH^{あての メッ}

セージ を転送する必要がある．し かし ，提案するプ ロ ト コルは ，各_MSSで 必要な 過去の メッセージ を 保存 することで ，このよ うな_MSS間での メッセージ 転送 を不要とし ている．

2.では分散移動シ ステムのモデルとこのモデルにお ける前後関係保存放送を定義する．3.では 移動計算機 間におけ る前後関係保存放送を実現するプ ロトコルを 提案する．4.でプ ロト コルの正当性を示し ，最後に5. でプ ロト コルの評価を行う．

2. _{諸 定 義}

2. 1 分散移動シ ステム

本 論 文で は ，分 散 移 動シ ステ ム の モデ ル とし て 文 献_[8]の モデ ル を 用 い る ．以 下 で は ，こ の モデ ル を 簡 単に 示す（ 図 ₁）．分 散 移 動シ ステ ム _S を₃項 組 S = (MSS, MH, CH) と 定 義 す る ．MSSは 移 動

支援局（_MSS）と 呼ば れ るプ ロセ スの 集合，MHは 移動計算機（_MH）と 呼ば れ るプ ロセ スの集 合，CH は_MSS間の静的通信チャネル の集合である ．本論文 で は 簡 単のた め に ，シ ステ ム 内に 存 在 す る 固 定 計 算 機は すべ て_MSSで あ ると する ．_MSSの数を _Nmss， MH^{の 数 を} Nmh ^{とし ，MSS} = {s1^,· · · , sN_mss}^， MH_{= {h1,· · · , hN}

mh^}とする．各プ ロセスは固有の 識別子をもち ，簡単のために _si，_hi の識 別子を 単に si^，hi^と表す．

二つの_MSS間に静的通信チャネルが 存在する場合， その 両端の_MSSは 相互に 通信可能で あ る．MSSと CHから構成され るネット ワークは連結であるとする． つまり，任意の_MSS間に 静的通信チャネルに よ る経 路が 少なくとも一つ存在する．各_MHは 動的通信チャ ネル と 呼ば れ る通信チャネル を 用いて ，一つの_MSS

図1 分散移動シ ステム Fig. 1 A distributed mobile system.

と 相互に 通信可能で あ る ．ハンド オフが 発生すると ， MHが 動的通信チャネルで 接続し ている_MSSが 変更

され る．例えば ，_{MH h}が_{MSS s}に 接続し ていると きに ，_sから別の_{MSS s}^′へ_hのハンド オフが 発生し たとすると ，_hと_sとの間の動的通信チャネルが 消失 し ，hと s^′ との間に 新たに 動的通信チャネルが 生成 され る．このように ，動的通信チャネルは_MHとど の MSSとの 間に 存在するか 決まって おら ず 動的に 変化

するため ，分散移動シ ステムのモデ ルにおいて動的通 信チャネルは ，その 両端の_MSSの状態と_MHの状態 の組とし て表され ているとする．つまり，各プ ロセ ス の状態には 接続状態とし て ，動的チャネルで 接続され ているプ ロセ スの識別子の 集合が 含まれ ている．_MH のハンド オフ処理は 有限時間内に 終了し ，ハンド オフ 処理中を除いてすべての_MHはいずれかの_MSSと接 続し ていると仮定する．

すべての静的・動的通信チャネルは_FIFOキューで あるとする．すなわち，通信チャネルを用いて送信し た メッセージは 送信され た順に 相手に 受信され る．更 に ，チャネルを用いて 送信され た メッセージは紛失さ れないとする．文献_[8]のモデルでは ，ハンド オフ時に 動的通信チャネルが 消失し た場合，その_FIFOキュー 内の メッセージは 紛失するとし ている．し かし 本論文 では ，簡単のために ，静的，動的にかかわらずすべて の通信チャネルに 入力され た メッセージは 有限時間内 に出力され ，メッセージの紛失は起きないと仮定する． ただし 本論文のプ ロト コルは ，動的通信チャネルにお け る メッセージの紛失に 対応できるように簡単に 拡張 できる．

分 散 移 動シ ステ ム の 状 況は ，シ ステ ム 内の すべ て のプ ロセ スの 状 態と すべ て の 通 信チャネル の 状 態か ら 構 成 され る ．プ ロ セ スで イベント が 生 起す るこ と により，分散移動シ ステムの 状況が 変化する．一般性 を 失わず シ ステ ム 全 体で 同 時に 一つの イベントし か 生 起し な いと 仮 定で き る ．状 況と イベント の 交 互 列 γ⁰, e¹, γ¹, e², γ²,· · ·^（γ^i，eⁱはそれぞれ 状況，イベン

ト を表す ）を分散移動シ ステムの実行と定義する．た だし ，_e

i

は_γⁱ⁻¹ で 生起可能な イベントであり，_γⁱ⁻¹ で_e

i

が 生起し た後の状況が_γ

i

である．実行は無限系 列であってもよく，有限の場合は 状況で 終わるものと する ．ここで ，_γ⁰ は 分散移動シ ステムの 初期状況で あり，初期状況では すべての_MHが いずれかの_MSS と接続し ているとする．

プ ロセスで生起する イベント とし て次の₇種類の イ

ベントを定義する．まず，（_MHを含まない ）従来の分 散シ ステムで 用いられている₃種類の イベント を定義 する．

1. internal：プ ロセ スの内部計算を表す イベント． 2. send： メッセージ の送信を表す イベント． 3. receive： メッセージの受信を表す イベント．

次に ，分散移動シ ステム特有のハンド オフを扱うた めの₄種類の イベントを定義する．これらは ，_{MH hi} が_{MSS sj} から_{MSS sk}へ ハンド オフされ たときに ， 4. 5. 6. 7.^{の順にそれぞれ}1回ず つ生起する イベント

で ，ハンド オフにかかわるプ ロセ スの接続状態の変化 と ，移動情報の交換を表す．移動情報とは ，_MHのハ ンド オフの際に ，ハンド オフにかかわるプ ロセス間で 交換され る情報で ，_hiから_sjへ ，_sjから_skへ ，_sk から_hi への順に 交換され る情報であ る．分散移動シ ステム上で 動作するプ ロト コルも，移動情報を利用し て情報交換可能であるものとする．

4. disconnecti^：hiで 生起する イベント．_hiの接続

状態が 空になることと，_hiから_sjへの移動情報_fの 送信を表す．

5. removej^：sj で 生起する イベント．_sj の 接続状

態からのhi^{の削除と ，}hiから送信され た移動情報f の受信，_skへの移動情報_f

′

の送信を表す．

6. accept_k^：sk^{で生起するイベント．}sk^{の接続状態}

への_hi の追加と ，_sjから 送信され た移動情報_f^′ の 受信，_hiへの移動情報_f^′′の送信を表す．

7. connecti^：hiで 生起する イベント．hi ^{の 接続状}

態が_{sk}になることと，_skから送信された移動情報 f^{′′の受信を表す．}

2. 2 前後関係保存放送

あるプ ロセスからすべてのプ ロセ スへあるメッセー ジを伝達することを放送と呼び ，放送を実現するプ ロ ト コルを放送プ ロト コルと呼ぶ．プ ロセ スが メッセー ジ の 放 送を 行 うと き ，まず 放 送プ ロト コル へ 放 送 要 求を出す．放送要求を受けた放送プ ロト コルはすべて のプ ロセ スで放送要求され た メッセージ の配達処理を 行う．

プ ロ セ ス_pi に お け る 放 送 メッセ ージ _m の 放 送 要 求と 配 達を ，それ ぞ れ _pi の イベン ト _cbcasti(m)， deliveri(m)で表す．混乱が 生じ ない限り，_i，_mを省 略することがある．_cbcast，_deliverをまとめて放送イ ベント と呼ぶ．以後，簡単のために ，任意の実行にお いて 放送要求がなされ る放送メッセージは 相異なると 仮定する．

［ 定義₁（ 放送 イベント 間の前 後関係 ）分散移動シ ス］ テムにおけ る任意の実行を_E，_E に 含まれ るすべての 放 送 イベント の 集合を_EB と す る ．_EB 上の 前 後関 係（

→B）は 以下のいずれかを満たす最小の₂項関係で ある．

1.同じプ ロセ スの異なる二つの 放送 イベントe，e^′

で ，_Eにおいてeがe^′より前に現れ るとき，e_{→ e}^{B ′}． 2.^{任意の放送メッセージ} m^{と任意のプ ロセス}pi^に

対し ，_cbcast(m)

→ deliverB i(m)^． 3.次の推移律が 成り立つ．

∀e, e^{′, e′′}∈ EB[(e→ e^{B ′}) ∧ (e^{′ B}→ e^′′) ⇒ e→ e^{B ′′}]^．

✷ 二つの 放送要求間に 前後関係がある場合，対応する 同一プ ロセ ス上の二つの 配達が その前後関係を保存す る放送を ，前後関係保存放送と呼ぶ ．

［ 定義₂（ 前後関係保存放送 ）分散移動シ ステムにおけ］ る任意の実行_Eについて ，以下の三つの性質を保証す る放送を前後関係保存放送と定義する．

1.^各cbcast(m)に 対し ，任 意のプ ロセ ス _pi 上で deliveri(m)^{が 正確に}1^{回生起する．}

2.^{あ るプ ロセ スで} deliver(m)が 生起するならば ， cbcast(m)が 生起するあ るプ ロセ スが 存在する．

3.任意の二つの放送メッセージ_m1，_m2について ， cbcast(m1)→ cbcast(m^B 2)ならば ，任意のプ ロセス_pi において_deliveri(m1)

→ deliverB i(m2)^である．✷

本論文では ，以下に定義する_MH間前後関係保存放 送プ ロト コルを提案する．

［ 定義₃（］_MH間前後関係保存放送 ）定義₂の 条件₁， 2^，3の対象をすべてのプ ロセ スではなく，シ ステム上

のすべての_MHに限定し て定義し た前後関係保存放送 を_MH間前後関係保存放送と定義する． _✷

本論文では ，簡単のため ，定義₃のよ うに ，_MHの みが 放送要求を出し ，_MHのみに メッセージを配達す ることを考え る．_MSSも放送要求を出し ，_MSSへの メッセ ージ 配達が 必要な 場合には ，_MSS内に 一つの

（ 移動し ない ）_MHを仮想的に 考え ，この_MHの放送 要求，メッセージ 配達とし て処理することにより，本 論文のプ ロトコルを適用できる．

3. MH間前後関係保存放送プ ロト コル

3. 1 基本ア イデア

MH間前後関係保存放送を実現するプ ロトコルを提

案する．本プ ロトコルではシ ステム内に存在する_MSS とその識別子が 全_MSSで 利用可能とする．_MHの総

数や識別子は利用可能である必要はない．ただし ，す べて の_MHは ハンド オフを 行 う場合を 除いて いずれ かの_MSSに 接続し ていると 仮定する．また ，ハンド オフは 有限時間内に 完了するものとする．つまり，あ る_MHで_disconnectが 生起し た 場合 ，有限時間内に 必ずconnectが その_MHで 生起すると 仮定する．

Birman^はMHを含まない分散シ ステム上の前後関

係 保存 放送プ ロト コル を 提案し て いる_[4]．こ のプ ロ ト コルはベクト ル 時計_[2]のア イデ アを 次のよ うに 利 用し て いる ．シ ステ ム内のプ ロセ スを _{p1, p2,· · · , pN}

（_N は総プ ロセス数 ）とする．プ ロセス_piが 放送メッ セージmを放送するとき，ベクトル_(v1, v₂,_{· · · , v}N) をヘッダ として_mに添付する．ここで ，各_{vj(j |= i)} は ，_piが_mの 放送要求を 行 う前に _piで 配達され た pjの放送し た放送 メッセージの 個数であり，_viは_m を 含めて _piが 放送要求を 行った 放送 メッセージ の 個 数を 意味する ．mを 受信し たプ ロセ スは ，pi^{の 放送}

し た_{vi− 1}個，各プ ロセ ス_{pj(j |= i)}の放送し た_vj 個の 放送 メッセージ を 配達するまで_mの配達を 延期 することにより，前後関係保存放送を実現する．

Birmanのプ ロト コルをその まま分散移動シ ステム

上の_MHへ適用すると，各メッセージに 付加するヘッ ダ は_Nmh 次ベクトルとなり，前後関係保存放送を 実 現するための通信オーバヘッド が 非常に大きい．また ， MHのハンド オフを考慮し ていないためいくつかの問 題点が 発生する．そこで ，まず_MHのハンド オフが 発 生し ない場合について ，メッセージのヘッダ サイズを 減らす方法を考案する．その後，_MHのハンド オフに 伴う問題点とその対策法を示す．

分散移動シ ステムは ，_MSSと_MHによる階層構造 をなし ている．すなわち，_MHが 他の_MHと メッセー ジを交換するときは，必ず_MSSを介してのみ行う．更 に ，_MHと_MSSの 間の 通信チャネルでは ，メッセー ジは 送信され た 順番に 受信され る．し たが って ，_MH の ハンド オフが 発生し な い 場合は ，_MSS間に おいて 前後関係保存放送を行うことで ，_MH間の前後関係保 存放送を実現することができる（ 図₂）．

MSS間前後関係保存放送に おいて_{MSS sj} の放 送

メッセージ_mの放送要求イベントを_{mss cbcastj(m)}， 配 達 イベン ト を mss deliverj(m)^{と 表す．あ る二つ} の_{MH h1}，_h2 が それ ぞ れ_{MSS s1}，_s2 に 接 続し て い る と き に ，放 送 メッセ ー ジ _m1，_m2 を そ れ ぞ れ 送 信し た と き ，_cbcast1(m1)

→ cbcastB 2(m2)^{が 成 り} 立 つな らば ，_{mss cbcast1(m1)}

→ mss cbcastB 2(m2)

図2 MSS 間前後関係保存放送の利用 Fig. 2 Application of causal broadcast on MSSs.

も 成 り 立 つ ．こ の と き ，_MSS間 前 後 関 係 保 存 放 送 は すべ て の_{MSS sj} に つ いて mss deliverj(m1) →^B mss deliverj(m2)を保証するため ，すべての_{MH hi}

について_deliveri(m1)

→ deliverB i(m2)^{が保証され る．} MSS間前後関係保存放送を実現するために_Birman

のプ ロト コルを用いると ，各放送 メッセージに付加す るベ クト ル の 次 元は _Nmss と な り，ヘッダ サ イズが MH^の数Nmhに依存し ないプ ロト コルを実現できる．

3. 2 ハンド オフ への対応

MHのハンド オフに 対応するために ，前節の基本ア

イデ アを以下のよ うに 拡張する．

a.配達 メッセージ の重複・欠落の回避：_{MH hi}が MSS sj ^{か ら} MSS sk へ ハンド オ フ され た と す る ． MSS間に おけ る メッセージ 交換は 非同期であ るため ，

ある時点において_{MSS sj}と_{MSS sk}の配達済み放送 メッセージは 一般に 異なる．このため，_hiが 放送 メッ セージ _mを_sjから 受信し た 後，ハンド オフ先の _sk から も更に _mを 受信し てし ま うと，_hiは_mを 重複 し て配達し てし まうことがある（ 配達 メッセージの重 複 ）．また ，ある放送 メッセージ _m

′

が_sjで 未配達で あり，_hiのハンド オフ 先の_skで 既に _m^′が 配達済み であるとき，_hiは永久に_m^′を受信・配達ができない

（ 配達 メッセージの欠落 ）ことがある．

配達 メッセージの重複，欠落を回避するために ，各 MSS sj^はsj^{に接続している各}MH hi^{で配達済みの放}

送メッセージ 数を表す_Nmss次ベクトルRECV_j[hi] を 管理する ．ここで ，RECV_{j[hi][sk] (sk∈ MSS)} は_{MSS sk}から放送された メッセージのうち，既に_hi へ送信された放送メッセージの数を表す．RECV_j[hi] を用いることにより，_hiで配達され るメッセージの重

複，欠落は 容易に 回避できる．ただし ，メッセージの 欠落を回避するために ，各_{MSS sj}で 配達済みの 放送 メッセージをキューDELIV MES_jに配達順に保存 する．

b.メッセージ の 前後関係非保存の回避：_{MH hi}が MSS sj^からskへハンド オフされたとする．また，hi

は_sjへ放送メッセージ_m1を送信した後，_skへハンド オフされ ，更に_skへ放送メッセージ_m2を送信したと する（ 図₃）．このとき ，_cbcasti(m1)

→ cbcastB i(m2)

という前後関係が 成り立つため ，_m1は_m2 より先に 各_MSSで 配達され なければ ならない ．し かし ，基本 ア イデアにおけ る放送メッセージに添付するヘッダは ， MSS間放送における前後関係のみ表し ており，同一の MH^{が 異な る}MSSに 対し て送信し た放送 メッセージ

間の 前後関係を 表し て いな い ．そのた め ，別の_MSS では_m1 より前に_m2が 配達され ることがある．

上記の問題を回避するために ，次のようにプロトコル を拡張する．各_{MSS sj}は次に送信する放送メッセージ に先行する放送メッセージ数を_Nmss次のベクトルによ って_MSSごとに管理している．このベクトルを_SENTj とする．_Mkを_{MSS sk}の送信し た放送メッセージの 集合とすると，sj^でmss cbcastj(m)^{が 生起し たとき} には ，各_{MSS sl}に 対し て ，_{SENTj[sl] = |{m}

′|m^′∈ Ml∧ mss cbcastl(m^′)→ mss cbcast^B j(m)}|^{が 成り} 立つものとする．_hiがハンド オフの前後で送信し た放 送メッセージの前後関係を保存するためには，各_MSS sl ^{に 対し ，}hi の ハンド オフ 直後の _SENTk[sl]の 値

が ，_hiのハンド オフ 直前の _SENTj[sl]以上となれば 十分である．そこで ，ハンド オフ 時に 移動情報を用い て_SENTjの値を_skへ伝え ，_skは ，各_{MSS sl}に対 し て，_SENTk[sl] := max(SENTk[sl], SENTj[sl])^を 実行し _SENTkを更新する（ 図₃）．

この よ うに_{MSS sk} に おいて _SENTkを 更新する

図3 ハンド オフ時のSENT の転送 Fig. 3 Transfer of SENT in the handoff procedure.

と，例えば ，_{MSS sj}で配達済みの メッセージがsk^で

未配達の場 合 ，_SENTkが _sk で 配達済みの 放送 メッ セ ージ 数より も 大き く な るこ とが あ る ．そこ で ，_sk で 配 達 済み の メッセ ージ 数を 管 理 す る 別のベ クト ル DELIVkを用意し て，配達の実行・延期の判断に使用

する．

3. 3 配達済みキューからの放送メッセージ の削除 配 達 メッセ ージ の 欠 落 を 避け るた め に 各_{MSS sj} にDELIV MES_jを導入し たが ，すべての放送 メッ セージ をすべての_MSSで 保存するためには 膨大な 記 憶容量を必要とする．そこで ，提案するプ ロトコルで は ，各メッセージのヘッダに 更に Nmss^{次ベクトルを}

加えることで ，すべての_MHで配達済みと 確認された 放送 メッセ ージ を キューDELIV MESから 効率良 く削除する．

各_{MSS sj}は新たな放送メッセージを他の_MSSへ送 信する際に ，接続し ているすべての_MHで配達済みの 放送メッセージを表す_Nmss次ベクトル_REDUCEを 放送メッセージに添付する．ここで，_REDUCE[sk]は， sjに 接続し ているすべての_MHで 受信済みの ，_MSS skから 送信され た 放送 メッセージ 数を 表す．各_MSS sj^{は受信した}REDUCE^を配列RECV RDCj[MSS]

で管理する．_{RECV RDCj[sk]}は_sjが_{MSS sk}から 受 信し た_REDUCEの 最 大 ベ クト ル と す る ．_sj は sk が 送 信し た 放 送 メッセ ー ジ を 配 達 す る と き に ， RECV RDCj[sk] を 更 新し ，す べ て の_MHで 配 達

済みと 確認できた放送 メッセージ をDELIV MES_j から 削除する．ただし ，_{MH hi}が_{MSS sj}から_MSS sk へ ハンド オフされ ると き ，_hi で 配達済み放送 メッ セージを表す_RECViが 移動情報を用いて_sjから_sk へ送られ るが ，_RECViが_sjにも_skにも存在し ない 瞬間が 生じ るため，_hiの配達済み放送メッセージの情 報が _sj と_sk のど ちらの メッセージ の_REDUCEに も反映されず，_hiで未配達の放送 メッセージが 削除さ れ てし ま う可能性が ある ．そこで ，_sj は_RECVi を sk^{へ送った後，}sk^がRECVi^{を受け 取ったこと（}sk

上の_acceptの 生 起 ）を 確認し てから ，_sj は_RECVi を 削除する ．以上の手法に より，すべて の_MSSが 適 当な頻度で 放送 メッセージ を送信することが 保証され ていれば ，すべての_MHで配達済みの放送メッセージ をDELIV MESから 削除できる．

3. 4 プ ロト コルの詳細

前後関係保存放送プ ロト コルを ，_MSSと_MHのそ れぞれについて ，イベント 駆動型のプ ログ ラムで 記述

する．あるイベントに 対するプ ログ ラムの実行中に 別 の イベント が 生 起し た 場 合 ，実 行 中のプ ログ ラ ムが 終 了し てか ら それ ら の イベント に 対す るプ ログ ラ ム が イベント の 生 起 順に 実 行され る ．プ ログ ラ ム 中の wait_(e)という記述は ，wait_(e)が 呼び 出され てから

イベント eが 生起するまで ，そのプ ログ ラムの実行が 停止することを表す．プ ログ ラム中の演算_max，_min が 配列に 対し て 適用され た 場合 ，配列の要 素ご とに ， 最 大 値 ，最 小 値を 選ぶ 演 算で あ ると す る ．また ，プ ログ ラム中の任意の二つの_Nmss 次配列（ ベクトル ） V₁^，V₂ ^{に ついて ，}_{∀s ∈ MSS[V1}[s] <_{= V}2[s]] ∧ ∃s^′∈ MSS_[V1[s^′_{] < V2[s}^′_]]が 成り立つとき，V₁< V₂であ るとする ．更に ，プ ログ ラムでは_MSS間の放送を 行 うマクロ命令を利用できるとする．このマクロ命令は ， メッセージ の受信順には 何の保証もし ないが ，送信さ れ た メッセージ は 有限時間内に すべての_MSSで 正確 に₁回受信され ることを保証するものとする．

分 散 移 動 シ ス テ ム に お け る₇種 の イ ベ ン ト の う ち ，プ ロト コ ル 中 で プ ロ グ ラ ム の 駆 動 に 利 用 す る イベン ト は _internal，_receive，_disconnect，_remove， accept^，connect^の 6 種 類 で あ る ．特 に _MHで 生

起 す る イ ベ ン ト _internalの う ち ，放 送 メッセ ー ジ m の 放 送 要 求 が 出 さ れ た こ と を 表 す_MHの 内 部 イベ ン ト を _cbcast(m) とし てプ ログ ラ ム の 駆 動 に 利 用 す る ．receive(p, m) は ，プ ロ セ ス（_MH 又 は MSS^）p^{か ら} m と い う メッセ ージ を 受 信し た こ と

を 表 す．disconnect(old)^，remove(new, mh, P U T )^， accept(old, mh, GET )^，connect(new)^はMH mh^が MSS old^からMSS newへ ハンド オフ され たと きに

この 順番で 生起する イベントである ．ここで ，_{P U T}， GET ^はold^からnewへ送受信され る移動情報を 表

す．以下に ，_{MH hi} の 実 行するプ ログ ラム 中で 使用 する変数を説明する．ここで ，変数の添字はその変数 をもつ_MHの添字に 等し い．

• TELEPOINTi^：hi ^{が 接 続 中の}MSS^{を 指 す．} ただし ，ハンド オフ 処理中で 接続する_MSSが 存在し ないときは 値とし て_nullを使用する． 以下に ，_{MSS sj}で 実行するプ ログ ラム中で 使用す る変数を 説明する．ここで ，MSSはシ ステム内に 存 在するすべての_MSSの識別子の集合を表す．また，変 数の添字はその変数をもつ_MSSの添字に 等し い．

• MHj^：MSS sj ^{が 接 続 中 の}MH^{の 識 別 子 の} 集合．

• DELIVj[MSS]^：DELIVj[sk]^はMSS sk^から

の 放送 メッセージ の うちsj^{で 配達済みの 放送}

メッセージ 数（ 初期値：すべての要素が₀）．

• SENTj[MSS]：放送メッセージの前後関係の管 理に使用．_MSS間で交換する メッセージのヘッ ダ となる（ 初期値：すべての要素が₀）．

• RECVj[MHj][MSS]^：RECVi[hi][sk]^はMSS sj^{と 接続中の}MH hi^{で 配達され た ，}MSS sk

から 送信され た放 送 メッセージ の 数（ 初期値： すべての要素が₀）．

• DELIV MESj^：MSS sj で 配 達 済 みの 放 送

メッセージを ，配達順に 保存するキュー（ 初期 値：空キュー ）．要素の順序を保存し たまま，任 意のキューの 要素を削除可能であるとする．

• WAITINGj^：MSS sjで 受信され たが ，前後 関係を 保存するために_sjでの配達を 延期し て いる放送 メッセージ を保存するバッファ．

• MOVINGj^：MSS sj^から別のMSS^へハンド オフされ たが ，ハンド オフ 先の_MSSとの 接続 を 確認し ていな い_MHの識 別子と その_MHに 対する_RECVの₂項組を 要素とする集合（ 初 期値：_∅）．

• RECV RDCj[MSS] ^： RECV RDCj[sk] ^は MSS sj^がMSS skから受信し たベクトル_RE- DUCE（ 削除可能な放送 メッセージ の情報 ）を 表す（ 初期値：すべての要素が 零ベクトル ）．

 MSS sjで 実行するアルゴ リズム_ 1. receive(hi, m): /∗ hi^{からm の放送要求}∗/

SENTj[sj] := SENTj[sj] + 1; REDUCE:= DELIVj;

foreach(mh, RECV ) ∈ MOVING_j do REDUCE:= min(REDUCE, RECV ); (SENTj,REDUCE, m) をすべての MSS へ放送; 2. receive(sk,(S, R, m)) :

/∗ Deliver Check 開始 ∗/ if S[sk] = DELIVj[sk] + 1 and

∀mss ∈ (MSS − {s_k})[S[mss] <_{= DELIV}j[mss]] then begin/∗ 配達処理 ∗/

foreach mh∈ MHj ^do

ifRECVj[mh][sk] = DELIVj[sk] then begin m を mh へ送信;

RECVj[mh][s_k] := RECVj[mh][s_k] + 1; end;

DELIVj[sk] := S[sk];

SENTj[sk] := max(SENTj[sk], S[sk]); (sk, S, m) を DELIV MESjの最後尾に 追加; foreach(s^′, S^′, m^′)]) ∈ WAITING_j do

(s^′, S^′, m^′) を WAITINGj^から

       取り出し てDeliver Check

（ 配達すれば(s^′, S^′, m^′) を WAITINGjから削除 ）; end else

WAITING_j:= WAITINGj∪ {(sk, S, m)};

/∗ Deliver Check 終了 ∗/

RECV RDCj[sk] := max(RECV RDCj[sk], R); M IN R:= min{RECV RDCj[s]|s ∈ MSS}; foreach(s^′, S^′, m^′) ∈ DELIV MESj ^do

/∗ キューの先頭要素から順に選択 ∗/ if S^′<= MIN R then

(s^′, S^′, m^′) を DELIV MESjから削除; else

break foreach;

3. remove(s_k, h_i,(RECV_j[h_i], SENT_j)): MHj:= MHj− {hi};

MOVINGj:= MOVINGj∪ {(hi,RECVj[hi])}; 4. accept(sk^{, h}i^,(RECVj[hi], S)):

MH_j:= MHj∪ {hi}; SENTj:= max(SENTj, S);

foreach(s^′, S^′, m^′) ∈ DELIV MES_j do /∗ キューの先頭要素から順に選択 ∗/

ifRECVj[hi][s^′] < S^′[s^′] then m^′をh_iへ送信;

RECVj[hi] := max(RECVj[hi], DELIVj); (accept, hi) を skに 送信;

5. receive(s_k,(accept, hi)):

MOVINGj:= MOVINGj− {(hi,∗)};

 MH hiで 実行するアルゴ リズム_ 1. cbcast(m):

m をTELEPOINTiへ送信; 2. receive(mss, m):

deliver(m); 3. disconnect(mss):

TELEPOINTi:= null wait(connect); 4. connect(mss):

TELEPOINTi:= mss

4. _{正当性の証明}

証明のために ，まず 分散移動シ ステムの実行に 現れ るすべての イベント 間の前後関係（

→L^）[8]^{を定義する．} MHでは ，放送 メッセージの放送要求と同時にその

放送 メッセージの送信が 行われ ，放送 メッセージの受 信と同時に 受信し た放送 メッセージの配達が 行われ る ので ，_{MH hi}の放送メッセージ_mに 関する イベント に ついて ，_cbcasti(m)と _sendi(m)，_deliveri(m)と receivei(m)はそれぞれ 同一の イベントとし て扱う．

MSS間の放送に 関する イベント を 次のよ うに 表す． MSS sjにおける放送メッセージ_mの放送要求イベン

ト を_{mss bcastj(m)}とする．_mの放送要求と同時に mの送信が 行われ るので ，_{mss bcastj(m)}と ，_mの あて先が_MSSである送信 イベント _sendj(m)を同一 とし て扱う．ある_MSSから 送信され た メッセージ _m の_{MSS sj}における受信イベント_receivej(m)を特に mss recvj(m)と 呼ぶ ．また ，放送 メッセージ _mの

MSS sj におけ る配達 イベント（sj ^{の内部 イベント ）}

を_{mss delivj(m)}とする．

［ 定義₄（ イベントの前後関係 ）分散移動シ ステムにお］ ける任意の実行を_Eとし ，_Eに現れ るすべての イベン ト の集合を_Eとする．_E上の前後関係（

→L^）は以下

の条件を満たす最小の₂項関係である． 1.同じ プ ロセ スの異な る二つの イベント _e，_e

′

で ， E^において e^がe^′より前に 現れ るとき，_e

→ eL ^′．

2.^{任意のメッセージ}mに関する送受信イベントをそ

れぞれ_send(m)，_receive(m)とすると ，_send(m)

→L

receive(m)^．

3.任意のハンド オフに 対応する四つの イベントにつ

いて ，_disconnect

→ removeL → accept^L → connect^{L ．} 4. ∀e, e^′, e^′′∈ E[(e→ e^{L ′}) ∧ (e^{′ L}→ e^′′) ⇒ e→ e^{L ′′}]

✷ MSS間で交換され る放送 メッセージ_mに 添付され

るベクトルを_SENT(m)と 表す．_SENT(m)に つい て ，次の補題が 成り立つ．

［ 補題₁］任意の実行において以下の性質が 成り立つ．

（ 性 質₁）_sj を 任 意 の _MSS，_m1，_m2 を _sj が 放 送 し た 任 意 の 放 送 メッセ ー ジ と す る ．こ の と き ， mss bcastj(m1) →^{L mss bcast}j(m2) ^{な ら ば ，} SENT(m1)[sj] < SENT (m2)[sj]^{が 成り立つ．}

（ 性 質₂）_sj を 任意の_MSS，_m1 を 任 意の 放送 メッ セージとする．このとき，_{1 <= a <= SENT (m1)[sj]}な る 任 意の _aに 対し ，_{MSS sj} が 放 送し た メッセージ m₂が 存在し ，_{SENT(m2)[sj] = a}が 成り立つ．

（ 性 質 ₃） _m1，_m2 を 相 異 な る 放 送 メッセ ー ジ ， sk ^を m1 ^{を 放 送 し た} MSS と す る ．こ の と き ，_{SENT(m1)[sk] <= SENT (m2)[sk]} な ら ば， SENT(m1) < SENT (m2)^{が 成り立つ．}

［ 補 題 ₂］_m，_m

′

を 任 意 の 放 送 メッセ ー ジ と す る ．_cbcast(m)

→ cbcast(mB ^′)^{ならば ，}SENT(m) < SENT(m^′)^{が 成り立つ．}

（ 証明 ）_cbcast(m)

→ cbcast(mB ^′)^{より，放送メッセー}

ジ の 連鎖 _{m1 (= m), m2,· · · , mq (= m}^′₎ が 存 在し ， 各_{p(1 <}= p < q)に 対し て次のいずれかを満たす_MH hi^{が 存在し ている．}

1. cbcasti(mp)→ cbcast^B i(mp+1)^． 2. deliveri(mp)→ cbcast^B i(mp+1)^．

いずれ の 場合に も ，_SENT(mp) < SENT (mp+1)^が 成り立つことを示せば 十分である．

（₁の 場 合 ）_hi が _mp を _{MSS sj} へ ，_mp+1 を MSS sk へ 放 送し た と す る ．_{sj = sk} の 場 合 ，_sj

は mp^，m_p+1 の 順 に hi か ら メッセ ージ を 受 信 す る の で ，_{mss bcastj(mp)}

→ mss bcastL j(mp+1) ^で

あ り，性 質 ₁よ り _SENT[mp] < SENT [mp+1]^が 成 り 立 つ ．_{sj = s| k} の 場 合 ，_sj が _mp を 放 送し て か ら _sk が _mp+1 を 放 送 す る ま で に ，_sj か ら sk ^{ま で ，}hi の ハ ン ド オ フ の 連 鎖 が あ る ．hi ^は

σ1(= sj), σ2,· · · , σb(= sk)の順にハンド オフされた とする ．ここで ，_{σa (1 <= a <= b)}は_MSSであ り_σa のもつ_SENTを_SENTσ(a)と表す．各_{a(1 <}= a < b) に 対し て，_hiが_σaから_σa+1へハンド オフされ ると き，_σa+1は移動情報として_σaから_SENTσ(a)を受け 取り，_SENTσ(a+1):= max(SENTσ(a)^,SENTσ(a+1)) とし て _SENTσ(a+1) を 更 新 す る ．よって ，_hiが _sk へ ハンド オフされ たとき，_{SENT(mp) <= SENTk} で あ る ．こ の 後 ，_sk は _SENTk[sk]を₁増やし てから m_p+1^{を放送するので ，}SENT(mp) < SENT (mp+1)

が 成り立つ．

（₂ の 場 合 ）₁ の 場 合 と 同 様 に ，_{SENT(mp) <} SENT(mp+1)^{が 成り立つ．} _✷

RECVj[h]^{は ，}MH h^{が 接続中の}MSS sj^{が もつ}

変数であるが ，_hが 別の_{MSS sk}に ハンド オフされ る と_RECVj[h]の値はそのまま_RECVk[h]とし て引き 継がれ ，_RECVj[h]は 破棄され る．つまり，_hの接続 中の_{MSS sj}のみが _RECVj[h]をもつため ，この 変 数を単に_RECV[h]と表す．

［ 補 題₃］_m を 任 意の 放 送 メッセ ージ ，_hを 任 意の MH^{とする．このと き，}hはmをたかだか₁回受信

する．

［ 補 題₄］_m を 任 意の 放 送 メッセ ージ ，_hを 任 意の MH^{とする．このと き，}h^はm^{を少な くとも}1^回受

信する．

補題₄を証明するために 次の補題₅を示す．

［ 補 題₅］ _mを 任 意の 放 送 メッセ ージ ，_s を 任 意の MSS^{とすると ，}s^はいずれm^{を配達する．}

（ 補 題₅の 証 明 ）あ る_{MSS sj} で 配 達 され な い 放 送 メッセ ージ _mが 存 在す ると 仮 定し ，矛 盾を 導 く． 一 般 性を 失 うこ とな く，sj が 配達し な い メッセ ージ の 中 で ，_m が 極 小 の ヘッダ _SENT(m)を も つ と す る ．_m を 放 送し た_MSSを _sk とし た と き ，永 久に SENT(m)[sk] > DELIVj[sk] + 1^{，あ るいは ，}∃s ∈ (MSS − {sk})[SENT (m)[s] > DELIVj[s]]^{が 成 り} 立つ．いずれ の場合も性質₂，₃より，_SENT(m

′_{) <}

SENT(m)^{なる放送メッセージ}m^{′が 存在する．}m^の 極小性より_SENT(m

′) < SENT (m)^なるsj^{が 配達}

し ない放送 メッセージm^′が 存在することが 示せ，m のヘッダ の極小性に 矛盾する． _✷

（ 補題₄の証 明 ） _{MH h}は 永久に 放送 メッセージ _m を 受信し ていな いと 仮定し て矛盾を 導く．_{MSS sj}で mの配達が 行われたときに_hが_sjと接続し ている場

合，hはsj ^からmを 受信する．よって ，hが_MSS sj と 接 続し て い ると きに sj ^で m の 配 達は 行われ

ていな い．ここで ，補題₅よりすべての_MSSはいず れ _mを 配達す るので ，_hは まだ _mを 配達し ていな い_{MSS sk}から ，既に_mを配達済みの_{MSS sl}へハ ンド オフされ る ．_mが _hで 配 達され な いこ とか ら ， こ の ハンド オフの 完 了時 点で ，sl^{の 保持す るキュー}

DELIV MES_lから_mは削除されている．つまり，_m を放送した_MSSを_spとするとすべての_{MSS sj}から SENT(m)[sp] <_{= REDUCE}j[sp]^{な る}REDUCEj ^を

受信している．_skで_{SENT(m)[sp] <= REDUCEj[sp]} が 成り立つた めにはsk^{で 既に} mが 配達され て いな ければ な ら な い ．_hの ハンド オフ 直 前の 時 点で ，_sk は _mを まだ 配 達し て い な いの で ，_hの ハンド オ フ 発 生 後に _sk は _m を 配 達し たこ とに な る ．し かし ， hの ハンド オ フが 開 始し てか ら ，ハンド オフが 完 了

し た こ と を 伝え る メッセ ージ を sl か ら 受 信 す る ま で は ，_sk の 保 持 す る MOVING_k に は RECV_[h] が 存 在 す る ．_h は _m を 受 信し て い な い こ と か ら RECV_[h][sp] < SENT (m)[sp]^{が 成り立つため ，}sk

が_hのハンド オフ中に_slへ送信し た_REDUCEkに ついて ，_REDUCEk[sp] < SENT (m)[sp]^{であること} が いえ る．これは ，_slが_hのハンド オフ 完了時点で m^{をキューDELIV MES}lから 削除し て いる 条 件

に 反し ている． _✷

［ 定理₁］_m，_m^′ を 任意の放送 メッセージ ，_hiを 任 意の_MHとする．_cbcast(m)

→ cbcast(mB ^′)^{が 成り立} つならば ，_deliveri(m)

→ deliverB i(m^′)^{が 成り立つ．}

（ 証明）まず，任意の_{MSS sj}に対し ，mss deliverj(m)

→ mss deliverL j(m^′)が 成り立つこ とを 示す．補題₂

よ り _SENT(m) < SENT (m^′) が 成 り 立 つ ．補 題₅ よ り，_sj は _m，_m

′

を い ず れ 配 達 す る ．こ の と き ， mss deliverj(m)→ mss deliver^L j(m^′)^{とな るのはプ} ロトコルより明らか．補題₃，₄より，各_MHはすべて の放送メッセージを正確に₁度配達する．ある_{MH h} でより前に_m^′が 配達されたと仮定し て，矛盾を導く． すべての_{MSS sj}は_m

′

の配達前に_mを配達するため， これらの メッセージはキューDELIV MES_jにおい て，_m，_m

′

の順に₁回ずつ現れ る．_hがある_{MSS sj}