Fast Concurrent Primitives Despite Contention
This work provides a theoretical foundation for building efficient concurrent data structures that gracefully handle write contention, with implications for shared-memory parallel systems.
The authors present contention-resolution algorithms for concurrent primitives (read/write and CAS registers) that achieve O(log P) latency with high probability under a relaxed stochastic scheduler, using O(1) hardware registers. They also prove a lower bound showing that any such algorithm must have expected latency Ω(log_{ML} P).
We study the problem of constructing concurrent objects in a setting where $P$ processes run in parallel and interact through a shared memory that is subject to write contention. Our goal is to transform hardware primitives that are subject to write contention into ones that handle contention gracefully. We give contention-resolution algorithms for several basic primitives, and analyze them under a relaxed, roughly-synchronous stochastic scheduler, where processes run at roughly the same rate up to a constant factor with high probability. Specifically, we construct read/write registers and CAS registers that have latency $O(\log P)$ w.h.p. under our scheduler model, using $O(1)$ hardware read/write registers and, in the case of our CAS construction, one hardware CAS register. Our algorithms guarantee performance even when their operations are invoked by an adaptive adversary that is able to see the entire history of operations so far, including their timing and return values. This allows them to be used as building blocks inside larger programs; using this compositionality property, we obtain several other constructions (LL/SC, fetch-and-increment, bounded max registers, and counters). To complement our constructions, we give a trade-off showing that even under a perfectly synchronous schedule and even if each process only executes one operation, any algorithm that implements any of the primitives that we consider, uses space $M$, and has latency at most $L$ with high probability must have expected latency at least $Ω(\log_{ML} P)$.