分散処理を勉強した記録～その18～

この記事は、
「分散処理システム」著：真鍋義文　森北出版株式会社
を参考にしています。

今回は、「因果順序通信アルゴリズム」についてのお話です。
メッセージの前後関係を保つ因果順序性を保証するには、
各プロセスが「どのメッセージを配送したか」という情報を保持する必要があります。

ここで、nは全体のプロセス数になります。
Vの要素はそれぞれ初期値は「0」です。

ここで、とあるプロセスP2がメッセージを送信する例を想定します。

プロセスP2がメッセージを送信すると、
V[2]の値を+1します。
この際、P2自身にもメッセージを送信します。

受信するプロセスPjがメッセージを受信する時、
次の関係を満足するまで配送を遅らせます。
任意のk(1 <= k <= n, k != i)に対し、
V(m)[k] <= V[k]　かつ　V(m)[i] = V[i] + 1

この条件を具体的な例に当て嵌めてみます。

V(m)[k] <= V[k]について、i=2, n=10, k=5とすると、

ここで、P2において
V(m)[5] <= V[5]　は　1 <= 0
となるので、P2のV[5]が1になるまで
P2は自分のメッセージを送る前に、
P5からのメッセージを受信する必要があります。

V(m)[i] = V[i] + 1について、
i=2, j=3,
受信側プロセスP3のベクトルV[2] = 0,
受信側プロセスP3の受信メッセージV(m)[2] = 2とすると、

P3はP2からのメッセージを2回分受信していないことになります。
よって、P3は自分のメッセージを配送する前に、
P2のメッセージを2回受信する必要があります。

今回はここまでです。ありがとうございました。