The Combinatorial Structure of Wait-Free Solvable Tasks
From MaRDI portal
atomic read/write registerscombinatorial topologyconsensusdistributed systemsrenamingset consensusshared memory systemswait-free solvable tasks
Combinatorial aspects of simplicial complexes (05E45) 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
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
- Wait-free n-set consensus when inputs are restricted
- 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)