A tight RMR lower bound for randomized mutual exclusionReport as inadecuate

A tight RMR lower bound for randomized mutual exclusion - Download this document for free, or read online. Document in PDF available to download.

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE 2 CPSC - Department of Computer Science Calgary

Abstract : The Cache Coherent CC and the Distributed Shared Memory DSM models are standard shared memory models, and the Remote Memory Reference RMR complexity is considered to accurately predict the actual performance of mutual exclusion algorithms in shared memory systems. In this paper we prove a tight lower bound for the RMR complexity of deadlock-free randomized mutual exclusion algorithms in both the CC and the DSM model with atomic registers and compare\&swap objects and an adaptive adversary. Our lower bound establishes that an adaptive adversary can schedule $n$ processes in such a way that each enters the critical section once, and the total number of RMRs is $\Omegan \log n-\log\log n$ in expectation. This matches an upper bound of Hendler and Woelfel 2011.

Author: George Giakkoupis - Philipp Woelfel -

Source: https://hal.archives-ouvertes.fr/


Related documents