Linearizable Register Emulation (ABD Algorithm)

The ABD algorithm, named after Attiya, Bar-Noy, and Dolev, solves the fundamental problem of implementing atomic read/write semantics in a distributed system where processes can crash and messages can be lost or reordered. Unlike consensus algorithms that require multiple rounds of communication, ABD achieves linearizability through a two-phase protocol: reads require one round-trip to a majority quorum to fetch the value with the highest timestamp, while writes require two phases—first broadcasting the new value with an incremented timestamp to a majority, then confirming the write completion.

The algorithm’s correctness relies on timestamp ordering and the intersection property of majority quorums. Each replica maintains a local timestamp-value pair, and operations use globally unique timestamps (often process ID concatenated with local counter). Read operations query a majority quorum for their current values, select the one with the highest timestamp, then write this value back to a majority to ensure subsequent reads see at least this value. Write operations increment the timestamp and write to a majority, followed by a second phase that propagates the write. The key insight is that any two majority quorums must intersect, guaranteeing that reads always observe the most recent completed write.

ABD’s performance characteristics make it suitable for read-heavy workloads where linearizable semantics are required but the overhead of full consensus is prohibitive. The algorithm tolerates up to f failures in a system of 2f+1 replicas, matching optimal resilience bounds. However, it suffers from read amplification—each read requires communication with a majority—and timestamp management complexity in multi-writer scenarios.

Modern implementations often enhance ABD with optimizations like fast reads (single round-trip when replicas are synchronized), batching multiple operations, and hybrid approaches that combine ABD with consensus for metadata management. The algorithm remains foundational to understanding how linearizability can be achieved without the full machinery of state machine replication, influencing designs in distributed databases, configuration stores, and coordination services.