Constant-RMR implementations of CAS and other synchronization primitives using read and write operations

ABSTRACT

We consider asynchronous multiprocessors where processes communicate only by reading or writing shared memory. We show how to implement consensus, all comparison primitives (such as CAS and TAS), and load-linked/store-conditional using only a constant number of remote memory references (RMRs), in both the cache-coherent and the distributed-shared-memory models of such multiprocessors. Our implementations are blocking, rather than wait-free: they ensure progress provided all processes that invoke the implemented primitive are live.

Our results imply that any algorithm using read and write operations, comparison primitives, and load-linked/store-conditional, can be simulated by an algorithm that uses read and write operations only, with at most a constant blowup in RMR complexity.

REFERENCES

• 1: 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]
• 2: James H. Anderson , Yong-Jik Kim, Local-spin Mutual Exclusion Using Fetch-and-\phi Primitives, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.538, May 19-22, 2003
• 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: T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
• 5: T. Craig. Queuing spin lock algorithms to support timing predictability. In Proc. of 14th RTSS, pages 148--156, 1993.
• 6: Robert Cypher, The communication requirements of mutual exclusion, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.147-156, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215434]
• 7: 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]
• 8: Wojciech Golab , Danny Hendler , Philipp Woelfel, An O(1) RMRs leader election algorithm, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146417]
• 9: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 10: 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
• 11: Mark Moir, Practical implementations of non-blocking synchronization primitives, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.219-228, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259442]
• 12: David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 13: 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: Distributed programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Performance, Theory

Keywords:
comparison primitives, consensus, mutual exclusion, remote memory references, shared memory