On the uncontended complexity of anonymous agreement

DOI10.1007/s00446-017-0297-zzbMath1419.68028OpenAlexW2595776753MaRDI QIDQ1682223

Claire Capdevielle, Petr Kuznetsov, Alessia Milani, Colette Johnen

Publication date: 29 November 2017

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-017-0297-z

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (3)

Agreeing within a few writes ⋮ On the complexity of basic abstractions to implement consensus ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Tight bounds for adopt-commit objects
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Wait-free algorithms for fast, long-lived renaming
• Anonymous and fault-tolerant shared-memory computing
• Structured derivations of consensus algorithms for failure detectors
• On the Space Complexity of Set Agreement
• Generalized Universality
• On the space complexity of randomized synchronization
• The topological structure of asynchronous computability
• The complexity of obstruction-free implementations
• Impossibility of distributed consensus with one faulty process
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• On deterministic abortable objects
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Long-lived renaming made fast
• A tight space bound for consensus
• On the Uncontended Complexity of Anonymous Consensus
• Distributed Computing
• On the optimal space complexity of consensus for anonymous processes

This page was built for publication: On the uncontended complexity of anonymous agreement