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

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

今回は、「全順序と因果順序の混在アルゴリズム」についてです。
チャットしながらお絵かきできるサービスで、
AさんとBさんとCさんがお絵描きをしています。

Aさんが描画した線を細くするコマンドを実行しました。

AさんのコマンドがBさんとCさんに届いて反映されるまでの間に、
Aさんが「線の細さを調整して」というメッセージをBさんとCさんに送信しました。

Aさんからのコマンドが到達する前に、
Bさんはメッセージを見て線を太くするコマンドを実行しました。

その後、遅れてAさんのコマンドが到達してしまいました。

本来意図した順番に到達するにはどうすれば良いでしょうか。

ここで、「全順序性」と「因果順序性」についておさらいします。
お絵描きに関しては、「全順序性」を保つ必要があります。
あるプロセスPiが受信した順番に、
別のプロセスPnもPiが受信した順番通りに受信する必要があります。
これが全順序性です。

チャットに関しては、「因果順序性」です。
Piが発信した順番通りにPnがメッセージを受け取れればそれでOKなので、
他のプロセスがどの順番で受け取っていようが関係ありません。

これを踏まえた上で、全順序と因果順序の混在するアルゴリズムについて考察していきます。
各プロセスに因果順序性を保証するためのパラメータS, Vがあります。
Sは因果順序性メッセージを送信する際に使用し、
Vは因果順序性メッセージを受信する際に使用します。
Vaは全順序性メッセージを受信する際に使用します。

P3が因果順序メッセージを送信すると、
P3は自身のパラメータSとVaを更新したものをメッセージに付加して送信します。

ここで、Token Holder Processが因果順序メッセージを受信すると、
Token Holder Processは、自身のパラメータV,Vaを更新します。

P2が因果順序メッセージを受信すると、
同様にパラメータV,Vaを更新します。

同様にP1もメッセージを受信してパラメータを更新します。

ここで、P2が全順序メッセージを送信するとします。
P2は自身のパラメータVaを更新し、SとVaをメッセージに付加して送信します。

Token Holder Processが全順序メッセージを受信すると、
Token Holder Processは、自身のパラメータVaを更新します。

その後、Token Holder Processは配信順序メッセージを各プロセスに送信します。

P3は配信順序メッセージを確認してから全順序メッセージを受信します。
その後、パラメータVaを更新します。

同様にP1もメッセージを受信してパラメータを更新します。

最期に、Token Holder Processが全順序メッセージを送信する場合です。
自身のパラメータVaを更新し、配信順序と共にメッセージを送信します。
この際、自分自身にもメッセージを送信します。

P2は配信順序を確認してから全順序メッセージを受信し、
パラメータVaを更新します。

P1とP3もメッセージを受信し、パラメータを更新します。

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