The Combinatorial Structure of Wait-Free Solvable Tasks

DOI10.1137/S0097539797330689MaRDI QIDQ3149868zbMATH OpenOpenAlexFDO

Authors 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

atomic read/write registerscombinatorial topologyconsensusdistributed systemsrenamingset consensusshared memory systemswait-free solvable tasks

Mathematics Subject Classification ID

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

Recommendations

• The topological structure of asynchronous computability
• New combinatorial topology bounds for renaming: the upper bound
• Wait-free solvability of equality negation tasks
• New combinatorial topology upper and lower bounds for renaming
• Computable obstructions to wait-free computability

Cited in

(38)

• Collapsibility of read/write models using discrete Morse theory
• Structure theory of flip graphs with applications to weak symmetry breaking
• Renaming and the weakest family of failure detectors
• Gathering identical autonomous systems on a circle using stigmergy
• A simplicial complex model for dynamic epistemic logic to study distributed task computability
• A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring
• Locality and checkability in wait-free computing
• Generalized symmetry breaking tasks and nondeterminism in concurrent objects
• Stability of multi-valued continuous consensus
• An axiomatic approach to computing the connectivity of synchronous and asynchronous systems
• A simple constructive computability theorem for wait-free computation
• An equivariance theorem with applications to renaming
• Locality and checkability in wait-free computing
• The topological structure of asynchronous computability
• Read-write memory and k-set consensus as an affine task
• Schlegel diagram and optimizable immediate snapshot protocol
• scientific article; zbMATH DE number 7228882 (Why is no real title available?)
• A simplicial complex model for dynamic epistemic logic to study distributed task computability
• A non-topological proof for the impossibility of \(k\)-set agreement
• Power and limits of distributed computing shared memory models
• scientific article; zbMATH DE number 2013840 (Why is no real title available?)
• Bounds on the step and namespace complexity of renaming
• The renaming problem in shared memory systems: an introduction
• An equivariance theorem with applications to renaming
• Hundreds of impossibility results for distributed computing
• 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
• Brief announcement: There are plenty of tasks weaker than perfect renaming and stronger than set agreement
• Uniform solvability with a finite number of MWMR registers. (Extended abstract)
• The solvability of consensus in iterated models extended with safe-consensus
• Why Extension-Based Proofs Fail
• Wait-free solvability of equality negation tasks
• Affine Tasks for k-Test-and-Set
• The combinatorial structure of wait-free solvable tasks (extended abstract)
• The computational power of distributed shared-memory models with bounded-size registers
• The computational power of distributed shared-memory models with bounded-size registers
• A combinatorial topology approach to Arrow's impossibility theorem
• New combinatorial topology bounds for renaming: the lower bound

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3149868)