Name
Abstract | ||
|---|---|---|
We consider the worst-case remote memory reference (RMR) complexity of first-come-first-served (FCFS) mutual exclusion (ME) algorithms for N asynchronous reliable processes that communicate only by reading and writing shared memory. We exhibit an upper bound of O(log N) RMRs for FCFS ME, which is tight, improves on prior results, and matches a lower bound for ME (with or without FCFS). |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1400751.1400844 | PODC |
Keywords | Field | DocType |
reliable process,worst-case remote memory reference,prior result,complexity gap,fcfs mutual exclusion,fcfs me,mutual exclusion,lower bound,upper bound,shared memory | Binary logarithm,Asynchronous communication,Shared memory,Computer science,Upper and lower bounds,Theoretical computer science,Remote memory,Mutual exclusion,Distributed computing | Conference |
Citations | PageRank | References |
5 | 0.45 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Danek | 1 | 29 | 2.40 |
| Wojciech Golab | 2 | 210 | 17.22 |