一貫性

Linearizability

定義. 並列操作の実行履歴が以下を満たす逐次実行と等価である:

1. 全順序 (total order): すべての操作に全順序が存在する
2. リアルタイム性約: 操作 \(A\) が操作 \(B\) より前に完了した場合 (\(A.end\lt B.end\))、全順序でも \(A\lt B\)
3. 仕様適合: 各読み取りは、順序で直前の書き込みの値を返す

Causal Consistency

定義. 因果関係にあるすべてのイベントが、すべてのプロセスで同じ順序で観測される (半順序; partial order)。つまり \(a \to b\) ならば、すべてのプロセスで \(a\) が \(b\) より前に観測される。因果関係にないイベントは異なるプロセスで異なる順序で観測される可能性がある。