loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
23rd IEEE International Conference on Distributed Computing Systems (ICDCS'03)
Local-spin Mutual Exclusion Using Fetch-and-\phi Primitives
Providence, Rhode Island
May 19-May 22
ISBN: 0-7695-1920-2
James H. Anderson, University of North Carolina at Chapel Hill
Yong-Jik Kim, University of North Carolina at Chapel Hill
We present a generic fetch-and-\phi-based local-spin mutual exclusion algorithm with O(1) time complexity under the RMR (remote-memory-reference) measure. This algorithm is "generic" in the sense that it can be implemented using any fetch-and-\phi primitive of rank 2N, where N is the number of processes. The rank of a fetch-and-\phi primitive expresses the extent to which processes may "order themselves" using that primitive. By using an arbitration tree, a \Theta(logr N) algorithm can be constructed using any primitive of rank r, where 2 \le r \< N. For primitives that meet a certain additional condition, we present a \Theta(log N / log log N) algorithm, which is time-optimal for certain primitives of constant rank.
Citation:
James H. Anderson, Yong-Jik Kim, "Local-spin Mutual Exclusion Using Fetch-and-\phi Primitives," icdcs, pp.538, 23rd IEEE International Conference on Distributed Computing Systems (ICDCS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.