March 6, Tuesday
12:00 – 14:00
While there is a lower bound of $\Omega(\log n / \log \log n)$ RMRs on the worst-case complexity of mutual exclusion algorithms that use only read/write operations, it was unknown whether such a lower bound applied also for the leader election problem, which may be regarded as `one-shot' mutual exclusion.
We provide a negative answer to this question by presenting an $O(1)$ RMRs leader election algorithm, using reads/writes only, improving on $\Theta(\log n)$ best prior-art algorithms. We show that our technique can be extended for deriving constant RMRs implementations of synchronization primitives that are considered stronger, such as consensus and comparison primitives (e.g., the widely used compare-and-swap).
Herlihy has shown that synchronization primitives vary widely in their power to support wait-free implementations and classified them in the wait-free hierarchy based on this computability power . For blocking implementations, this hierarchy is flat, since all primitives can be implemented in a blocking manner from reads and writes. Instead of comparing the computability power of a pair of primitives, it is therefore natural to ask whether we can base such a comparison on the RMR complexities of implementing these primitives from reads and writes. Our results establish that looking at the relative power of primitives through this lens reveals a landscape sharply different from that of Herlihy's wait-free hierarchy.
This talk is for a general audience and, to the extent possible, will be self-contained.
Joint work with Wojciech Golab, Vassos Hadzilacos, and Philipp Woelfel.