論理時計の条件

$e_{i}$ happend-before $e_{j}$ ( $e_{i} \Rightarrow e_{j}$ )ならば、 $T (e_{i}) < T (e_{j})$ となる (Timestamp Completeness)
- $e$ はイベント
$T (e_{i}) < T (e_{j})$ ならば、 $e_{i} \Rightarrow e_{j}$ (Timestamp Soundness)

線形時間

Scalar logical clocksとも
各プロセス $p_{i}$ は、線形時間を示す変数 $L$ を持つ。
各プロセスが送信するメッセージ $m$ は、線形時間を運ぶ変数 $m . L$ を持つ。
各プロセスは、以下のイベントを発生させる。
- 送信イベント
  1. $L = L + 1$
  2. $m . L = L$ とする
  3. $m$ を送信する。
  - $T (s_{i} [m])$ は $L$ となる
- 受信イベント
  1. $m$ を受信する
  2. $L = max (L, m . L)$
  3. $L = L + 1$ 。
  - $T (r_{i} [m])$ は $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)
2. $T (e_{i}) < T (e_{j})$ であるときに、 $e_{i} \Rightarrow e_{k}$ かつ $e_{k} \Rightarrow e_{j}$ となるイベント $e_{k}$ が存在するかどうかはわからない
空間計算量が $O (n)$ bitsになるので、大規模システムに適さないとされる
システムにおけるプロセス数を $N$ としたときに、各プロセス $p_{i} \in P$ は、 $∣ T ∣ = N$ となるベクター $T$ をタイムスタンプとして保持する。
プロセス $p_{i}$ は計算およびメッセージの送受信イベント $e$ が発生するたびに、 $t_{i} \in T$ をインクリメントする。
また、Lamportの論理クロックと同様にメッセージのペイロードにタイムスタンプを添付する。
タイムスタンプ $T^{'}$ をペイロードに持つメッセージを受信した際には、ベクターのマージ操作 $\forall i : t_{i} := ma x (t_{i}, t^{'}_{i})$ を実行し、これをインクリメント前のタイムスタンプ値として採用する。
なお、ベクター間の順序関係は以下で定義される。 $T < T^{'} ⟺ (\forall i : t_{i} \leq t^{'}_{i}) \land (\exists j : t_{j} < t^{'}_{j})$

Lamport Clock
Vector Clock
Synchronized clocks
- Google Spanner的なやつ
[Hybrid Logical Clock]
- 因果関係を捉えつつ、NTPに近い物理時間を反映するクロック
  - どんなんだ?(kekeho)
  - Logical Physical Clocks
Bloom Clock
- https://arxiv.org/abs/1905.13064
- The Bloom Clock to Characterize Causality in Distributed Systems | SpringerLink
- 偽陽性があるが、ベクタークロックと比べて空間効率がよい
  - 偽陰性があると致命的だと思うけど、偽陽性なら多くのアプリケーションで許容できるんでは(kekeho)