The Combinatorial Structure of Wait-Free Solvable Tasks

DOI10.1137/S0097539797330689zbMath1015.68080OpenAlexW1975213343MaRDI QIDQ3149868

Hagit Attiya, Sergio Rajsbaum

Publication date: 29 September 2002

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

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

zbMATH Keywords

distributed systemsconsensuscombinatorial topologyrenamingshared memory systemsatomic read/write registersset consensuswait-free solvable tasks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (23)

Collapsibility of read/write models using discrete Morse theory ⋮ An Equivariance Theorem with Applications to Renaming ⋮ Unnamed Item ⋮ Schlegel Diagram and Optimizable Immediate Snapshot Protocol ⋮ A non-topological proof for the impossibility of \(k\)-set agreement ⋮ Power and limits of distributed computing shared memory models ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Renaming and the weakest family of failure detectors ⋮ Gathering identical autonomous systems on a circle using stigmergy ⋮ Why Extension-Based Proofs Fail ⋮ Unnamed Item ⋮ The renaming problem in shared memory systems: an introduction ⋮ Hundreds of impossibility results for distributed computing ⋮ An equivariance theorem with applications to renaming ⋮ Bounds on the Step and Namespace Complexity of Renaming ⋮ 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 ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ A simplicial complex model for dynamic epistemic logic to study distributed task computability ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ Stability of Multi-Valued Continuous Consensus11Preliminary Version, Some proofs are omitted from this version. ⋮ An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems ⋮ A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring

This page was built for publication: The Combinatorial Structure of Wait-Free Solvable Tasks