On the complexity of basic abstractions to implement consensus

DOI10.1016/J.TCS.2017.12.039MaRDI QIDQ683759zbMATH OpenOpenAlexFDO

Authors Claire Capdevielle, Colette Johnen, Alessia Milani

Publication date 9 February 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2017.12.039

zbMATH Keywords

complexitydistributed computingconsensusshared memorywait-freedomadopt-commitconflict-detectorgrafariusvalue-splitter

Mathematics Subject Classification ID

Distributed algorithms (68W15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Tight bounds for adopt-commit objects
• On the uncontended complexity of anonymous consensus
• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• N-Consensus is the Second Strongest Object for N + 1 Processes

Cites work

• A practical distributed universal construction with unknown participants
• Impossibility of distributed consensus with one faulty process
• Long-lived renaming made fast
• On the uncontended complexity of anonymous agreement
• Randomized protocols for asynchronous consensus
• Round-by-round fault detectors (extended abstract), unifying synchrony and asynchrony
• The complexity of obstruction-free implementations
• Tight bounds for adopt-commit objects
• Unreliable failure detectors for reliable distributed systems
• Wait-free algorithms for fast, long-lived renaming

Cited in

(7)

• The Complexity Gap between Consensus and Safe-Consensus
• Quorum tree abstractions of consensus protocols
• Consensus with an abstract MAC layer
• Principles of Distributed Systems
• On the uncontended complexity of anonymous consensus
• Tight bounds for adopt-commit objects
• Paxos consensus, deconstructed and abstracted

This page was built for publication: On the complexity of basic abstractions to implement consensus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683759)