Consider a deceptively simple operation: increment a counter. In a single-threaded program, this is three machine instructions executed atomically by virtue of sequential execution. Distribute that counter across multiple processes, replicas, or geographic regions, and the same operation becomes one of the most analyzed problems in concurrent computing.

The read-modify-write (RMW) pattern—load a value, compute a new value as a function of it, and store the result—is fundamental to nearly every stateful system. Bank balances, inventory counts, sequence numbers, version vectors, and quota enforcement all depend on RMW semantics. When concurrent actors execute overlapping RMW sequences without coordination, the system loses linearizability, and with it, any meaningful guarantee about correctness.

This article examines the RMW problem through three lenses: the formal characterization of the lost update anomaly, optimistic approaches using compare-and-swap (CAS) primitives, and pessimistic approaches employing distributed locks. Each represents a distinct point in the trade-off space between throughput, contention behavior, fault tolerance, and operational complexity. Understanding the theoretical limits of each approach—and the failure modes they expose—is essential for architects designing systems where correctness under concurrency is non-negotiable.

Let x denote a shared register and let two processes P₁ and P₂ each execute the RMW sequence: read x, compute f(x), write the result. Without synchronization, the histories may interleave such that both processes read the same initial value v₀, both compute f(v₀), and both write f(v₀). The second write overwrites the first, producing a final state of f(v₀) rather than the expected f(f(v₀)). One update is lost.

Formally, this violates linearizability: there exists no sequential ordering of the operations consistent with their real-time precedence that produces the observed outcome. The schedule is serializable only if f is idempotent and commutative, which is rarely the case for operations like increment, append, or balance debit.

The probability of conflict scales with the duration of the critical section and the contention rate. If reads and writes are separated by latency Δt and the arrival rate of conflicting RMW operations is λ, the expected number of conflicts per operation approximates λΔt—a quantity that grows linearly with both contention and the size of the modify window.

In distributed settings, the problem compounds. Network partitions, replica lag, and clock skew expand the effective Δt. Two clients writing to different replicas of an eventually consistent store may both succeed locally and only discover the conflict during reconciliation—often too late to recover the lost update without application-level logic.

The anomaly is not merely a performance issue; it is a correctness violation. Any system claiming serializable or linearizable semantics must, by definition, prevent it. The mechanisms differ; the requirement does not.

Takeaway

Lost updates are not edge cases—they are the default behavior of uncoordinated concurrent state mutation. Every correctness guarantee in a stateful distributed system is, ultimately, a story about how RMW interleavings are prevented or detected.

Optimistic concurrency control assumes conflicts are rare and validates this assumption at commit time. The canonical primitive is compare-and-swap: CAS(addr, expected, new) atomically writes new to addr only if its current value equals expected. Distributed equivalents include conditional writes keyed on version numbers, ETags, or vector clocks—DynamoDB's conditional updates and etcd's revision-based transactions are practical instantiations.

The RMW loop becomes: read v, compute f(v), attempt to write conditional on the value still being v. On failure, retry. This eliminates lost updates because the write only succeeds if no intervening modification occurred. The cost is shifted from the common path to the contended path—uncontended operations require no locking, while contended operations may retry repeatedly.

Under high contention, retry behavior degrades sharply. If n processes contend on the same register, the expected number of retries per process is O(n), and the system throughput per process drops as 1/n. Worse, in the absence of fairness guarantees, individual processes may experience starvation: faster processes may consistently win the CAS race, leaving slower ones in an unbounded retry loop. This is livelock—the system makes progress, but specific participants do not.

Mitigations include exponential backoff, randomized jitter, and combining trees, all of which reduce contention at the cost of latency. More structurally, one can shard the contended state—replacing a single counter with k counters summed on read—trading write contention for read complexity. This works only when the operation permits decomposition; serial dependencies cannot be sharded away.

Optimistic concurrency excels when conflicts are rare and operations are short. It degrades when either assumption fails, and the failure mode is throughput collapse rather than correctness violation—a desirable property, but one that demands careful workload analysis before deployment.

Takeaway

Optimistic concurrency converts correctness problems into performance problems. Whether that trade is favorable depends entirely on your contention distribution, which is often less benign than designers assume.

When contention is high or operations are long, pessimistic locking becomes preferable: acquire exclusive access to a resource, perform the RMW, release. The challenge in distributed systems is that locks must themselves be highly available, fault-tolerant, and resistant to client failures—a process holding a lock might crash, partition, or simply pause for a long garbage collection cycle.

Production systems address this through lease-based locks: a lock is held for a bounded duration, after which it expires automatically. ZooKeeper, etcd, and Chubby implement this via consensus protocols (Zab, Raft, Paxos respectively), providing linearizable lock acquisition with strong safety guarantees. The lock manager itself is a replicated state machine, and lock state is committed through the consensus log.

Antirez's Redlock algorithm proposed using Redis—a non-consensus system—as a distributed lock by requiring acquisition on a majority of independent Redis instances. Martin Kleppmann's critique argued that Redlock is unsafe under realistic timing assumptions: a process can be paused after acquiring the lock and resume after the lease has expired and been reissued, causing two clients to believe they hold the lock simultaneously. Antirez countered that fencing tokens—monotonically increasing identifiers checked at the resource—provide the necessary safety net, and that consensus-based locks face the same fundamental issue.

The deeper insight from this exchange is that no lease-based distributed lock can provide mutual exclusion in the face of unbounded process pauses without cooperation from the protected resource. Safety requires either (a) the resource itself enforces token-based admission, rejecting writes from holders of stale leases, or (b) the system abandons asynchrony assumptions—an option unavailable to most practical deployments.

Distributed locks are thus not a complete solution but a coordination primitive. Their correctness depends on fencing at the storage layer, bounded clock drift, and a clear-eyed understanding that the lock manager's liveness and the protected operation's safety are separable concerns.

Takeaway

A distributed lock alone does not provide mutual exclusion—it provides a likely hint of mutual exclusion. True safety requires the protected resource to participate via fencing tokens or equivalent mechanisms.

The read-modify-write problem is a microcosm of distributed systems design: a simple operation rendered profound by concurrency, failure, and asynchrony. The lost update anomaly defines what we must prevent; CAS and distributed locks represent two philosophies for preventing it; and neither is universally superior.

Optimistic methods win on uncontended throughput and degrade gracefully into retry storms under load. Pessimistic methods provide predictable behavior under contention but introduce coordination overhead, single points of contention, and subtle safety dependencies on fencing and clock assumptions. The competent architect chooses based on measured contention, operation duration, and tolerance for tail latency.

The enduring principle is that correctness under concurrency is never accidental. It is constructed deliberately, from primitives whose semantics are understood precisely, deployed in contexts whose assumptions are validated continuously. Everything else is a lost update waiting to happen.