並列分散システムでの「クロック」

クロックといっても、ここでいうのは何秒とか何分とかいうものではなく、 プログラムの進度を表す指標みたいなものです。 このクロックは並列システムにおいてプログラムが進んだ道筋を 各プログラムの立場で把握するもので、障害復旧などに役立ちます。 ここでの説明は、 という順番で進めていきます。

ここで考えるクロックについて

「順序関係」「因果関係」を表すのがクロック
ここで述べるクロックの基本は、二つのイベントについて、どちらが先に起こったかわかる というものです。例えば、以下のような順でイベントが起こったとします。
[0]----A--------B--C---
以下、このような線を一定の時間軸、[0]をプロセッサ番号、(n)をクロックとします。 また、軸上のA,B,Cはイベント、tAなどはその時間を表す記号とします。
上のようなシステムで、例えばA-Bの時間はB-Cの時間より長いですが、それは ここでは問題にしません。
一方で、Bという地点はAの結果を知ることができるため、 tA < tBであると考えます。 同様にtB < tCから、 tA < tB < tCとなります。 必要とされるのはこの順序(因果)関係だけになります。
因果関係というのはここではややミスマッチな言葉です。 ひょっとしたら、AでもBでも状態は変化せず、 Bの結果の原因がAにある…とは言えないかもしれません。 しかし、ここでは「プログラムによってはBはAの結果を知り得る」ということで 「因果関係」と呼ぶことにします。
独立したプロセスの場合
先に、順序関係のみを問題にすると言いましたが、この場合はどうでしょうか?
[0]--A--------


[1]--------B-
[0]と[1]は全く関係なく動いているプロセスで、共通のクロックやメモリは持たず、 情報をやりとりするにはメッセージを送り合うしかないものとします。 このとき、上の図ではAの情報はBに伝わっていませんし、逆もありません。 実時間ではAがBより先に起こっているのですが、BはAの結果を見ることはできないので、 AとBに「因果関係」はありません。 よって、AとBは比較しても無意味だと考えます。 繰り返しになりますが、これは決め事で、後々便利なのでここでは意味がないと考えるというものです。 このようなAとBの関係を"Concurrnt State"と言い、記号||で表します。
この「比較が無意味」ということについて、もう少し考えてみます。 もしもし[0]と[1]の二つのプロセスがクロックを共有しているなら、AとBは比較可能になります。 あるいは、二つのプロセスが共通のメモリを持っていて、随時ここを参照しているなら、 BはAの結果を利用することができます。そうすると、 tA < tB という関係が成立します。 しかし、実際には[0]と[1]では共通の時間の基準を持たないため、[0]や[1]というプロセスの 立場にとってみると、AとBの比較は無意味であることが分かると思います。
メッセージ
以下のような並列システムでは、どのように考えればいいでしょうか。
[0]---A-----B--C--
           /
          /
         /
[1]--D--E----F----
これは、Eで何らかのメッセージが送信され、Bでそれを受け取ったことを示しています。 E,Bはそれぞれ「送受信した直後」の状態とします。
まず、明らかに定義として
tA < tB < tC、
tD < tE < tF
の関係があります。また、メッセージの授受が行われていますが、 これについて、
tE < tB
と定義します。
さて、残りの関係はどうでしょうか? 先と同様、確かに実時間ではAはDより後ですが、この比較は意味を持ちません。 よって、クロックが満たすべき条件は先の式だけになります。
まとめ
ここで言うクロックは、以下の二つの原理に基づいています。 これは、イメージ的に言うと 「tA < tB」のとき「BはAの情報を見ることが出来る」 となります。
すると、二つの時間tAとtBの関係は、以下の四つがあります。 (この他にも、=と<のorを取って<=、同様に>=や!=(not equal)も定義できます)
このように任意の二つの項についての関係が「=, >, <, ||」の四つで表せるものを 半順序関係といいます。 これは普通のスカラーだけでは、「比較不能」という状態が作れないのでうまく表わせません。 (スカラーは二つの数について一意に順序が決定できる全順序関係を持つため) このため、後の方でVector Timeが導入されることになります。

Vector Time …ちゃんと半順序を表す

では、本命のVectorat Clockです。 ベクトルというのは、クロックを一つの数字ではなく、プロセッサの数だけ並べて「ベクトル」とするという意味です。 よって、三つのプロセッサがあればクロックは全て三次元ベクトル、四つあれば四次元ベクトルで表します。 このベクトルを、各プロセッサが「別々に」持っていて、メッセージにもこのVector Clockが添付されます。
ベクトルの中身ですが、感覚的には各要素が各プロセッサのクロックを表しています。 以下、プロセッサを0,1,2、それぞれのプロセッサが持つVector ClockをC0,C1,C2、 CiのVector Clockの要素をCi[0],Ci[1],Ci[2]とします。
また、二つのベクトルV1, V2の比較を定義します。 V1とV2の対応する要素について、全ての要素についてV1の方がV2より大きいとき、V1 > V2であるとします。 また、逆にV1 > V2という関係があるなら、対応する全ての要素についてV1の方がV2より大きいとします。
例えば、以下のような関係が成り立ちます。けっこう感覚的で分かりやすいのでは? このとき、Vector Clockは以下のルールに従うものとします。 では、実例を示します。
この図で、(a, b)のように示されているのがVector Clockです。 矢印の近くにあるのは、メッセージに添付されたクロックです、
まずプロセッサ[1]ですが、E->F->Gは時間の推移に従って後の成分が1ずつ増えます。 Gでメッセージを送信するわけですが、このときFのクロック(0,2)を 添付して送ります。そして、[1]自体のクロックはGでも1増えて(0,3)になります。
さて、このメッセージを受信したBでは、Aのクロック(1,0)とGからのメッセージに 付いてきたクロック(0,2)を比較します。そして、先のルールに従い、前の成分は Aから取り1、後の成分はGから取り2となります。さらに、前の成分に 1を加え、次のクロック(2,2)とします。
C, Dではメッセージの送信がありますが、これもGと同様、送信する直前のクロックを 送ります。そして、Dからのクロックを受けるJでは直前のクロック(0,4)とメッセージの(3,2) を比較し、前の成分は3、後の成分は4に1を加え(3,5)となります。 同様に、Lでは直前の(3,6)とメッセージの(2,2)を比較し、後者に1を足して(3,7)とします。
こうして計算したVector Clockを用いると、二つのイベントの時間的関係を 決定することができます。 地点AとBについて、Vector Clockの値がVA及びVBであるとき、 以下のような関係が成り立ちます。
VA < VB BはAより先に起こった
VA > VB AはBより先に起こった
VA = VB AとBは同じプロセッサで同時に起こった
VA || VB Concurrent State、異なるプロセッサで比較不能な時刻に起こった
例えば上の図でBとHは(2,2)||(0,4)よりconcurrent、 CとKは(3,2)と(3,5)でKが後、などが分かります。

Vector Clockのお手軽版…Lamport Clock

先に述べたように、ここでの「クロック」はスカラーでは完全には表せません。 しかし、この「比較不能」なものにも勝手に順番を決めてよいとすると、 次のような比較的簡単な仕組みで計算することができます。 なお初期値やクロックの増加数は自由ですが、以下の例では 初期値は0、増加数は1としています。 先のVector Clockと比較すると、ベクトルの成分を区別せず、 全て同じ成分を比較したり増加させたりしたのに対応します。
地点AとBについて、Lamport Clockの値がLCA及びLCB、 Vector Clockの値がVA及びVBであるとき、 以下のような関係が成り立ちます。
LCA < LC2 VA < VB又はVA || VB AがBより先に起こっていることはない
LCA > LC2 VA < VB又はVA || VB BがAより先に起こっていることはない
LCA = LCB VA = VB又はtA || tB AとBは同時に起こっているか、比較不能
これについて、以下の例で実際にLamport Clockを計算してみます。
まずプロセッサ[1]ですが、E->F->Gは時間の推移に従って1ずつ増えます。 Gでメッセージを送信するわけですが、このときGの直前のクロック(1)を 添付して送ります。そして、[0]自体のクロックはGでも1増えて(2)になります。
さて、このメッセージを受信したBでは、直前のクロック(0)とメッセージに付いてきた クロック(1)を比較します。そして、大きい方に1を加え、次のクロック(2)とします。
C, Dではメッセージの送信がありますが、これもGと同様、送信する直前のクロックを 送ります。そして、Dからのクロックを受けるJでは直前のクロック(3)とメッセージの(3) を比較し、大きい方(この場合は同じなので3)に1を加え、新しいクロックとします。 同様に、Lでは直前の(5)とメッセージの(2)を比較し、大きい方の(5)に1を加え(6)とします。
このLamport Clockは実装が簡単な反面、数字だけ見ると 比較できない部分まで比較できてしまいます。 例えば上の図だと、BとH,CとHは本来「比較不能」となるべきですが、 見かけ上B < C = Hのように見えます。 しかし、メッセージの到着が送信に先行しないようにする、といった 実用的な用途ではLamport Clockで十分なことも多いようです。