An O(1) RMRs leader election algorithm

ABSTRACT

The leader election problem is a fundamental distributed coordination problem. We present leader election algorithms for the cache-coherent (CC) and distributed shared memory (DSM) models using reads and writes only, for which the number of remote memory references (RMRs) is constant in the worst case.The algorithms use splitter-like objects [6, 8] in a novel way for the efficient partitioning of processes into disjoint sets that share work. As there is an Ω(log n/log log n) lower bound on the RMR complexity of mutual exclusion for n processes using reads and writes only [4], our result separates the mutual exclusion and leader election problems in terms of RMR complexity in both the CC and DSM models.Our result also implies that any algorithm using reads, writes and one-time test-and-set objects can be simulated by an algorithm using reads and writes with only a constant blowup of the RMR complexity. Anderson, Herman and Kim raise the question of whether conditional primitives such as test-and-set and compare-and-swap are stronger than read and write for the implementation of local-spin mutual exclusion [3]. We provide a negative answer to this question, at least for one-time test-and-set.

REFERENCES

• 1: R. Alur and G. Taubenfeld. Results about fast mutual exclusion. In Proc. RTSS 1992, pp. 154--162, 1992.
• 2: J. Anderson. A fine-grained solution to the mutual exclusion problem. Acta Inf., 30(3):249--265, 1993.
• 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, An improved lower bound for the time complexity of mutual exclusion, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.90-99, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383996]
• 5: 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]
• 6: Mark Moir , James H. Anderson, Wait-free algorithms for fast, long-lived renaming, Science of Computer Programming, v.25 n.1, p.1-39, Oct. 1995 [doi>10.1016/0167-6423(95)00009-H ]
• 7: James H. Anderson , Jae-Heon Yang, Time/contention trade-offs for multiprocessor synchronization, Information and Computation, v.124 n.1, p.68-84, Jan. 10, 1996 [doi>10.1006/inco.1996.0006 ]
• 8: Hagit Attiya , Arie Fouren, Adaptive and Efficient Algorithms for Lattice Agreement and Renaming, SIAM Journal on Computing, v.31 n.2, p.642-664, 2001 [doi>10.1137/S0097539700366000]
• 9: Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Distributed Computing, v.8 n.1, p.1-17, August 1994 [doi>10.1007/BF02283567]
• 10: 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]
• 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: Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Journal of the ACM (JACM), v.44 n.6, p.779-805, Nov. 1997 [doi>10.1145/268999.269000]
• 13: 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]
• 14: 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]
• 15: 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
• 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: Hyonho Lee, Transformations of Mutual Exclusion Algorithms from the Cache-Coherent Model to the Distributed Shared Memory Model, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.261-270, June 06-10, 2005 [doi>10.1109/ICDCS.2005.83]

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:
leader election, mutual exclusion, remote memory references, shared memory, test-and-set