Paper Info
Title
The k-bakery: local-spin k-exclusion using non-atomic reads and writes
Abstract
Mutual exclusion is used to coordinate access to shared resources by concurrent processes. k-Exclusion is a variant of mutual exclusion in which up to k processes can simultaneously access the shared resource. We present the first known shared-memory k-exclusion algorithms that use only atomic reads and writes, have bounded remote memory reference (RMR) complexity, and tolerate crash failures. Our algorithms have RMR complexity O(N) in both the cache-coherent and distributed shared-memory models, where N is the number of processes in the system. Additionally, we present a k-exclusion algorithm that satisfies the First-In-First-Enabled (FIFE) fairness property. FIFE requires that processes become "enabled" to enter the CS roughly in the order that they request access to the shared resource. Finally, we present a modification to the FIFE k-exclusion algorithm that works with non-atomic reads and writes. The high-level structure of all our algorithms is inspired by Lamport's famous Bakery algorithm.
Year
DOI
Venue
2010
10.1145/1835698.1835707
PODC
Keywords
Field
DocType
k-exclusion algorithm,fife k-exclusion algorithm,local-spin k-exclusion,shared-memory model,concurrent process,crash failure,famous bakery algorithm,shared resource,shared-memory k-exclusion algorithm,rmr complexity,mutual exclusion,distributed shared memory,satisfiability,shared memory,cache coherence
Spin-½,Lamport's bakery algorithm,Shared memory,Computer science,Parallel computing,Theoretical computer science,Shared resource,Remote memory,Mutual exclusion,Distributed computing,Bounded function
Conference
Citations 
PageRank 
References 
2
0.37
17
Authors
1
Name
Order
Citations
PageRank
Robert Danek1292.40