Causal Ordering of Messages (メッセージの到着を送信順に整列させる)

Causalとは直訳すると「因果関係の」、Causal Orderingは「因果関係の順番」です。 これは、並列システムがどういう動作をしているのかを把握したり、 状態を記録する際に大事になってくる概念です。 普通に設計したシステムはCausal Orderingを満たしていないことが多いですが、 これを満たすようにシステムを制限することで、システムの動作や アルゴリズムの見通しが良くなります。
ここでの説明は、 という順で進めていきます。
☆なお、ここで言う時間は全てVector Timeとします。

Causal Ordering of messagesとは

まずは定義
Causal Orderingは「因果関係の順番」となりますが、 まずよく出てくるのはCausal Ordering of eventです。 これはCosistency(一貫性)とも言われ、状態の記録では非常に大事になります。 この意味は、因果関係がちゃんとした順で起こるということで、 「同一プロセッサの中で、実時間でイベントAよりBが先に起こった場合、 clockA < clockBが成立する」 及び 「あるメッセージを送った時点Sと、それが受信された時点Rについて、 clockS < clockRが成立する」 ということです。 これらはここで考えるクロックの性質そのものです。
さて、ここで問題にするのはCausal Ordering of messagesです。 これは一つのメッセージの送信受信の関係ではなく、 二つ以上のメッセージについての関係を考えます。 メッセージm1とm2について、m1の送信時刻をtm1s、受信をtm1r、 同様にm2の送受信をtm2s, tm2rとするとき、
「tm1s < tm2s なら (tm1r < tm2r 又は tm1r || tm2r )」 かつ 「tm1r < tm2r なら (tm1s < tm2s 又は tm1s || tm2s )」
が成り立つなら、Causal Oredering of messagesが成立していると考えます。
簡単に言うと、「Vector Clock的に先に送信したメッセージが後に着くことはない」 ということです。
具体例
具体例を見てみます。
メッセージの送信・受信を調べてみると、 となっていて、 送信の時はtA < tBなのに、受信の時はtD > tC と順番が逆転しています。 つまり、メッセージA-DとB-Cとの間でCausal Orderingが乱れています。 この場合は送信と受信が同じメッセージの間で追い抜きが起こっているので、 比較的容易に分かります。
次はもう少し複雑な例を示します
この場合も各メッセージを調べてみます。 この場合は送信と受信を共に同じにするメッセージはありません。 しかし、Vector Clockを比較するとB-EとA-K、F-J,とA-Kの間で Causal Orderingが崩れていることが分かります。
どうすればCausal Orderingを維持できるのか
では、どうすればこのCausal Orderingを維持できるのかを 考えてみます。 …といっても原理は大したことはなくて、速く到着しすぎたメッセージを 退避させ、新しいメッセージを受信した後、早く付いたメッセージを 受信するか判断し、良ければ受信する、というものです。 先の例だとこうなります。
上のXが付いた所で何らかの判断をして、メッセージの到着を止めておきます。 そして、A->Dのメッセージが着いた後で、これを受信すればよいのです。
とはいえ、どのような場合に退避が必要なのかは今までのVector Clockを 見るだけでは分かりません。そこで、その他のメッセージを用いた プロトコルが考案されています。これを順に述べていきます。

Birman-Schiper-Stephenson Protocol

このアルゴリズムは、メッセージが全てbroadcast(あるプロセッサから 全プロセッサへの送信)の場合に用いることができます。
Vector Clockを少し変えることでそのメッセージを受信してもいいか、分かるようになっています。
アルゴリズムの説明
用いるのはVector Clockと同様、プロセッサ数個の要素を持つベクトルです。 メッセージにクロックを添付するのも同じです。 ただし、値の増加のさせ方が少し異なります。
☆以降、メッセージを送信するプロセッサをPi、受信するプロセッサをPjとします。 决まりだけ書くとややこしそうですが、要は自分より前に送信されたメッセージが 全て受信されるまで受信を延期するわけです。その条件が上に挙げたものです。
適応例
ともあれ、例を見れば分かってもらえると思います。
先程と同じ図ですが、ピンク色で書かれているのはVector Clockではなく、 BSSのクロック(?)です。
ポイントはメッセージを送信する*前に*クロックが上がること、 メッセージの送信でのみクロックが増加すること、 Cではメッセージのクロックが(2,0)に対しプロセッサ[1]のクロックが (0,0)なので、上の条件に違反し受信が延期されていることです。

Schiper-Eggli-Sandoz Protocol

上に述べたBSSプロトコルは単純ですが、全てのメッセージがbroadcastでないと 使えないという致命的な欠点があります。 この解決としては、1:1のメッセージ送信についても、元々メッセージが送信されて いなかったプロセッに対しダミーのメッセージを送信する、なども考えられますが、 メッセージの送信自体を増やすのはあまり好ましくありません。
これに対し、ここに述べるSchiper-Eggli-Sandoz Protocolは少し複雑ですが、 あらゆるメッセージ送信に対し使えます。
アルゴリズムの説明
このプロトコルでは、各プロセッサはVector Clockと共に、自分以外のプロセッサの数だけ Vector Clockを格納できる配列を持っています。 プロセッサiは自分のVector ClockであるtPiの他に、Vector Clockの配列 V_Piを持っています。 プロセッサ数がn個、それぞれをP0,P1, .. ,Pi, .., P(n-1)と呼ぶと、各プロセッサが V_Piという配列を持っていまて、V_Piの要素はV_Pi[0],V_Pi[1],...V_Pi[n-1]まで、 ただしV_Pi[i]はありません。これらの要素にはVector Clockが入り、初めは空です。
以降、この配列をどう用いるかを述べていきます。 なお、メッセージを送信するプロセッサをi、受信するプロセッサをjとします。 …文字で書くとややこしいですが、要はメッセージのVector Clockが V_Pj[i]より古ければメッセージを受信し、配列をマージし、 条件を満たす受信待ちメッセージがあれば受信するわけです。
適応例
想像できるように、このプロトコルではたくさんの数字が出てきて 人力でシミュレーションするのはけっこう大変でした。
ピンク色のものがSESの配列の要素、緑色はVector Clockです。 SESの配列は自分に当たる要素が抜けているので、ここに Vector Clockを入れたような格好ですが、更新する手順は全く異なります。 (-,-,-)となっているのは、SESの配列が空であることを示しています。
こちらは複雑なので順を追って見てみます。 まず、緑のVector Clockは先程と同様に変化します。JでXが付いているところは メッセージの受信が延期されているので、クロックは変化しません。
まずAですが、メッセージが送信され、その後上から3番目の段に メッセージに添付されたクロック、(1,0,0)が格納されています。 なお、送信されたメッセージに、このピンク色の(1,0,0)は無いのが ポイントです。 次のBで送信されたメッセージには、三段目に(1,0,0)が付いています。
Eでの到着では、Bからのメッセージに[1]に当たるクロックが含まれていないので そのまま受信されます。その後、ピンク色のSES配列がマージされます。 ここで、緑のVector ClockがピンクのSES配列にマージされたりはしないので、 注意して下さい。
最後に、Causal Ordering of messasgesのチェックが働く場合です。 Jでは、メッセージが[2]の成分(上から三段目)を含み、かつ その値(1,0,0)がJ直前のクロック(0,0,2)とConcurrentで 「古くはない」ため、メッセージの到着は延期されます。 KでAからのメッセージが到着すると、 メッセージの値(1,0,0)とKのクロック(1,0,3)の比較になり、 (1,0,0) < (1,0,3)より受信が行えるようになります。