Collapsibility of read/write models using discrete Morse theory

DOI10.1007/s41468-018-0011-7zbMath1398.68359OpenAlexW2791631471MaRDI QIDQ1616395

R. Smith

Publication date: 6 November 2018

Published in: Journal of Applied and Computational Topology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s41468-018-0011-7

zbMATH Keywords

collapsibilitydistributed computingshared memorydiscrete Morse theorywait-free computingread/write protocols

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ A simplicial complex model for dynamic epistemic logic to study distributed task computability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The topology of distributed adversaries
• Topology of the immediate snapshot complexes
• Iterated chromatic subdivisions are collapsible
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Morse theory for cell complexes
• Discrete Morse theory for the barycentric subdivision
• Chromatic subdivision of a simplicial complex
• Topology of the view complex
• Simplicial complexes of graphs
• The Read/Write Protocol Complex Is Collapsible
• Simulations and reductions for colorless tasks
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The topological structure of asynchronous computability
• A combinatorial characterization of the distributed 1-solvable tasks
• The Iterated Restricted Immediate Snapshot Model
• Impossibility of distributed consensus with one faulty process
• Atomic snapshots of shared memory
• A Note on the Homotopy Type of Wait-Free Atomic Snapshot Protocol Complexes
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• The BG distributed simulation algorithm
• Generalized FLP impossibility result for t-resilient asynchronous computations
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• Towards a topological characterization of asynchronous complexity
• Immediate atomic snapshots and fast renaming
• Combinatorial algebraic topology

This page was built for publication: Collapsibility of read/write models using discrete Morse theory