Loading...
Please wait, while we are loading the content...
Similar Documents
Local-spin Mutual Exclusion Using Fetch-and-φ Primitives ∗ ( Extended Abstract )
| Content Provider | Semantic Scholar |
|---|---|
| Author | Anderson, James H. Kim, Yong-Jik |
| Copyright Year | 2002 |
| Abstract | We present a generic fetch-and-φ-based local-spin mutual exclusion algorithm, with O(1) time complexity under the remote-memory-references time measure. This algorithm is “generic” in the sense that it can be implemented using any fetch-and-φ primitive of rank 2N , where N is the number of processes. The rank of a fetch-and-φ primitive is a notion introduced herein; informally, it expresses the extent to which processes may “order themselves” using that primitive. This algorithm breaks new ground because it shows that O(1) time complexity is possible using a wide range of primitives. In addition, previously published fetch-and-φ-based algorithms either use multiple primitives or require an underlying cache-coherence mechanism for spins to be local, while ours does not. By applying our generic algorithm within an arbitration tree, one can easily construct a Θ(logr N) algorithm using any primitive of rank r, where 2 ≤ r < N . For certain primitives of constant rank, we present a slightly more efficient Θ(logN/ log logN) algorithm. It follows from a previously-presented lower bound proof that this algorithm is time-optimal. |
| File Format | PDF HTM / HTML |
| DOI | 10.1109/icdcs.2003.1203505 |
| Alternate Webpage(s) | https://cs.unc.edu/~anderson/papers/icdcs03a.pdf |
| Alternate Webpage(s) | http://www.cs.unc.edu/~anderson/papers/icdcs03a.ps |
| Alternate Webpage(s) | http://www.cs.unc.edu/~anderson/papers/disc02.pdf |
| Alternate Webpage(s) | http://cs.unc.edu/~anderson/papers/icdcs03a.pdf |
| Alternate Webpage(s) | http://www.cs.unc.edu/~anderson/papers/icdcs03a.pdf |
| Alternate Webpage(s) | https://doi.org/10.1109/icdcs.2003.1203505 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
