Abstract | ||
---|---|---|
In this paper, we study complexity of anonymous -set agreement algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that in contention-free executions of a -set agreement algorithm, only “fast” read and write operations are performed, and more expensive synchronization primitives, such as CAS, are only used when contention is detected. We call such concurrent implementations and derive the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast -set agreement. |
Year | DOI | Venue |
---|---|---|
2017 | https://doi.org/10.1007/s00446-017-0297-z | Distributed Computing |
Keywords | Field | DocType |
Space Complexity,Base Object,Consensus Algorithm,Step Complexity,Mutual Exclusion Algorithm | Consensus algorithm,Synchronization,Computer science,Implementation,Theoretical computer science | Journal |
Volume | Issue | ISSN |
30 | 6 | 0178-2770 |
Citations | PageRank | References |
1 | 0.36 | 18 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Claire Capdevielle | 1 | 2 | 1.39 |
Colette Johnen | 2 | 364 | 31.21 |
Petr Kuznetsov | 3 | 253 | 30.43 |
Alessia Milani | 4 | 187 | 15.54 |