Randomized mutual exclusion in O(log N / log log N) RMRs

ABSTRACT

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. A recent proof [9] established an Ω(log N) lower bound on the number of RMRs incurred by processes as they enter and exit the critical section, matching an upper bound by Yang and Anderson [18]. Both these bounds apply for algorithms that only use read and write operations. The lower bound of [9] only holds for deterministic algorithms, however; the question of whether randomized mutual exclusion algorithms, using reads and writes only, can achieve sub-logarithmic expected RMR complexity remained open. This paper answers this question in the affirmative.

We present two strong-adversary [8] randomized local-spin mutual exclusion algorithms. In both algorithms, processes incur O(log N / log log N) expected RMRs per passage in every execution. Our first algorithm has sub-optimal worst-case RMR complexity of O(log N / log log N)²). Our second algorithm is a variant of the first that can be combined with a deterministic algorithm, such as [18], to obtain O(log N) worst-case RMR complexity. The combined algorithm thus achieves sub-logarithmic expected RMR complexity while maintaining optimal worst-case RMR complexity. Our upper bounds apply for both the cache coherent (CC) and the distributed shared memory (DSM) models.

REFERENCES

• 1: R. Alur and G. Taubenfeld. Results about fast mutual exclusion. In Proc. of the 13th IEEE Real-Time Systems Symposium, pages 12--21, December 1992.
• 2: James H. Anderson , Yong-Jik Kim, An improved lower bound for the time complexity of mutual exclusion, Distributed Computing, v.15 n.4, p.221-253, December 2002 [doi>10.1007/s00446-002-0084-2]
• 3: James H. Anderson , Yong-Jik Kim , Ted Herman, Shared-memory mutual exclusion: major research trends since 1986, Distributed Computing, v.16 n.2-3, p.75-110, September 2003 [doi>10.1007/s00446-003-0088-6]
• 4: James H. Anderson , Yong-Jik Kim, Fast and Scalable Mutual Exclusion, Proceedings of the 13th International Symposium on Distributed Computing, p.180-194, September 27-29, 1999
• 5: James H. Anderson , Yong-Jik Kim, Adaptive Mutual Exclusion with Local Spinning, Proceedings of the 14th International Conference on Distributed Computing, p.29-43, October 04-06, 2000
• 6: James H. Anderson , Yong-Jik Kim, Nonatomic mutual exclusion with local spinning, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571827]
• 7: T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
• 8: James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September 2003 [doi>10.1007/s00446-002-0081-5]
• 9: Hagit Attiya , Danny Hendler , Philipp Woelfel, Tight RMR lower bounds for mutual exclusion and other problems, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374410]
• 10: Robert Danek , Wojciech Golab, Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion, Proceedings of the 22nd international symposium on Distributed Computing, September 22-24, 2008, Arcachon, France [doi>10.1007/978-3-540-87779-0_7]
• 11: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 12: Wojciech Golab , Vassos Hadzilacos , Danny Hendler , Philipp Woelfel, Constant-RMR implementations of CAS and other synchronization primitives using read and write operations, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281105]
• 13: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 14: Prasad Jayanti, Adaptive and efficient abortable mutual exclusion, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.295-304, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872079]
• 15: P. Jayanti, S. Petrovic, and N. Narula. Read/write based fast-path transformation for FCFS mutual exclusion. In SOFSEM, pages 209--218, 2005.
• 16: Yong-Jik Kim , James H. Anderson, A Time Complexity Bound for Adaptive Mutual Exclusion, Proceedings of the 15th International Conference on Distributed Computing, p.1-15, October 03-05, 2001
• 17: Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 2006
• 18: J.-H. Yang and J. Anderson. A fast, scalable mutual exclusion algorithm. Distributed Computing, 9(1):51--60, 1995.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Theory

Keywords:
mutual exclusion, remote memory references (RMRS)