Search papers, labs, and topics across Lattice.
This paper presents contention-resolution algorithms for fundamental concurrent primitives like read/write and CAS registers, achieving $O(\log P)$ latency with high probability under a relaxed stochastic scheduler. The algorithms transform hardware primitives susceptible to write contention into those that handle it gracefully, using only $O(1)$ hardware registers. A lower bound trade-off between space, latency, and number of processes is also proven, demonstrating a fundamental limit even under ideal conditions.
Even with adaptive adversaries and write contention, practical concurrent primitives can achieve logarithmic latency using only constant hardware resources.
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 $\Omega(\log_{ML} P)$.
