Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
From MaRDI portal
Publication:4943878
DOI10.1137/S0097539796307698zbMath0952.68159OpenAlexW1967858331WikidataQ56386813 ScholiaQ56386813MaRDI QIDQ4943878
Fotios Zaharoglou, Michael E. Saks
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539796307698
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Generalities in topology (54A99)
Related Items
Collapsibility of read/write models using discrete Morse theory ⋮ The \(k\)-simultaneous consensus problem ⋮ On the computability power and the robustness of set agreement-oriented failure detector classes ⋮ Unnamed Item ⋮ A Separation of n-consensus and (n + 1)-consensus Based on Process Scheduling ⋮ The Computability of Relaxed Data Structures: Queues and Stacks as Examples ⋮ Distributed universality ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ The topology of distributed adversaries ⋮ Bounded disagreement ⋮ 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 ⋮ Agreeing within a few writes ⋮ On the uncontended complexity of anonymous agreement ⋮ Randomized \(k\)-set agreement in crash-prone and Byzantine asynchronous systems ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Impure Simplicial Complexes: Complete Axiomatization ⋮ 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 ⋮ The Iterated Restricted Immediate Snapshot Model ⋮ Of choices, failures and asynchrony: the many faces of set agreement ⋮ Tight bounds for \(k\)-set agreement with limited-scope failure detectors ⋮ Waiting in concurrent algorithms ⋮ The renaming problem in shared memory systems: an introduction ⋮ The Weakest Failure Detector for Message Passing Set-Agreement ⋮ Hundreds of impossibility results for distributed computing ⋮ 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 ⋮ A closer look at fault tolerance ⋮ Tight bounds on the round complexity of distributed 1-solvable tasks ⋮ Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers ⋮ The computability of relaxed data structures: queues and stacks as examples ⋮ An Inductive-style Procedure for Counting Monochromatic Simplexes of Symmetric Subdivisions with Applications to Distributed Computing ⋮ An Introduction to the Topological Theory of Distributed Computing with Safe-consensus ⋮ On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems ⋮ Algebraic topology and concurrency ⋮ Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures ⋮ 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 ⋮ A simplicial complex model for dynamic epistemic logic to study distributed task computability ⋮ 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 approximate agreement on graphs ⋮ From adaptive renaming to set agreement ⋮ An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems ⋮ Wait-free approximate agreement on graphs ⋮ Generalized Universality ⋮ Oblivious Collaboration ⋮ Asynchronous Coordination Under Preferences and Constraints ⋮ 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 ⋮ Unnamed Item ⋮ Back to the Coordinated Attack Problem ⋮ Simultaneous Consensus vs Set Agreement: A Message-Passing-Sensitive Hierarchy of Agreement Problems
