Minicourse on
Geometric
and Topological Methods
in Concurrency
Theory
associated to
LATIN
2002
Venue: Cancun, Mexico
Dates: April 2 - April 6, 2002
Scope of the Minicourse
Mathematical methods have always played a significant role in theoretical
computer science: Discrete mathematics, in particular graph theory
and ordered structures; logics, i.e., proof theory for all kinds of
logics, classical, intuitionistic, modal etc.; and category theory,
cartesian closed categories, topoi etc., have become undispensable
tools. Also general topology has been used for instance in
denotational semantics, with relations to ordered structures in
particular.
Recently, ideas and notions from mainstream geometric and
algebraic topology have entered the scene in Concurrency Theory and
Distributed Systems Theory. They have been applied in particular to problems
dealing with the coordination of multi-processor and distributed
systems. Techniques borrowed from higher-dimensional algebraic and geometric
topology yield concepts, results and algorithms that seemed unreachable with
traditional approaches:
Techniques relying on simplicial combinatorial topology have led to new
theoretical bounds concerning computability of fault-tolerant distributed
protocols. Higher dimensional automata have been modelled as cubical
complexes with a partial order reflecting the time flows, and their homotopy
properties allow to reason about a system's global behaviour. Amongst
others, this approach has led to competitive algorithms detecting deadlocks
and unreachable states in huge state spaces.
Target group and Prerequisites
The minicourse is intended for students (advanced undergraduate and graduate
in mathematics or Computer Science) and researchers with an interest and
curiosity for this new field. Prior knowledge of algebraic topology is not
assumed, and technicalities will be suppressed as much as possible. But of
course, you ought to be fond of mathematical reasoning...
Schedule
The minicourse will consist of five lectures lasting between 1 and 1.5 hours
(including time for questions). The first lecture will take place on
Tuesday, April 2, 2002 - just preceeding the LATIN 2002-schedule. The
remaining lectures will be given within the conference schedule (April 3 -
April 6). It is intended to prepare a set of lecture notes for this
minicourse.
Abstracts of the talks
Organisation
The group of organisers and lecturers consists of:
References
Curious readers can start with this historical note. As
an introductory textbook on topology, we recommend M.A. Armstrong,
Basic Topology, Springer-Verlag. For those with some prerequisites
within algebraic topology, the classical and more advanced texbook on
algebraic topology, J.R. Munkres, Elements of Algebraic Topology,
Addison-Wesley, is a recommendable reference. Allan Hatcher has a very
readable online book Algebraic Topology, which
has recently appeared in
print. For references to lecture notes and journal articles, you may
look at the following web-pages:
In particular, the recent volumes 10 of Math. Struct. in
Comp. Science and 39, issue 2, of Electr. Notes
Theor. Comp. Science have been devoted to this area. Moreover,
three international scientific workshops have been organised on the
topics of the minicourse:
GETCO
1999, GETCO
2000, and GETCO 2001.
The paper Dihomotopy as a tool in state space analysis by E.Goubault
and M.Raussen (ps),
(pdf),
that is to appear in the LATIN conference proceedings, expands on a
substantial part of the tutorial and describes new lines of research
attacking the so-called state space explosion problem via
topological methodology and relates them to formerly used approaches.
Last modified: Fri Mar 8 15:04:16 MET 2002