Algebraic topology and concurrency
This article outlines a way in which algebraic topology can be applied to concurrency theory. The state of a concurrent computation can be represented by a configuration space in which each point stands for the locations of the participating processes in their tasks. Thus a computation involving just two processes could have as its ``state the pair of program counters representing the state of each component process. In a quite natural way this space is ``locally partially ordered. The `locally' being necessitated by the fact that a process may have a built in loop structure. When mutual exclusions between processes need to be taken into account, as will be the case in access to shared memory, there will be forbidden regions in the configuration space, corresponding to violations of the mutual exclusion, indeed there are also deadlock regions from which the processes cannot escape to complete their tasks. The computer scientist is interested in restricting the processes to those paths that allow them to run to completion. The algebraic topologist is interested in determining how many different paths there are in the configuration space. This paper constructs a directed homotopy theory of these configuration spaces based on a notion of cubical set, not unlike cubical homology except that the cubes have a partial ordering on them. The results are applied to prove the safeness of a two-phase protocol. The paper concludes with a list of interesting problems in the area. The paper has an extensive bibliography which will be of great use to persons interested in pursuing work in this area.
- A Correctness Condition for High-Performance Multiprocessors
- A finiteness condition for rewriting systems
- A simple constructive computability theorem for wait-free computation
- Algebraic spans
- Colimit theorems for relative homotopy groups
- Complete rewriting systems and homology of monoid algebras
- Components of the fundamental category
- Concurrent transition systems
- Dicovering spaces
- Dipaths and dihomotopies in a cubical complex
- Extraction of concurrent processes from higher dimensional automata
- From concurrency to algebraic topology
- Generalized FLP impossibility result for t-resilient asynchronous computations
- Homologie singulière des espaces fibrés. Applications
- Homotopy invariants of higher dimensional categories and concurrency in computer science
- scientific article; zbMATH DE number 2086216 (Why is no real title available?)
- scientific article; zbMATH DE number 996442 (Why is no real title available?)
- scientific article; zbMATH DE number 1803729 (Why is no real title available?)
- scientific article; zbMATH DE number 4210420 (Why is no real title available?)
- scientific article; zbMATH DE number 3676806 (Why is no real title available?)
- scientific article; zbMATH DE number 3706504 (Why is no real title available?)
- scientific article; zbMATH DE number 3502307 (Why is no real title available?)
- scientific article; zbMATH DE number 1231557 (Why is no real title available?)
- scientific article; zbMATH DE number 709538 (Why is no real title available?)
- scientific article; zbMATH DE number 2051884 (Why is no real title available?)
- scientific article; zbMATH DE number 1372681 (Why is no real title available?)
- scientific article; zbMATH DE number 3213310 (Why is no real title available?)
- Impossibility of distributed consensus with one faulty process
- Investigation of concurrent processes by means of homotopy functors
- On the algebra of cubes
- On the classification of dipaths in geometric models for concurrency
- On the expressiveness of higher dimensional automata
- On the robustness of Herlihy's hierarchy
- Renaming in an asynchronous environment
- Robust wait-free hierarchies
- Set consensus using arbitrary objects (preliminary version)
- Some geometric perspectives in concurrency theory
- State spaces and dipaths up to dihomotopy
- The Anick resolution
- The asynchronous computability theorem for t-resilient tasks
- The geometry of semaphore programs
- The geometry of timed PV programs
- Topological deformation of higher dimensional automata
- Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
- Trace spaces in a pre-cubical complex
- A convenient category of locally preordered spaces
- Some geometric perspectives in concurrency theory
- Geometric and combinatorial views on asynchronous computability
- Directed homology theories and Eilenberg-Steenrod axioms
- Higher fundamental groupoids for spaces
- Combinatorial conditions for directed collapsing
- On symmetric higher-dimensional automata and bisimilarity
- Homology of spaces of directed paths on Euclidean cubical complexes
- Saturating directed spaces
- Spaces of directed paths on pre-cubical sets II
- Pair component categories for directed spaces
- Labeled homology of higher-dimensional automata
- Cubical approximation for directed topology. I
- The trace space of the \(k\)-skeleton of the \(n\)-cube
- Homology groups of cubical sets
- Stable components of directed spaces
- Weak morphisms of higher dimensional automata
- Components of the fundamental category. II
- Directed algebraic topology, categories and higher categories
- Invariants of directed spaces
- A model category for local po-spaces
- Directed algebraic topology and concurrency. With a foreword by Maurice Herlihy and a preface by Samuel Mimram
- Dipaths and dihomotopies in a cubical complex
- History-preserving bisimilarity for higher-dimensional automata via open maps
- Homomorphism complexes, reconfiguration, and homotopy for directed graphs
- Infinitely running concurrent processes with loops from a geometric viewpoint
- From concurrency to algebraic topology
- Topological abstraction of higher-dimensional automata
- Context for models of concurrency
- A framework for component categories
- Comparing topological models for concurrency
- A fibration category of local pospaces
- Criteria for homotopic maps to be so along monotone homotopies
- Sheaves and geometric logic and applications to modular verification of complex systems
- A case for po-manifolds -- in chase after a good topological model for concurrency
- Crossed complexes and higher homotopy groupoids as noncommutative tools for higher dimensional local-to-global problems
- Future path-components in directed topology
- ST-structures
- scientific article; zbMATH DE number 17695 (Why is no real title available?)
- scientific article; zbMATH DE number 1206113 (Why is no real title available?)
- Simplicial models for trace spaces. II: General higher dimensional automata
- On the classification of dipaths in geometric models for concurrency
- Homology for higher-rank graphs and twisted \(C^*\)-algebras
- Homology of Spaces of Directed Paths in Euclidean Pattern Spaces
- Unique decomposition of homogeneous languages and application to isothetic regions
- Investigation of concurrent processes by means of homotopy functors
- The geometry of conservative programs
- Sculptures in concurrency
- A Hurewicz model structure for directed topology
- Inessential directed maps and directed homotopy equivalences
- Configuration spaces and directed paths on the final precubical set
- Languages of higher-dimensional automata
- Stratified spaces, directed algebraic topology, and state-sum TQFTs
- Towards directed collapsibility (research)
- Simplicial Models for Concurrency
- Formal relationships between geometrical and classical models for concurrency
- Streams, \(d\)-spaces and their fundamental categories
- The Boolean algebra of cubical areas as a tensor product in the category of semilattices with zero
- On the hierarchy of d-structures
- Trace spaces of directed tori with rectangular holes
- On execution spaces of PV-programs
- Cut-off theorems for the \textit{PV}-model
- The homology digraph of a preordered space
- Non-existing and ill-behaved coequalizers of locally ordered spaces
- Single-set cubical categories and their formalisation with a proof assistant
- Syntactic regions for concurrent programs
- The topology of critical processes. III: Computing homotopy
- Persistent homology of partially ordered spaces
- Directed path spaces via discrete vector fields
- Spaces of directed paths on pre-cubical sets
- The directed Van Kampen theorem in Lean
- Cubical approximation for directed topology. II
- Some collapsing operations for 2-dimensional precubical sets
- Non-Hausdorff parallelized manifolds over geometric models of conservative programs
- On the topology of concurrent systems
- Directed homology and persistence modules
- Kleene theorem for higher-dimensional automata
- Cubical local partial orders on cubically subdivided spaces -- existence and construction
- Deadlocks and dihomotopy in mutual exclusion models
- Geometric analysis of nondeterminacy in dynamical systems
- Simplicial models of trace spaces
This page was built for publication: Algebraic topology and concurrency
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500494)
