Toward a Topological Characterization of Asynchronous Complexity

DOI10.1137/S0097539701397412zbMath1112.68062MaRDI QIDQ3434995

Nir Shavit, Gunnar Hoest

Publication date: 3 May 2007

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

zbMATH Keywords

simplicial complexestopologyasynchronous systemsshared memorysubdivisionsapproximate agreementimmediate snapshots

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Schlegel Diagram and Optimizable Immediate Snapshot Protocol ⋮ A non-topological proof for the impossibility of \(k\)-set agreement ⋮ Why Extension-Based Proofs Fail ⋮ 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 ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Wait-free approximate agreement on graphs ⋮ Wait-free approximate agreement on graphs

This page was built for publication: Toward a Topological Characterization of Asynchronous Complexity