Skip to content

Compare-and-Swap Version Token

Optimistic-concurrency method — instantiates Use-Time Precondition Binding

Reads a value together with a version marker and writes back only if the version is still unchanged — so a write computed from stale state is refused instead of silently overwriting a newer one.

Compare-and-Swap Version Token binds the check to the use by fusing them into a single atomic conditional write. You read a value together with a version marker — a counter, an ETag, a content hash — and carry that marker with you. When you write, the write is not "set X to 42" but "set X to 42 only if the version is still the one I read." If anyone changed the value in between, the marker no longer matches and the write is refused. Its defining move is that no lock is held and no resource is reserved: everyone proceeds optimistically, and the version comparison is what catches the loser of a race and rejects the stale overwrite. The gap between check and use is collapsed to the width of one indivisible instruction.

Example

Two editors open the same wiki page. Each GET returns the page body and an ETag: "v7" — a real HTTP mechanism for exactly this. Editor A finishes first and saves with If-Match: "v7"; the server sees the current version is still v7, accepts the write, and advances the page to v8. Editor B, who also loaded v7, now saves — also with If-Match: "v7". The server sees the page is now v8, not v7, and returns 412 Precondition Failed: B's write was computed against a version that no longer exists, so it is refused rather than allowed to clobber A's changes. B must re-fetch v8, reapply the edit on top of A's, and try again.

The version token is what makes B's stale write visible as stale. Without it, B's save would silently overwrite A's — the classic lost-update bug — because both writes look individually valid; only the version reveals that B was acting on a superseded picture of the page.

How it works

  • The marker travels with the read. Whatever is read out carries a version — monotonic counter, ETag, or hash — that identifies exactly which state it reflects.
  • The write is conditional and atomic. Compare-then-swap is one indivisible operation (a CPU instruction, a database WHERE version = ?, an If-Match header): there is no window between confirming the version and applying the change.
  • A mismatch refuses, it doesn't block. Because nothing is locked, a conflicting write simply fails and returns the current version; nobody waits, so there is no deadlock — the cost of contention is redone work, not blocked time.

Tuning parameters

  • Version representation — a monotonic counter, a content hash/ETag, or a timestamp. Counters are safest; hashes can alias; timestamps break under clock skew.
  • Version granularity — one marker per field, per row, or per whole document. Fine-grained yields fewer false conflicts but more bookkeeping; coarse is simpler but rejects writes that never truly collided.
  • Compare breadth — swap on a single value, or require several values to all match (multi-word compare-and-swap) for a consistent multi-field update.
  • Failure return — report bare failure, or return the current value and version so the caller can auto-rebase without a second read.

When it helps, and when it misleads

Its strength is lock-free safety: it turns "check then write" into one operation, cannot deadlock, and scales beautifully when contention is low and conflicts are the exception. It is the safe core that most optimistic-concurrency systems are built on.

It misleads in three ways. Under high contention it degrades — writers spend all their effort failing and re-reading, and a lock would have been cheaper than the churn. It is vulnerable to the ABA problem: if a value goes A → B → back to A, a plain marker looks unchanged and the swap wrongly succeeds even though the world moved and returned[1]. And a timestamp or reused version invites the subtler failure where a stale write sneaks through because two distinct states shared a marker. The classic misuse is treating a successful swap as proof of correctness while ignoring ABA. The discipline is to use monotonic, never-reused version counters (or tagged/hazard pointers) so that "same version" reliably means "same state."

How it implements the components

Compare-and-Swap realizes the detect-and-refuse side of the archetype — proving at the write that the read is still current, without holding anything:

  • state_version_or_freshness_token — the version marker it reads out and carries: the token that ties a write to the exact state it was computed from.
  • atomic_or_exclusive_use_boundary — the compare-and-swap itself, an indivisible operation that leaves no window between confirming the version and applying the write.
  • invalidation_and_revocation_signal — a version mismatch is the built-in signal that the caller's read is now stale (the data-invalidation kind; authority/permission revocation is Revocation Status Check at Use's job).

It refuses a stale write but does not decide what to do next — the conflict_abort_and_retry_policy belongs to Abort-and-Retry After State Mismatch — and it holds nothing, so the reservation_or_hold_record and validity_window_or_lease are Reservation-Commit Protocol's and Lease-Bound Capability Token's.

  • Instantiates: Use-Time Precondition Binding — Compare-and-Swap binds the precondition by making the write itself conditional on the checked state still holding.
  • Sibling mechanisms: Abort-and-Retry After State Mismatch · Two-Phase Commit with Freshness Check · Snapshot-Pinned Decision · Reservation-Commit Protocol · Lock or Hold Until Use · Final Revalidation Before Commit · Lease-Bound Capability Token · Stale Data Revalidation Gate · Revocation Status Check at Use · Confirmation Dialog with State Refresh · Timestamp and Freshness Badge

Notes

Compare-and-Swap only reports the conflict — it is deliberately incomplete on its own. In practice it is the sensor paired with Abort-and-Retry After State Mismatch as the actuator: CAS detects the mismatch atomically, and the retry policy decides whether to rebase, escalate, or give up. Keeping detection and reaction separate is what lets the same version-token core drive very different responses in different systems.

References

[1] The ABA problem: a location read as value A is later found to be A again at the swap, so a naïve version check passes — yet in between it was changed to B and back, and the intervening state was missed. It is defeated by making the version strictly monotonic (or tagging the pointer) so that a round trip still shows a different marker. ↩