More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
From MaRDI portal
Publication:1260652
DOI10.1006/inco.1993.1043zbMath0776.68016OpenAlexW1981017197MaRDI QIDQ1260652
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
Related Items
Collapsibility of read/write models using discrete Morse theory ⋮ A necessary and sufficient condition for transforming limited accuracy failure detectors ⋮ Synchronous condition-based consensus ⋮ The \(k\)-simultaneous consensus problem ⋮ On the computability power and the robustness of set agreement-oriented failure detector classes ⋮ On the weakest failure detector ever ⋮ Unnamed Item ⋮ Distributed universality ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ The topology of distributed adversaries ⋮ Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement ⋮ A non-topological proof for the impossibility of \(k\)-set agreement ⋮ Power and limits of distributed computing shared memory models ⋮ On the uncontended complexity of anonymous agreement ⋮ Randomized \(k\)-set agreement in crash-prone and Byzantine asynchronous systems ⋮ Tasks in modular proofs of concurrent algorithms ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Life beyond set agreement ⋮ Optimal algorithms for synchronous Byzantine \(k\)-set agreement ⋮ Reaching agreement in the presence of contention-related crash failures ⋮ Partial synchrony based on set timeliness ⋮ Why Extension-Based Proofs Fail ⋮ Optimal algorithms for synchronous Byzantine \(k\)-set agreement ⋮ Stability of long-lived consensus. ⋮ Reaching consensus in the presence of contention-related crash failures ⋮ The Iterated Restricted Immediate Snapshot Model ⋮ Of choices, failures and asynchrony: the many faces of set agreement ⋮ On Byzantine generals with alternative plans ⋮ Locality and checkability in wait-free computing ⋮ The renaming problem in shared memory systems: an introduction ⋮ The Weakest Failure Detector for Message Passing Set-Agreement ⋮ Closed schedulers: a novel technique for analyzing asynchronous protocols ⋮ The BG distributed simulation algorithm ⋮ Objects shared by Byzantine processes ⋮ Hundreds of impossibility results for distributed computing ⋮ Condition-based consensus solvability: a hierarchy of conditions and efficient protocols ⋮ Linear space bootstrap communication schemes ⋮ The disagreement power of an adversary ⋮ On set consensus numbers ⋮ The minimum information about failures for solving non-local tasks in message-passing systems ⋮ Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers ⋮ Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks ⋮ The topology of look-compute-move robot wait-free algorithms with hard termination ⋮ An Introduction to the Topological Theory of Distributed Computing with Safe-consensus ⋮ An impossibility about failure detectors in the iterated immediate snapshot model ⋮ On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems ⋮ Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures ⋮ A note on atomicity: boosting Test\&Set to solve consensus ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Anti-\(\Omega \): the weakest failure detector for set agreement ⋮ Narrowing Power vs. Efficiency in Synchronous Set Agreement ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ Wait-freedom with advice ⋮ A topological treatment of early-deciding set-agreement ⋮ Wait-free solvability of colorless tasks in anonymous shared-memory model ⋮ A necessary condition for Byzantine \(k\)-set agreement ⋮ From adaptive renaming to set agreement ⋮ The Complexity of Early Deciding Set Agreement: How can Topology help? ⋮ Classifying rendezvous tasks of arbitrary dimension ⋮ Generalized Universality ⋮ Structured Derivation of Semi-Synchronous Algorithms ⋮ Recent Results on Fault-Tolerant Consensus in Message-Passing Networks ⋮ t-Resilient Immediate Snapshot Is Impossible ⋮ Contention-related crash failures: definitions, agreement algorithms, and impossibility results ⋮ Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound ⋮ Simultaneous Consensus vs Set Agreement: A Message-Passing-Sensitive Hierarchy of Agreement Problems ⋮ A classification of wait-free loop agreement tasks
