Document Open Access Logo

Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions

Authors Liat Maor, Gadi Taubenfeld

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.30.pdf
  • Filesize: 0.65 MB
  • 16 pages

Document Identifiers

Author Details

Liat Maor
  • The Interdisciplinary Center, Herzliya, Israel
Gadi Taubenfeld
  • The Interdisciplinary Center, Herzliya, Israel

Acknowledgements

We thank the anonymous referees for their constructive suggestions.

Cite AsGet BibTex

Liat Maor and Gadi Taubenfeld. Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.30

Abstract

Group mutual exclusion (GME), introduced by Joung in 1998, is a natural synchronization problem that generalizes the classical mutual exclusion and readers and writers problems. In GME a process requests a session before entering its critical section; processes are allowed to be in their critical sections simultaneously provided they have requested the same session. We present a GME algorithm that (1) is the first to achieve a constant Remote Memory Reference (RMR) complexity for both cache coherent and distributed shared memory machines; and (2) is the first that can be accessed by arbitrarily many dynamically allocated processes and with arbitrarily many session names. Neither of the existing GME algorithms satisfies either of these two important properties. In addition, our algorithm has constant space complexity per process and satisfies the two strong fairness properties, first-come-first-served and first-in-first-enabled. Our algorithm uses an atomic instruction set supported by most modern processor architectures, namely: read, write, fetch-and-store and compare-and-swap.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Distributed computing models
  • Theory of computation → Shared memory algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • Group mutual exclusion
  • RMR complexity
  • unbounded number of processes
  • fetch&store (FAS)
  • compare&swap (CAS)

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. R. Alur and G. Taubenfeld. Results about fast mutual exclusion. In Proceedings of the 13th IEEE Real-Time Systems Symposium, pages 12-21, 1992. Google Scholar
  2. A. Aravind and W.H. Hesselink. Group mutual exclusion by fetch-and-increment. ACM Trans. Parallel Comput., 5(4), 2019. Google Scholar
  3. R. Atreya, N. Mittal, and S. Peri. A quorum-based group mutual exclusion algorithm for a distributed system with dynamic group set. IEEE Transactions on Parallel and Distributed Systems, 18(10), 2007. Google Scholar
  4. J. Beauquier, S. Cantarell, A. K. Datta, and F. Petit. Group mutual exclusion in tree networks. In Proc. of the 9th International Conference on Parallel and Distributed Systems, pages 111-116, 2002. Google Scholar
  5. V. Bhatt and C.C. Huang. Group mutual exclusion in O(log~n) RMR. In Proc. 29th ACM Symp. on Principles of Distributed Computing, pages 45-54, 2010. Google Scholar
  6. G. E. Blelloch, P. Cheng, and P. B. Gibbons. Room synchronization. In Proc. of the 13th Annual Symposium on Parallel Algorithms and Architectures, pages 122-133, 2001. Google Scholar
  7. I. Calciu, D. Dice, Y. Lev, V. Luchangco, V.J. Marathe, and N. Shavit. Numa-aware reader-writer locks. In Proceedings of the 18th ACM symposium on Principles and practice of parallel programming, PPoPP '13, page 157–166, February 2013. Google Scholar
  8. K. M. Chandy and J. Misra. The drinking philosophers problem. ACM Transactions on Programming Languages and Systems, 6:632-646, 1984. Google Scholar
  9. P.L. Courtois, F. Heyman, and D.L Parnas. Concurrent control with Readers and Writers. Communications of the ACM, 14(10):667-668, 1971. Google Scholar
  10. T.S. Craig. Building FIFO and priority-queuing spin locks from atomic swap. Technical Report TR-93-02-02, Dept. of Computer Science, Univ. of Washington, 1993. Google Scholar
  11. R. Danek and V. Hadzilacos. Local-spin group mutual exclusion algorithms. In 18th international symposium on distributed computing, 2004. LNCS 3274 Springer Verlag 2004, 71-85. Google Scholar
  12. E. W. Dijkstra. Solution of a problem in concurrent programming control. Communications of the ACM, 8(9):569, 1965. Google Scholar
  13. R. Dvir and G. Taubenfeld. Mutual exclusion algorithms with constant rmr complexity and wait-free exit code. In Proc. of the 21st international conference on principles of distributed systems (OPODIS 2017), October 2017. Google Scholar
  14. S. Gokhale and N. Mittal. Fast and scalable group mutual exclusion, 2019. URL: http://arxiv.org/abs/1805.04819.
  15. W. Golab and A. Ramaraju. Recoverable mutual exclusion. In Proc. 2016 ACM Symposium on Principles of Distributed Computing, pages 65-74, 2016. Google Scholar
  16. V. Hadzilacos. A note on group mutual exclusion. In Proc. 20th symp. on Principles of distributed computing, pages 100-106, 2001. Google Scholar
  17. Y. He, K. Gopalakrishnan, and E. Gafni. Group mutual exclusion in linear time and space. Theoretical Computer Science, 709:31-47, 2018. Google Scholar
  18. P. Jayanti. Adaptive and efficient abortable mutual exclusion. In Proc. 22nd ACM Symp. on Principles of Distributed Computing, pages 295-304, 2003. Google Scholar
  19. P. Jayanti, S. Jayanti, and S. Jayanti. Towards an ideal queue lock. In Proc. 21st International Conference on Distributed Computing and Networking, ICDCN 2020, pages 1-10, 2020. Google Scholar
  20. P. Jayanti, S. Petrovic, and K. Tan. Fair group mutual exclusion. In Proc. 22th ACM Symp. on Principles of Distributed Computing, pages 275-284, July 2003. Google Scholar
  21. Yuh-Jzer Joung. Asynchronous group mutual exclusion. In Proc. 17th ACM Symp. on Principles of Distributed Computing, pages 51-60, 1998. Google Scholar
  22. Yuh-Jzer Joung. Asynchronous group mutual exclusion. Distributed Computing, 13(4):189-206, 2000. Google Scholar
  23. H. Kakugawa, S. Kamei, and T. Masuzawa. A token-based distributed group mutual exclusion algorithm with quorums. IEEE Transactions on Parallel and Distributed Systems, 19(9):1153-1166, 2008. Google Scholar
  24. P. Keane and M. Moir. A simple local-spin group mutual exclusion algorithm. In Proc. 18th ACM Symp. on Principles of Distributed Computing, pages 23-32, 1999. Google Scholar
  25. P. Keane and M. Moir. A simple local-spin group mutual exclusion algorithm. IEEE Transactions on Parallel and Distributed Systems, 12(7), 2001. Google Scholar
  26. L. Lamport. A new solution of Dijkstra’s concurrent programming problem. Communications of the ACM, 17(8):453-455, 1974. Google Scholar
  27. L. Maor. Constant RMR group mutual exclusion for arbitrarily many processes and sessions. Master’s thesis, The Interdisciplinary Center, Herzliya, Israel, August 2021. Google Scholar
  28. J.M. Mellor-Crummey and M.L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst., 9(1):21–65, 1991. Google Scholar
  29. M. Takamura, T. Altman, and Y. Igarashi. Speedup of Vidyasankar’s algorithm for the group k-exclusion problem. Inf. Process. Lett., 91(2):85-91, 2004. Google Scholar
  30. G. Taubenfeld. Synchronization Algorithms and Concurrent Programming. Pearson / Prentice-Hall, 2006. ISBN 0-131-97259-6, 423 pages. Google Scholar
  31. M. Toyomura, S. Kamei, and H. Kakugawa. A quorum-based distributed algorithm for group mutual exclusion. In Proc. of the 4th International Conference on Parallel and Distributed Computing, Applications and Technologies, pages 742-746, 2003. Google Scholar
  32. K. Vidyasankar. A simple group mutual 𝓁-exclusion algorithm. Inf. Process. Lett., 85(2):79-85, 2003. Google Scholar
  33. Kuen-Pin Wu and Yuh-Jzer Joung. Asynchronous group mutual exclusion in ring networks. In Proc. 13th Inter. Parallel Processing Symposium and 10th Symp. on Parallel and Distributed Processing, pages 539-543, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact