Toward a Topological Characterization of Asynchronous Complexity

DOI10.1137/S0097539701397412MaRDI QIDQ3434995zbMATH OpenFDO

Authors Gunnar Hoest, Nir Shavit

Publication date 3 May 2007

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

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

zbMATH Keywords

approximate agreementasynchronous systemsimmediate snapshotsshared memorysimplicial complexessubdivisionstopology

Mathematics Subject Classification ID

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

Recommendations

• The topological structure of asynchronous computability
• An algorithmic approach to the asynchronous computability theorem
• Geometric and combinatorial views on asynchronous computability
• A simple characterization of asynchronous computations
• A generalized asynchronous computability theorem
• Topology for Computations of Concurrent Automata
• Asynchronous computability theorems for \(t\)-resilient systems
• From geometric semantics to asynchronous computability
• Asynchronous l-complete approximations
• On asynchronous iterations in partially ordered spaces

Cited in

(19)

• An algorithmic approach to the asynchronous computability theorem
• From geometric semantics to asynchronous computability
• Using the topological characterization of synchronous models
• A generalized asynchronous computability theorem
• Schlegel diagram and optimizable immediate snapshot protocol
• A non-topological proof for the impossibility of \(k\)-set agreement
• 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
• Wait-free approximate agreement on graphs
• Wait-free approximate agreement on graphs
• Why Extension-Based Proofs Fail
• Revisionist simulations: a new approach to proving space lower bounds
• Algebraic topology and distributed computing
• The topology of local computing in networks
• The computational power of distributed shared-memory models with bounded-size registers
• A speedup theorem for asynchronous computation with applications to consensus and approximate agreement
• The computational power of distributed shared-memory models with bounded-size registers
• The complexity of full-information iterated protocols
• New combinatorial topology bounds for renaming: the lower bound

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

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