Storage consistency: ordering is not a transaction or a durability promise

Name the guarantee and its scope

The ordering distinctions follow Herlihy and Wing; session guarantees follow Terry and colleagues. Persistence is a separate API obligation, as the etcd documentation also makes explicit. [1] [2] [4]

A read has an interval, not a magic response timestamp

Linearizability places each operation somewhere between its invocation and response. If a write finishes before a read starts, that order matters. Overlapping operations can have either order when their results permit it. The formal definition is about a legal history, not synchronized wall clocks. [1, section 2.2]

Constructed example: x starts at 0. A read begins and obtains 0; a concurrent write sets x to 1 and finishes; the read then returns 0. That can be linearizable: place the read before the overlapping write. Requiring the newest value at response time would incorrectly reject this history.

Two correct requests can make one incorrect increment

Both clients intend to increment x, initially 0. Each computes a replacement from its own read. These tables are constructed single-register examples, computed by the downloadable example module, not observations from a database.

The first history is already sequential at the GET/PUT level. Nevertheless, two intended increments leave x at 1. In the second, comparison and replacement are one operation: without intervening resets, only one CAS expecting 0 succeeds. The loser rereads, recomputes and retries. Continued contention can require further retries; this example is not a progress guarantee.

etcd offers an atomic conditional transaction with comparisons on values or revision metadata. Its scope does not extend to an unrelated object store or external side effect. [3, Transaction]

Matching bytes do not prove an unchanged history

A separate constructed example allows arbitrary assignments: after A reads 0, another client changes x from 0 to 2 and back to 0. A value-based CAS expecting 0 can succeed. This is not a CAS violation; equality is true. It is insufficient when the application needs evidence that no intervening mutation occurred.

Within the same etcd revision history, atomically comparing the saved mod_revision detects intervening changes to that key even when the bytes return to their old value. The key's version is different: deletion resets it. Neither field covers mutations to other keys. [3, Key-Value pair]

Transaction isolation answers a larger question

Serializability concerns transactions, not just individual requests. Strict serializability also preserves real-time precedence between transactions. [1, section 3.3] In PostgreSQL 18, Serializable isolation can reject a transaction to prevent an anomaly. Applications must handle serialization failures by retrying the transaction, including the reads and decisions that led to its writes; replaying just the final statement is not a general repair. [5, section 13.2.3]

Do not infer these semantics from an option name alone. etcd's serializable read mode can return stale state relative to quorum; it is a read consistency choice, not a promise about an arbitrary sequence of separate client requests. [4]

Different rows can still break one invariant

Snapshot isolation rejects overlapping writes to the same data, but does not generally validate every read dependency. [6, section 4.2] Here is an original metadata example: flags A and B start enabled, and a maintenance transaction may disable its own flag only if it reads more than one enabled flag. This is database metadata, not proof that any physical replica is healthy.

Both concurrent transactions establish their snapshots while A and B are enabled. Each therefore reads 2 and writes a different flag. The module computes this schedule and both possible serial transaction orders:

Neither serial order produces the concurrent outcome. Each serial second transaction sees one enabled flag and leaves it alone. This is write skew, not two writers overwriting the same value. Checking only the version of each flag being written would also miss the cross-key dependency.

The comparison is a small counterexample, not a general serializability checker. A real assessment must account for read results and dependencies, not merely compare final values. See the same executable module used by these tables. Serializable execution or a correctly designed locking protocol must cover the whole invariant, not just the row being updated.

Read-only does not automatically mean safe

Ports and Grittner show how a read-only transaction can participate in a serialization anomaly and derive safe snapshots for such readers. Their PostgreSQL 9.1 implementation paper is historical implementation evidence, not a benchmark of PostgreSQL 18. [7, sections 2.1.2 and 4]

PostgreSQL 18 supports SERIALIZABLE READ ONLY DEFERRABLE: it may wait for a safe snapshot, then avoids serialization-failure retries caused by concurrent transactions. This is not a bound on waiting time or protection against every other error. [5] The paper explicitly distinguishes snapshot safety from how soon a suitable snapshot becomes available. [7, section 4.3]

Session guarantees protect different dependencies

Read-your-writes requires later session reads to incorporate its prior successful writes. A subsequent write can supersede their exact values. Monotonic reads instead protects write effects relevant to earlier reads: changing replicas must not erase those observations. Neither alone demands the globally freshest state. Terry and colleagues specify them separately. [2, sections 3.1-3.2]

If no reachable replica can satisfy a session dependency, preserving the guarantee may require waiting or refusing the operation. A client reconnecting without its session context must not assume the guarantee continues automatically. The system's actual session protocol determines that boundary. [2]

Timeout and durability need their own contracts

etcd documents durable completion separately from ordering. It also distinguishes a completed request from a timeout whose result may be unknown. Do not treat a lost response as proof that a write failed or blindly repeat a non-idempotent action. [4, Operation completed]

A hypothetical volatile in-memory register can implement ordered operations during execution without promising recovery after power loss. That illustrates why an ordering label alone is not a persistence contract; it is not a claim that etcd behaves this way. For the storage path, see NFS stable writes, flush and FUA. For uncertain outcomes, see storage timeouts.

Method, limits and definitions

Primary-source review with constructed register and two-flag transaction schedules, calculated by a public module and checked against both serial transaction orders; not a storage benchmark or implementation conformance test. The register examples use one key; the write-skew example uses two Boolean metadata flags. All assume successful replies and no failures unless stated. They do not certify a deployed database, real replica availability, recovery procedure or disaster-survival guarantee. The tests check these small examples, not arbitrary concurrent histories. No fault injection, throughput measurement or system certification was performed.

Corpus: linearizability, serializability, read-your-writes, monotonic reads, compare-and-swap, snapshot isolation, and write skew.

Primary sources

1. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM TOPLAS 12(3), 1990, sections 2.2 and 3.3.
2. Douglas B. Terry et al. Session Guarantees for Weakly Consistent Replicated Data. PDIS 1994, sections 3.1 and 3.2.
3. etcd v3.6 documentation: Key-Value pair metadata and Transaction.
4. etcd v3.6 API guarantees: durability, strict serializability and operation completion.
5. PostgreSQL 18 documentation, section 13.2: Transaction Isolation.
6. Hal Berenson et al. A Critique of ANSI SQL Isolation Levels. ACM SIGMOD 1995; MSR-TR-95-51, section 4.2.
7. Dan R. K. Ports and Kevin Grittner. Serializable Snapshot Isolation in PostgreSQL. PVLDB 5(12), 1850-1861, 2012, sections 2 and 4. arXiv:1208.4179v1.

Reviewed 12 October 2026. Examples are original illustrations; no source figures reproduced.