2026-07-25T01:47:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9838 2024-03-06T10:45:03Z ddc:004 open_access

Brief Announcement: Fast and Scalable Group Mutual Exclusion Gokhale, Shreyas Mittal, Neeraj Group Mutual Exclusion Fine-Grained Synchronization Space Complexity Contention-Free Step Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shreyas Gokhale and Neeraj Mittal 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.49 urn:nbn:de:0030-drops-98381 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.49 eng https://creativecommons.org/licenses/by/3.0/legalcode