An Almost Tight RMR Lower Bound for Abortable Test-And-Set

Aryaz Eghbali, Philipp Woelfel

We prove a lower bound of Omega(log n/loglog n) for the remote memory reference (RMR) complexity of abortable test-and-set (leader election) in the cache-coherent (CC) and the dist…