論理時計
論理時計の条件
$ eはイベント
線形時間
各プロセス$ p_iは、線形時間を示す変数$ Lを持つ。
各プロセスが送信するメッセージ$ mは、線形時間を運ぶ変数$ m.Lを持つ。
各プロセスは、以下のイベントを発生させる。
送信イベント
1. $ L = L + 1
2. $ m.L = Lとする
3. $ mを送信する。
$ T(s_i \lbrack m \rbrack)は$ Lとなる
受信イベント
1. $ mを受信する
2. $ L = \mathrm{max}(L, m.L)
3. $ L = L + 1。
$ T(r_i \lbrack m \rbrack)は$ Lとなる。
計算イベント
1. 計算$ eを行う
2. $ L = L + 1
$ T(e)は$ Lとなる。
線形時間の性質
1. $ e_i \Rightarrow e_jならば、$ T(e_i) < T(e_j)である
2. しかし、1.の逆は成り立たないことがある
3. $ T(e_i) < T(e_j)であるとき、$ e_i \Rightarrow e_kかつ$ e_k \Rightarrow e_jとなるイベント$ e_kが存在するかはわからない
よって、線形時間は論理時計の条件1を充足するが、2は充足しない。
ベクタ時間
ベクタ時間の性質
1. $ e_i \Rightarrow e_jのとき、かつそのときに限り、$ T(e_i) < T(e_j)である
論理時計の条件を満たしている
並行関係が保存されているkekeho.icon
2. $ T(e_i) < T(e_j)であるときに、$ e_i \Rightarrow e_kかつ$ e_k \Rightarrow e_jとなるイベント$ e_kが存在するかどうかはわからない
空間計算量が$ O(n) bitsになるので、大規模システムに適さないとされる
いろいろな論理時計
因果関係を捉えつつ、NTPに近い物理時間を反映するクロック どんなんだ?kekeho.icon
偽陽性があるが、ベクタークロックと比べて空間効率がよい
偽陰性があると致命的だと思うけど、偽陽性なら多くのアプリケーションで許容できるんではkekeho.icon
参考
https://www.youtube.com/watch?v=BRvj8PykSc4&feature=youtu.be