Three-Processor Tasks Are Undecidable

DOI10.1137/S0097539796305766zbMath0918.68027OpenAlexW2042928046MaRDI QIDQ4229418

Eli Gafni, Elias Koutsoupias

Publication date: 22 February 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796305766

zbMATH Keywords

wait-free computationasynchronous distributed computationcontractibility problemtask-solvability

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items (21)

An algorithmic approach to the asynchronous computability theorem ⋮ Unnamed Item ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ The topology of distributed adversaries ⋮ A non-topological proof for the impossibility of \(k\)-set agreement ⋮ Power and limits of distributed computing shared memory models ⋮ Communication Complexity of Wait-Free Computability in Dynamic Networks ⋮ Unnamed Item ⋮ Locality and checkability in wait-free computing ⋮ Hundreds of impossibility results for distributed computing ⋮ Condition-based consensus solvability: a hierarchy of conditions and efficient protocols ⋮ 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 ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Anti-\(\Omega \): the weakest failure detector for set agreement ⋮ A simplicial complex model for dynamic epistemic logic to study distributed task computability ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ Wait-free solvability of colorless tasks in anonymous shared-memory model ⋮ A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks ⋮ Locality and Checkability in Wait-Free Computing ⋮ A classification of wait-free loop agreement tasks

This page was built for publication: Three-Processor Tasks Are Undecidable