A Tight RMR Lower Bound for Randomized Mutual Exclusion

被引:0
作者
Giakkoupis, George [1 ]
Woelfel, Philipp [2 ]
机构
[1] INRIA Rennes Bretagne Atlantique, Rennes, France
[2] Univ Calgary, Calgary, AB, Canada
来源
STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2012年
基金
加拿大自然科学与工程研究理事会;
关键词
Mutual exclusion; Lower bound; Remote memory references; RMRs; Strong adversary; Randomization; IMPLEMENTATIONS;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 Omega(n log n/log log n) in expectation. This matches an upper bound of Hendler and Woelfel [16].
引用
收藏
页码:983 / 1001
页数:19
相关论文
共 24 条
  • [1] An improved lower bound for the time complexity of mutual exclusion
    Anderson, JH
    Kim, YJ
    [J]. DISTRIBUTED COMPUTING, 2002, 15 (04) : 221 - 253
  • [2] Anderson JH, 2000, LECT NOTES COMPUT SC, V1914, P29
  • [3] Anderson JH, 1999, LECT NOTES COMPUT SC, V1693, P180
  • [4] Anderson T. E., 1990, IEEE Transactions on Parallel and Distributed Systems, V1, P6, DOI 10.1109/71.80120
  • [5] [Anonymous], 2008, ART MULTIPROCESSOR P
  • [6] Randomized protocols for asynchronous consensus
    Aspnes, J
    [J]. DISTRIBUTED COMPUTING, 2003, 16 (2-3) : 165 - 175
  • [7] Attiya H, 2008, ACM S THEORY COMPUT, P217
  • [8] Mutual Exclusion with O(log2 log n) Amortized Work
    Bender, Michael A.
    Gilbert, Seth
    [J]. 2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, : 728 - 737
  • [9] Chi-Chih Yao A., 1977, 18th Annual Symposium on Foundations of Computer Science, P222
  • [10] Cypher R., 1995, SPAA '95. 7th Annual ACM Symposium on Parallel Algorithms and Architectures, P147, DOI 10.1145/215399.215434