Name
Abstract | ||
|---|---|---|
First-Come-First-Served (FCFS) mutual exclusion (ME) is the problem of ensuring that processes attempting to concurrently access a shared resource do so one by one, in a fair order. In this paper, we close the complexity gap between FCFS ME and ME in the asynchronous shared memory model where processes communicate using atomic reads and writes only, and do not fail. Our main result is the first known FCFS ME algorithm that makes O(logN) remote memory references (RMRs) per passage and uses only atomic reads and writes. Our algorithm is also adaptive to point contention. More precisely, the number of RMRs a process makes per passage in our algorithm is 茂戮驴( min (k,logN)), where kis the point contention. Our algorithm matches known RMR complexity lower bounds for the class of ME algorithms that use reads and writes only, and beats the RMR complexity of prior algorithms in this class that have the FCFS property. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00446-010-0096-2 | Distributed Computing |
Keywords | Field | DocType |
Leaf Node,Priority Queue,Critical Section,Mutual Exclusion,Distribute Shared Memory | Asynchronous communication,Binary logarithm,Shared memory model,Computer science,Theoretical computer science,Remote memory,Shared resource,Mutual exclusion | Conference |
Volume | Issue | ISSN |
23 | 2 | 0178-2770 |
Citations | PageRank | References |
18 | 0.79 | 28 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Danek | 1 | 29 | 2.40 |
| Wojciech Golab | 2 | 210 | 17.22 |