hesela.devSequential consistency
Sequential consistency requires one legal sequential order of an execution's operations that preserves each process's program order.
The order must work for the entire claimed scope, not separately for each observer. The client or process boundary must be specified. [1]
Unlike linearizability, the common order can reverse real-time precedence between different clients. In a constructed example, x starts at 0; A finishes writing 1 before B starts a read that returns 0. Ordering B's read before A's write explains the result sequentially, but violates real-time precedence. There are no other operations or synchronization in this example. [2]
Sequential consistency is not local: separate objects can each admit an order while their combination admits none. Cross-object reasoning requires a compatible common order. [2]
Ordering alone does not specify crash durability or turn several requests into one transaction. Persistence and transaction boundaries require additional contracts. [3]
Relations
Citations
- Leslie Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE TC 28(9), 1979, pp. 690-691.
- Herlihy and Wing. Linearizability. ACM TOPLAS 12(3), 1990, sections 2.1-2.2 and 3.3.
- etcd v3.6 API guarantees: durability, atomicity and strict serializability.
Further reading
Sources & caveats
- Definition and scope checked against Lamport 1979 and Herlihy/Wing 1990. Separate durability contract illustrated by etcd documentation.
- Worked histories are constructed examples, not observations of a database, processor or storage device.