More choices allow more faults: Set consensus problems in totally asynchronous systems

DOI10.1006/INCO.1993.1043MaRDI QIDQ1260652zbMATH OpenOpenAlexFDO

Authors Soma Chaudhuri

Publication date 30 August 1993

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1993.1043

zbMATH Keywords

consensus problemprotocolstotally asynchronous system

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Recommendations

• The combined power of conditions and failure detectors to solve asynchronous set agreement
• Randomized k-set agreement in crash-prone and Byzantine asynchronous systems
• Failure detectors to solve asynchronous \(k\)-set agreement: a glimpse of recent results
• The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement
• scientific article; zbMATH DE number 2013840
• Tight bounds for connectivity and set agreement in Byzantine synchronous systems
• The Election Problem in Asynchronous Distributed Systems with Bounded Faulty Processes

Cited in

(80)

• Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound
• scientific article; zbMATH DE number 7561451 (Why is no real title available?)
• Anti-\(\Omega \): the weakest failure detector for set agreement
• scientific article; zbMATH DE number 2013840 (Why is no real title available?)
• The complexity of early deciding set agreement: how can topology help?
• Condition-based consensus solvability: a hierarchy of conditions and efficient protocols
• Reaching consensus in the presence of contention-related crash failures
• Synchronous condition-based consensus
• A non-topological proof for the impossibility of \(k\)-set agreement
• Power and limits of distributed computing shared memory models
• The topology of look-compute-move robot wait-free algorithms with hard termination
• Recent results on fault-tolerant consensus in message-passing networks
• A necessary and sufficient condition for transforming limited accuracy failure detectors
• On Byzantine generals with alternative plans
• Narrowing Power vs. Efficiency in Synchronous Set Agreement
• On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems
• A note on atomicity: boosting Test\&Set to solve consensus
• Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures
• An impossibility about failure detectors in the iterated immediate snapshot model
• Generalized symmetry breaking tasks and nondeterminism in concurrent objects
• Closed schedulers: a novel technique for analyzing asynchronous protocols
• The \(k\)-simultaneous consensus problem
• Structured Derivation of Semi-Synchronous Algorithms
• A topological treatment of early-deciding set-agreement
• Contention-related crash failures: definitions, agreement algorithms, and impossibility results
• A necessary condition for Byzantine \(k\)-set agreement
• Classifying rendezvous tasks of arbitrary dimension
• The topology of distributed adversaries
• Hundreds of impossibility results for distributed computing
• Collapsibility of read/write models using discrete Morse theory
• Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks
• Locality and checkability in wait-free computing
• Randomized \(k\)-set agreement in crash-prone and Byzantine asynchronous systems
• From wait-free to arbitrary concurrent solo executions in colorless distributed computing
• The Weakest Failure Detector for Message Passing Set-Agreement
• The disagreement power of an adversary
• Reaching agreement in the presence of contention-related crash failures
• Simultaneous consensus vs set agreement: a message-passing-sensitive hierarchy of agreement problems
• Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
• Life beyond set agreement
• From adaptive renaming to set agreement
• The BG distributed simulation algorithm
• On set consensus numbers
• The minimum information about failures for solving non-local tasks in message-passing systems
• Partial synchrony based on set timeliness
• The renaming problem in shared memory systems: an introduction
• On the computability power and the robustness of set agreement-oriented failure detector classes
• New combinatorial topology bounds for renaming: the lower bound
• Stability of long-lived consensus.
• The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement
• Distributed universality
• On the uncontended complexity of anonymous agreement
• The combined power of conditions and failure detectors to solve asynchronous set agreement
• Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers
• Generalized Universality
• From binary consensus to multivalued consensus in asynchronous message-passing systems
• The Iterated Restricted Immediate Snapshot Model
• On the weakest failure detector ever
• A classification of wait-free loop agreement tasks
• Linear space bootstrap communication schemes
• Objects shared by Byzantine processes
• Algebraic topology and distributed computing
• Tasks in modular proofs of concurrent algorithms
• Of choices, failures and asynchrony: the many faces of set agreement
• Why Extension-Based Proofs Fail
• An Introduction to the Topological Theory of Distributed Computing with Safe-consensus
• scientific article; zbMATH DE number 7561269 (Why is no real title available?)
• Optimal algorithms for synchronous Byzantine \(k\)-set agreement
• Optimal algorithms for synchronous Byzantine \(k\)-set agreement
• Wait-free solvability of colorless tasks in anonymous shared-memory model
• \(t\)-resilient immediate snapshot Is impossible
• The combinatorial structure of wait-free solvable tasks (extended abstract)
• Understanding the set consensus partial order using the Borowsky-Gafni simulation (extended abstract)
• Untangling partial agreement: iterated \(x\)-consensus simulations
• The solvability of consensus in iterated models extended with safe-consensus
• Tasks in modular proofs of concurrent algorithms
• Wait-freedom with advice
• scientific article; zbMATH DE number 1950670 (Why is no real title available?)
• Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement
• scientific article; zbMATH DE number 7228882 (Why is no real title available?)

This page was built for publication: More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems

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