The Price of being Adaptive
Ohad Ben-Baruch, Danny Hendler · 2015
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. To ensure the correctness of concurrent algorithms in general, and mutual exclusion algorithms in particular, it is often required to prohibit certain re-orderings of memory instructions that may compromise correctness, by inserting memory fence (a.k.a. memory barrier) instructions. Memory fences incur non-negligible overhead and may significantly increase time complexity.