The read/write protocol complex is collapsible

DOI10.1007/978-3-662-49529-2_14MaRDI QIDQ2802937zbMATH OpenOpenAlexFDO

Authors Fernando G. Benavides, Sergio Rajsbaum

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.05427

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Simplicial sets and complexes in algebraic topology (55U10) Network protocols (68M12) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: The celebrated emph{asynchronous computability theorem} provides a characterization of the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by writing and taking atomic snapshots of a shared memory. Several variations of the model have been proposed (immediate snapshots and iterated immediate snapshots), all equivalent for wait-free solution of decision tasks, in spite of the fact that the protocol complexes that arise from the different models are structurally distinct. The topological and combinatorial properties of these snapshot protocol complexes have been studied in detail, providing explanations for why the asynchronous computability theorem holds in all the models. In reality concurrent systems do not provide processes with snapshot operations. Instead, snapshots are implemented (by a wait-free protocol) using operations that write and read individual shared memory locations. Thus, read/write protocols are also computationally equivalent to snapshot protocols. However, the structure of the read/write protocol complex has not been studied. In this paper we show that the read/write iterated protocol complex is collapsible (and hence contractible). Furthermore, we show that a distributed protocol that wait-free implements atomic snapshots in effect is performing the collapses.

Recommendations

• Collapsibility of read/write models using discrete Morse theory
• Topology of the view complex
• A Note on the Homotopy Type of Wait-Free Atomic Snapshot Protocol Complexes
• The topological structure of asynchronous computability
• Topology of the immediate snapshot complexes

Cited in

(8)

• Collapsibility of read/write models using discrete Morse theory
• Geometric and combinatorial views on asynchronous computability
• Structure theory of flip graphs with applications to weak symmetry breaking
• Chromatic subdivision of a simplicial complex
• Topology of the view complex
• Schlegel diagram and optimizable immediate snapshot protocol
• A Note on the Homotopy Type of Wait-Free Atomic Snapshot Protocol Complexes
• Topology of the immediate snapshot complexes

This page was built for publication: The read/write protocol complex is collapsible

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