Nonatomic mutual exclusion with local spinning

ABSTRACT

We present an N-process local-spin mutual exclusion algorithm, based on nonatomic reads and writes, in which each process performs Θ(log N) remote memory references to enter and exit its critical section. No atomic read/write algorithm with better asymptotic worst-case time complexity is currently known. This suggests that atomic memory is not fundamentally required if one is interested in worst-case time complexity. The same cannot be said if one is interested in fast-path or adaptive algorithms. We show that such algorithms fundamentally require memory accesses to be atomic. In particular, we show that for any N-process nonatomic algorithm, there exists a single-process execution in which the lone competing process executes Ω(log N/log log N) remote operations to enter its critical section. Moreover, these operations must access Ω(√log N/log log N) distinct variables.

REFERENCES

• 1: Yehuda Afek , Hagit Attiya , Arie Fouren , Gideon Stupp , Dan Touitou, Long-lived renaming made adaptive, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.91-103, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301335]
• 2: Yehuda Afek , Pazi Boxer , Dan Touitou, Bounds on the shared memory requirements for long-lived & adaptive objects (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.81-89, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343523]
• 3: Rajeev Alur , Gadi Taubenfeld, Contention-free complexity of shared memory algorithms, Information and Computation, v.126 n.1, p.62-73, April 10, 1996 [doi>10.1006/inco.1996.0034]
• 4: J. Anderson. A fine-grained solution to the mutual exclusion problem. Acta Informatica, 30(3):249-265, May 1993.
• 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, 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]
• 7: James H. Anderson , Yong-Jik Kim, A new fast-path mechanism for mutual exclusion, Distributed Computing, v.14 n.1, p.17-29, January 2001 [doi>10.1007/PL00008923]
• 8: J. Anderson and Y.-J. Kim. Nonatomic mutual exclusion with local spinning (full version of this paper). Available at http://www.cs.unc.edu/~anderson/papers.html
• 9: 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]
• 10: 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]
• 11: Hagit Attiya , Vita Bortnikov, Adaptive and efficient mutual exclusion (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.91-100, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343525]
• 12: J. Burns and N. Lynch. Mutual exclusion using indivisible reads and writes. In Proceedings of the 18th Annual Allerton Conference on Communication, Control, and Computing, pages 833-842, 1980.
• 13: 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]
• 14: Gary Granunke , Shreekant Thakkar, Synchronization Algorithms for Shared-Memory Multiprocessors, Computer, v.23 n.6, p.60-69, June 1990 [doi>10.1109/2.55501]
• 15: Sibsankar Haldar , P. S. Subramanian, Space-optimum Conflict-free Construction of 1-Writer 1-Reader Multivalued Atomic Variable, Proceedings of the 8th International Workshop on Distributed Algorithms, p.116-129, September 29-October 01, 1994
• 16: S. Haldar , K. Vidyasankar, Constructing 1-writer multireader multivalued atomic variables from regular variables, Journal of the ACM (JACM), v.42 n.1, p.186-203, Jan. 1995 [doi>10.1145/200836.200871]
• 17: J. Kessels. Arbitration without common modifiable variables. Acta Informatica, 17:135-141, 1982.
• 18: 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
• 19: Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
• 20: Leslie Lamport, The mutual exclusion problem: partII—statement and solutions, Journal of the ACM (JACM), v.33 n.2, p.327-348, April 1986 [doi>10.1145/5383.5385]
• 21: L. Lamport. On interprocess communication: Part II - Algorithms. Distributed Computing, 1:86-101, 1986.
• 22: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 23: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 24: G. Peterson and J. Burns. Concurrent reading while writing II: The multi-writer case. In Proceedings of the 28th Annual ACM Symposium on Foundation of Computer Science. ACM, 1987.
• 25: R. Schaffer. On the correctness of atomic multi-writer registers. Technical Report MIT/LCS/TM-364, Laboratory for Computer Science, MIT, Cambridge, 1988.
• 26: Ambuj K. Singh , James H. Anderson , Mohamed G. Gouda, The elusive atomic register, Journal of the ACM (JACM), v.41 n.2, p.311-339, March 1994 [doi>10.1145/174652.174657]
• 27: Eugene Styer, Improving fast mutual exclusion, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.159-168, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135453]
• 28: E. Styer , G. L. Peterson, Tight bounds for shared memory symmetric mutual exclusion problems, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.177-191, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72993]
• 29: P. Turán. On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok, 48:436-452, 1941.
• 30: J.-H. Yang and J. Anderson. A fast, scalable mutual exclusion algorithm. Distributed Computing, 9(1):51-60, August 1995.