The solvability of consensus in iterated models extended with safe-consensus

DOI10.1007/S00224-023-10125-ZarXiv1505.01259OpenAlexW1945324215MaRDI QIDQ6056624

Sergio Rajsbaum, R. Conde

Publication date: 30 October 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.01259

zbMATH Keywords

Johnson graphconnectivitylower boundscoalitiondistributed algorithmsconsensuswait-free computingiterated modelssafe-consensus

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Computer system organization (68Mxx) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The topology of distributed adversaries
• The renaming problem in shared memory systems: an introduction
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• An impossibility about failure detectors in the iterated immediate snapshot model
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• A Layered Analysis of Consensus
• An Equivariance Theorem with Applications to Renaming
• Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks
• New combinatorial topology upper and lower bounds for renaming
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The topological structure of asynchronous computability
• Renaming in an asynchronous environment
• The Iterated Restricted Immediate Snapshot Model
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus
• Impossibility of distributed consensus with one faulty process
• Atomic snapshots of shared memory
• Bounds on the time to reach agreement in the presence of timing uncertainty
• Association schemes and coding theory
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• The BG distributed simulation algorithm
• The extended BG-simulation and the characterization of t-resiliency
• The topology of shared-memory adversaries
• An Introduction to the Topological Theory of Distributed Computing with Safe-consensus
• Generalized FLP impossibility result for t-resilient asynchronous computations
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• Immediate atomic snapshots and fast renaming
• New combinatorial topology bounds for renaming
• The Complexity Gap between Consensus and Safe-Consensus

This page was built for publication: The solvability of consensus in iterated models extended with safe-consensus