Directed algebraic topology and concurrency

Description

In recent years, methods from algebraic topology in pure mathematics have been applied to model parallelism in computer networks and in concurrent software, and its effects on the complexity of coordination algorithms. A non-concurrent execution of a program is classically modelled as a (1-dimensional) directed graph. A concurrent execution should however be seen as a trajectory on a multi-dimensional space -- one dimension per process. Moreover, that space has to model restrictions due to synchronizations and the direction of the time-flow.Particularly attractive models are the so-called higher-dimensional automata (HDA), which can be described as cubical complexes with a (local) partial order or as directed spaces. It is the aim of the project to combine mathematical methods from homotopy theory and geometry with combinatorial methods in the study of these automata, their properties and their limitations with respect to parallelcomputations. Current research attempts to apply modified homotopynotions to the classification of both executions and states. This includes a comparison of various notions for dihomotopy, a study of trace, fundamental and higher homotopy and homology categories of a directed space and their ``components'' and a topological interpretation of simulations/bisimulations of HDA.  Notions and methods from category theory and relativity theory adjusted to the situation have shown to be useful.Though the methods are quite general and theoretically minded, possible applications range from the understanding of distributed databases to program analysis and verification since they provide newtools in attacking the state space explosion problem. Joint with Éric Goubault and Emmanuel Haucourt, CEA, Saclay, France.
StatusActive
Effective start/end date19/05/2010 → …