We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Scalable Room Synchronizations.
- Authors
Blelloch, Guy E.; Cheng, Perry; Gibbons, Phillip B.
- Abstract
This paper presents a scalable solution to the group mutual exclusion problem, with applications to linearizable stacks and queues, and related problems. Our solution allows entry and exit from the mutually exclusive regions in O(t[sub r] + τ) time, where t[sub τ] is the maximum time spent in a critical region by a user, and τ is the maximum time taken by any instruction, including a fetch-and-add instruction. This bound holds regardless of the number of users. We describe how stacks and queues can be implemented using two regions, one for pushing (enqueueing) and one for popping (dequeueing). These implementations are particularly simple, are linearizable, and support access in time proportional to a fetch-and-add operation. In addition, we present experimental results comparing room synchronizations with the Keane-Moir algorithm for group mutual exclusion.
- Subjects
GROUP theory; SCALABILITY; QUEUING theory
- Publication
Theory of Computing Systems, 2003, Vol 36, Issue 5, p397
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-003-1081-y