Skip to content

Sequential-Consistency Trace Protocol

Verification protocol — instantiates Shared-State Consistency Contract Design

Records the interleaved history of operations and checks it against a single program-order-respecting total order, flagging any execution no such order can explain.

Sequential-Consistency Trace Protocol pins the contract to a precise legal-history rule and then checks executions against it. Sequential consistency requires that there exist one total order over all operations that (a) is consistent with each individual process's program order and (b) makes every read return the value of the most recent write in that order — but, unlike linearizability, it need not respect real time. This mechanism captures per-process operation traces with their returned values, searches for a total order that explains them, and if none exists, reports a violation with the offending cycle. Its distinguishing role is to define and enforce which interleavings are legal under this specific model and to supply the oracle that catches illegal ones — as opposed to merely measuring staleness or asserting real-time recency.

Example

A cluster exposes a shared "config generation number" that nodes increment and read to coordinate rollouts. The team wants to verify the store is at least sequentially consistent. Each client is instrumented to emit an ordered trace of its own operations and the values it saw. The protocol collects these into one global history and searches for a total order in which each client's operations keep their program order and every read returns the latest preceding write. It finds an execution where one client read generation 5, then on its next read saw generation 4 — its own reads went backward. No single total order consistent with that client's program order can produce that, so the protocol flags a violation: the store is not even sequentially consistent, an anomaly a freshness dashboard would never have surfaced because both values were "recent."

How it works

The distinguishing mechanics are trace-and-search against a model, not against a bound. Clients emit ordered per-process histories; these are merged into a global history; a solver looks for a legal total order (program order per process, plus read-sees-last-write), which is a constraint-satisfaction search that reduces to something combinatorial. When it fails, it returns the minimal violating cycle so the bug is localizable. Because the search is expensive, it runs over sampled windows rather than continuously, and it can operate online (streaming) or offline (post-hoc on captured logs).

Tuning parameters

  • Trace window length — longer windows catch more but cost far more to check (the search is combinatorially hard); bound the window.
  • Recorded fields — values and program order only, or also timestamps: more power to localize versus more overhead.
  • Model strictness — pure sequential consistency, or sequential plus monotonic-reads: which anomalies count as violations.
  • Online vs. offline — stream-check for fast feedback, or batch-check logs for completeness.
  • Client sampling rate — how many clients are instrumented, trading coverage against instrumentation cost.

When it helps, and when it misleads

Its strength is catching reordering anomalies that symptom metrics cannot see, and doing so model-precisely — it tells you exactly which guarantee broke. It is especially valuable in CI and alongside fault injection.

It misleads if a pass is read as a proof. Sequential consistency is not compositional — verifying components does not verify the whole — and it is strictly weaker than linearizability, so passing this check does not mean the store is linearizable; a sequentially-consistent read may legally be stale.[1] Because checking cost forces sampling, "no violation found" means only that — not correctness. The backwards move is relaxing the model until the trace passes. The discipline is to choose the model from the invariant first, and treat a clean run as "no violation found in this window," never as a guarantee.

How it implements the components

  • legal_history_contract — encodes exactly which interleavings are legal under sequential consistency (a program-order-respecting total order in which reads see the last write).
  • consistency_violation_oracle — the checker that searches captured histories for a legal order and reports the violating cycle when none exists.

It does not assert real-time recency (consistency_guarantee_profile, operation_semantics_contract) — that is Linearizable Read/Write Protocol — supply the version tokens the trace relies on (version_token, Version Vector), or inject the faults it checks under (Partition and Clock Fault Injection); a model-agnostic checker is Consistency History Checker.

References

[1] Sequential consistency (Lamport, 1979) — there exists a total order over all operations consistent with each process's program order. Unlike linearizability it ignores real time (so a read may return a stale-but-ordered value) and, also unlike linearizability, it does not compose — two sequentially-consistent objects together need not be sequentially consistent. ↩