|
Stefan Sokolowski
Homotopy in concurrent processes
854
Abstract
In theories of job scheduling and of distributed computing, there have
been many attempts to introduce tools originating from algebraic and
combinatorial topology, such as homotopy groups. Informally, the
fundamental (or first homotopy) group gives an account of the nature
of ``holes'' in a topological space. In the realm of processes, such
holes may correspond to forbidden configurations; e.g. where more than
one process is within the same critical region.
However, many topological properties, technically necessary for the
construction of the fundamental group, have no counterparts, or only
artificial ones, in concurrent processes. The paths corresponding to
process executions are not cyclic, because time only flows forwards,
and they cannot be as naturally composed as looping paths in
topological spaces. The fundamental ``group'' lacks therefore its
group operations.
This paper puts forward a simple remedy for the shortcomings: if you
cannot find a useful group operation on your homotopy classes, settle
for a less requiring structure, e.g. homotopy cpo-s (explained in this
paper). As will be shown, the transition from vectors of processes to
their homotopy cpo-s is functorial, preserves information about the
``holes'' and abstracts from inessential details. This renders the
approach a potentially useful tool for investigating admissible runs
of concurrent processes.
Key words:
concurrency,
homotopy,
algebraic topology,
fundamental cpo
|
|
 |
 |
