The Complexity Gap between Consensus and Safe-Consensus

DOI10.1007/978-3-319-09620-9_7MaRDI QIDQ5496149zbMATH OpenOpenAlexFDO

Authors R. Conde, Sergio Rajsbaum

Publication date 7 August 2014

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-09620-9_7

zbMATH Keywords

coalitionconnectivityconsensusdistributed algorithmsiterated modelsJohnson graphlower boundssafe-consensuswait-free computing

Mathematics Subject Classification ID

Distributed systems (68M14) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The solvability of consensus in iterated models extended with safe-consensus
• On the complexity of basic abstractions to implement consensus
• On the uncontended complexity of consensus
• Consensus Algorithms and the Decomposition-Separation Theorem
• Condition-based consensus solvability: a hierarchy of conditions and efficient protocols
• On the nonexistence of resilient consensus protocols
• On the viability of the deterministic consensus hierarchy
• Generalized Irreducibility of Consensus and the Equivalence of t-Resilient and Wait-Free Implementations of Consensus
• An Introduction to the Topological Theory of Distributed Computing with Safe-consensus

Cited in

(6)

• Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus
• An Introduction to the Topological Theory of Distributed Computing with Safe-consensus
• Untangling partial agreement: iterated \(x\)-consensus simulations
• A distributed computing perspective of unconditionally secure information transmission in Russian cards problems
• A distributed computing perspective of unconditionally secure information transmission in Russian cards problems
• The solvability of consensus in iterated models extended with safe-consensus

This page was built for publication: The Complexity Gap between Consensus and Safe-Consensus

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