A note on Lamport Logical Clock

Lamport の論理クロックのメモ。

プロセス P1, P2 において、イベントを a, b として C(a), C(b) をプロセスのローカルな論理時間を, X -> Y と X < Y をイベントの順序を表現すると決める。 この時、a ≠ b ならば C(a) ≠ C(b)、 a < b ならば C(a) < C(b) も自明。 しかし、C(a) < C(b) ならば a < b は成り立たない。 例えば P1 から P2 へメッセージを2回送信した場合にそれぞれのメッセージを m1, m2 とおく。 この時、P2 が受け取る時に m2 -> m1 の順で受け取る可能性があり、この時 P2 上では C(m2) < C(m1) となり P1 と比較してメッセージの順番が前後することになる。 よって、 C(a) < C(b) でも a < b は言えない。

Comments

comments powered by Disqus