2026-07-26T16:44:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9810 2024-03-06T10:44:59Z ddc:004 open_access

An Almost Tight RMR Lower Bound for Abortable Test-And-Set Eghbali, Aryaz Woelfel, Philipp Abortability Test-And-Set Leader Election Compare-and-Swap RMR Complexity Lower Bound We prove a lower bound of Omega(log n/log log n) for the remote memory reference (RMR) complexity of abortable test-and-set (leader election) in the cache-coherent (CC) and the distributed shared memory (DSM) model. This separates the complexities of abortable and non-abortable test-and-set, as the latter has constant RMR complexity [Wojciech Golab et al., 2010]. Golab, Hendler, Hadzilacos and Woelfel [Wojciech M. Golab et al., 2012] showed that compare-and-swap can be implemented from registers and test-and-set objects with constant RMR complexity. We observe that a small modification to that implementation is abortable, provided that the used test-and-set objects are atomic (or abortable). As a consequence, using existing efficient randomized wait-free implementations of test-and-set [George Giakkoupis and Philipp Woelfel, 2012], we obtain randomized abortable compare-and-swap objects with almost constant (O(log^* n)) RMR complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aryaz Eghbali and Philipp Woelfel 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.21 urn:nbn:de:0030-drops-98103 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.21 eng https://creativecommons.org/licenses/by/3.0/legalcode