Time, Clocks, and the Ordering of Events in a Distributed System - Leslie B. Lamport
分散システムにおける時間、クロック、イベントの順序について - 2000年ダイクストラ受賞
物理学のアナロジーで分散システムを捉えた古典的論文
CSは突き詰めると物理学(相対論)になってくる
光の早さによるメッセージパッシングの速度的制限や非決定的なメッセージングパッシングの振る舞い複数の並行する主体が観測する際の問題、観測するまで結果が確定しない等…
突き詰めると分散システムは量子論的とも言えるかもしれない
プロセスを観測者として捉えてメッセージングを光の伝達として捉えるような相対論的アプローチ
1つのプロセスは順序のあるイベントの集合といえる p1, p2, p3, p4...
happend before 関係を→として定義する
同一プロセス内でイベントaの後にイベントbが起こったとするなら a → b
あるプロセスからイベントaが別のプロセスでbとしてメッセージが受け取られたとするなら a → b
a → b, b → cが成り立つなら a → c
並行の定義
もしあるイベントp3, q3がお互いに何の影響もなく発生したのならそのイベントは並行している
何らかの因果関係 →が存在するイベント同士は並行ではない
また因果関係→が存在しないのならば原理的にはどちらのイベントが最初に起こったかということは定義出来ない(ネットワークの遅延、物理学で例えると何か光の速度に差がある場合それぞれの観測者から見たお互いのイベントの順序と第三者が見たイベントの順序は同一ではない。光速船におけるウラシマ効果みたいな話)
バージョニングというのは論理的な時計として定義出来るかもしれない
実際に時間を進めるという実装をすることなく、あるイベントが起こる度に前後関係のあるカウンターが進められる
a → b なら C<a> < C<b>
論理クロックの一種としてランポートタイムスタンプアルゴリズムと呼ばれる
アルゴリズム
あるイベントが起こる時にプロセスはメッセージ送信前にローカルの論理クロック(カウンター等)をインクリメントする
code:pseudo
# event is known
time = time + 1;
# event happens
send(message, time)
メッセージの受信では受け取った論理クロックもしくは自身の現在のクロックの大きい方をインクリメントしたものがもう一方のプロセスでの論理クロックとしてメッセージの受領を完了する
code:psuedo
(message, time_stamp) = receive();
time = max(time_stamp, time) + 1;
マルチプロセッサやマルチスレッドにおいては同時に複数のプロセスが動作するため、それぞれのプロセスのユニークなPID等を用いて論理クロックをユニークにする
分散システムにおいては原理的に複数の主体においてクロックを同期するというのは不可能。それ故に論理クロックのような概念が必要になる
分散システムにおいて部分的順序が分かるのであれば、同じアルゴリズムで全てのイベントの順序を把握することも可能
タイムスタンプやカウンターは2つのプロセスにおいて同じ値になる場合もあるかもしれないが、論理クロックのアルゴリズムに従う限りは決定的に振る舞うことが出来る
論理クロック時間C(a) < C(b) だからといって現実時間でaがbの前に起こらなくても問題ない。現に分散システムにおいてはネットワークの遅延等により現実時間で先行するように見える場合もある
論理クロックのVariantとしてVectorクロックというものもある
分散データベース(e.g. Dynamo) を実装する際にも用いられる