Brief Announcement: Fast and Scalable Group Mutual Exclusion

Authors Shreyas Gokhale , Neeraj Mittal



PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.49.pdf
  • Filesize: 229 kB
  • 3 pages

Document Identifiers

Author Details

Shreyas Gokhale
  • The University of Texas at Dallas , Richardson, TX 75080, USA
Neeraj Mittal
  • The University of Texas at Dallas , Richardson, TX 75080, USA

Cite AsGet BibTex

Shreyas Gokhale and Neeraj Mittal. Brief Announcement: Fast and Scalable Group Mutual Exclusion. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.49

Abstract

The group mutual exclusion (GME) problem is a generalization of the classical mutual exclusion problem in which every critical section is associated with a type or session. Critical sections belonging to the same session can execute concurrently, whereas critical sections belonging to different sessions must be executed serially. The well-known read-write mutual exclusion problem is a special case of the group mutual exclusion problem. In a shared memory system, locks based on traditional mutual exclusion or its variants are commonly used to manage contention among processes. In concurrent algorithms based on fine-grained synchronization, a single lock is used to protect access to a small number of shared objects (e.g., a lock for every tree node) so as to minimize contention window. Evidently, a large number of shared objects in the system would translate into a large number of locks. Also, when fine-grained synchronization is used, most lock accesses are expected to be uncontended in practice. Most existing algorithms for the solving the GME problem have high space-complexity per lock. Further, all algorithms except for one have high step-complexity in the uncontented case. This makes them unsuitable for use in concurrent algorithms based on fine-grained synchronization. In this work, we present a novel GME algorithm for an asynchronous shared-memory system that has O(1) space-complexity per GME lock when the system contains a large number of GME locks as well as O(1) step-complexity when the system contains no conflicting requests.

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrent algorithms
Keywords
  • Group Mutual Exclusion
  • Fine-Grained Synchronization
  • Space Complexity
  • Contention-Free Step Complexity

Metrics

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

References

  1. V. Bhatt and C. C. Huang. Group Mutual Exclusion in O(log n) RMR. In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC), pages 45-54, JUL 2010. Google Scholar
  2. R. Danek and V. Hadzilacos. Local-Spin Group Mutual Exclusion Algorithms. In Proceedings of the 18th Symposium on Distributed Computing (DISC), pages 71-85, OCT 2004. Google Scholar
  3. S. Gokhale and N. Mittal. Fast and Scalable Group Mutual Exclusion. Available at http://arxiv.org/abs/1805.04819. Google Scholar
  4. Y. He, K. Gopalakrishnan, and E. Gafni. Group Mutual Exclusion in Linear Time and Space. In Proceedings of the 17th International Conference on Distributed Computing And Networking (ICDCN), JAN 2016. Google Scholar
  5. M. Herlihy and N. Shavit. The Art of Multiprocessor Programming, Revised Reprint. Morgan Kaufmann, 2012. Google Scholar
  6. P. Jayanti, S. Petrovic, and K. Tan. Fair Group Mutual Exclusion. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pages 275-284, JUL 2003. Google Scholar
  7. Y.-J. Joung. Asynchronous Group Mutual Exclusion. Distributed Computing (DC), 13(4):189-206, 2000. Google Scholar
  8. K. Platz. Saturation in Lock-Based Concurrent Data Structures. PhD thesis, Department of Computer Science, The University of Texas at Dallas, 2017. 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