論理クロック

分散システム

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/dsys-1997/1998-02-10 /logical-clock.html
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■論理クロック

◆クロック

タイマ割込み。１秒間に５０回〜６０回割込みがかかる。 水晶発振か、電源の周波数を使う。 一回の割込みを、clock tick という。

単一のコンピュータでは、水晶でも問題がないが、複数のコンピュータでは、 クロックの進み方(clock skew)が違うので、だんだんずれてくる。

◆論理クロックと物理クロック

論理クロック

内部で一貫性がとれていればいい

物理クロック

実際の時計とおおきくずれていてはいけない

◆Lamportの論理クロック

「a→b」は、「aはbの前に発生する」

• もしaとbが同じプロセスの事象で、bより前にaが生じるなら、a→bであ る。
• もしaがあるプロセスがあるメッセージを送信したという事象で、 bが別のプロセスでそのメッセージを受信したという事象なら、a→bである。 (送信まえには受信できない。 メッセージの到着には、有限の時間がかかるので、送信と同時にも受信できな い。)

「a→bかつb→cならばa→cである」

平行性がある：「x→y」も、「y→x」も両方とも成り立たないことがある。 xとyが別々のプロセスで発生して、それらの間でメッセージを交換しない時な ど。 どちらが先に起きたかということを言えない（言う必要がない）

◆時間値C(x)

• a→b ならば、C(a)＜C(b)
• 常に前進する。逆戻りしない。

◆Lamportのアルゴリズム

• 同じプロセスにおいてaがbの前に発生すれば、C(a)＜C(b)となる。
• もしaおよびbが同じメッセージの送信と受信の事象ならば、C(a)＜C(b) となる。
• すべての事象a,bについて、a≠bならば、C(a)≠C(b)。 (total ordering)