Generalized FLP impossibility result for t-resilient asynchronous computations

DOI10.1145/167088.167119zbMath1310.68078OpenAlexW2024624176MaRDI QIDQ5248475

Eli Gafni, Elizabeth Borowsky

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167119

Mathematics Subject Classification ID

Related Items (80)

Collapsibility of read/write models using discrete Morse theory ⋮ An algorithmic approach to the asynchronous computability theorem ⋮ 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 ⋮ 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 ⋮ Geometric and combinatorial views on asynchronous computability ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ A computationally intractable problem on simplicial complexes ⋮ Schlegel Diagram and Optimizable Immediate Snapshot Protocol ⋮ Towards a universal construction for transaction-based multiprocess programs ⋮ 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 ⋮ Tasks in modular proofs of concurrent algorithms ⋮ Communication pattern logic: epistemic and topological views ⋮ Iterated chromatic subdivisions are collapsible ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Wait-free computing ⋮ Optimal algorithms for synchronous Byzantine \(k\)-set agreement ⋮ Reaching agreement in the presence of contention-related crash failures ⋮ Partial synchrony based on set timeliness ⋮ Renaming and the weakest family of failure detectors ⋮ 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 ⋮ Closed schedulers: a novel technique for analyzing asynchronous protocols ⋮ The BG distributed simulation algorithm ⋮ Hundreds of impossibility results for distributed computing ⋮ The disagreement power of an adversary ⋮ On set consensus numbers ⋮ A Sound Foundation for the Topological Approach to Task Solvability ⋮ 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 ⋮ The topology of look-compute-move robot wait-free algorithms with hard termination ⋮ 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 ⋮ 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 ⋮ Towards a practical snapshot algorithm ⋮ 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 ⋮ A topological perspective on distributed network algorithms ⋮ Wait-free approximate agreement on graphs ⋮ Classifying rendezvous tasks of arbitrary dimension ⋮ Generalized Universality ⋮ Oblivious Collaboration ⋮ The evolution of non-degenerate and degenerate rendezvous tasks ⋮ 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 ⋮ A classification of wait-free loop agreement tasks

This page was built for publication: Generalized FLP impossibility result for t-resilient asynchronous computations