Loading...
Please wait, while we are loading the content...
Similar Documents
Nonatomic mutual exclusion with local spinning (2002)
| Content Provider | CiteSeerX |
|---|---|
| Author | Anderson, James H. Kim, Yong-Jik |
| Description | In Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing |
| Abstract | We present an N-process local-spin mutual exclusion algorithm, based on nonatomic reads and writes, in which each process performs Θ(log N) remote memory references to enter and exit its critical section. This algorithm is derived from Yang and Anderson’s atomic tree-based local-spin algorithm in a way that preserves its time complexity. No atomic read/write algorithm with better asymptotic worst-case time complexity (under the remote-memory-references measure) is currently known. This suggests that atomic memory is not fundamentally required if one is interested in worst-case time complexity. The same cannot be said if one is interested in fast-path algorithms (in which contention-free time complexity is required to be O(1)) or adaptive algorithms (in which time complexity is required to depend only on the number of contending processes). We show that such algorithms fundamentally require memory accesses to be atomic. In particular, we show that for any N-process nonatomic algorithm, there exists a single-process execution in which the lone competing process accesses Ω(log N / log log N) distinct variables to enter its critical section. Thus, fast and adaptive algorithms are impossible even if caching techniques are used to avoid accessing the processors-to-memory interconnection network. 1 |
| File Format | |
| Publisher Date | 2002-01-01 |
| Access Restriction | Open |
| Subject Keyword | Single-process Execution Nonatomic Read Processors-to-memory Interconnection Network Contention-free Time Complexity Process Access Atomic Read N-process Local-spin Mutual Exclusion Algorithm Process Performs Remote-memory-references Measure Atomic Memory Atomic Tree-based Local-spin Algorithm N-process Nonatomic Algorithm Asymptotic Worst-case Time Complexity Fast-path Algorithm Nonatomic Mutual Exclusion Worst-case Time Complexity |
| Content Type | Text |
| Resource Type | Proceeding Conference Proceedings |
