caa a22 4500 445355018 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00446-011-0128-6 doi (NATIONALLICENCE)springer-10.1007/s00446-011-0128-6 Randomized mutual exclusion with sub-logarithmic RMR-complexity [Elektronische Daten] [Danny Hendler, Philipp Woelfel] Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. Attiya, Hendler, and Woelfel (40th STOC, 2008) established an Ω(log N) lower bound on the number of RMRs incurred by processes as they enter and exit the critical section, where N is the number of processes in the system. This matches the upper bound of Yang and Anderson (Distrib. Comput. 9(1):51-60, 1995). The upper and lower bounds apply for algorithms that only use read and write operations. The lower bound of Attiya etal., however, only holds for deterministic algorithms. The question of whether randomized mutual exclusion algorithms, using reads and writes only, can achieve sub-logarithmic expected RMR complexity remained open. We answer this question in the affirmative by presenting starvation-free randomized mutual exclusion algorithms for the cache coherent (CC) and the distributed shared memory (DSM) model that have sub-logarithmic expected RMR complexity against the strong adversary. More specifically, each process incurs an expected number of O(log N / log log N) RMRs per passage through the entry and exit sections, while in the worst case the number of RMRs is O(log N). Springer-Verlag, 2011 Mutual exclusion nationallicence Remote memory references nationallicence RMRs nationallicence Strong adversary nationallicence Randomization nationallicence Hendler Danny Ben-Gurion University, Beersheba, Israel aut Woelfel Philipp University of Calgary, Calgary, AB, Canada aut Distributed Computing Springer-Verlag 24/1(2011-09-01), 3-19 0178-2770 24:1<3 2011 24 446 https://doi.org/10.1007/s00446-011-0128-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0128-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hendler Danny Ben-Gurion University, Beersheba, Israel aut NATIONALLICENCE 700 1- Woelfel Philipp University of Calgary, Calgary, AB, Canada aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/1(2011-09-01), 3-19 0178-2770 24:1<3 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer