Schedule and Abstracts

2.4.2002

Introduction to the tutorial. A geometric deadlock algorithm.
The coordination of several concurrent processes imposes severe theoretical and practical problems. Among those are the occurence of deadlocks and questions about safeness and correctness of a concurrent calculation that are difficult to handle in the light of the state space explosion problem . Simple geometric models of the state space of a concurrent program allow to reason about and to shed light on important properties of these programs. A first practical outcome of these considerations is a fast geometrically based algorithm determining deadlocks and unreachable regions in a model for semaphore (lock/unlock) programs.

3.4.2002

Elementary Algebraic Topology I: Homotopy and the Fundamental Group.
Robust geometrical properties can best be investigated by topological methods. One way to obtain computable algebraic information about the geometry is to consider the paths in such a space up to a natural equivalence relation, called homotopy . The equivalence classes of loops can be assembled as the fundamental group of the space. The Seifert-van Kampen theorem allows to calculate fundamental groups ``by recurrence''. Higher homotopy groups generalize the fundamental groups and enjoy nice functorial properties. Although often difficult to calculate, they have shown to be extremely useful in all sorts of geometric/topological considerations.

4.4.2002

The Basics of Directed Topology.
In topological models of concurrency, the direction of time plays a crucial role. In particular, one has to consider directed paths and directed homotopies in partially ordered topological spaces. The fundamental group is then replaced by the fundamental category . Its study seems to be instrumental for many problems in static analysis, on the other hand it seems to be more complicated and is thus much less advanced yet. First results, among them a directed Seifert-van Kampen theorem, a definition and determination of ``diconnected components'' and some of their applications to static analysis will be discussed.

5.4.2002

Combinatorial Models in Topology. Homology Groups.
To investigate topological spaces, one tries often to ``cut them up'' into elementary pieces remembering how to glue those together. This results in several combinatorial models, among them the categories of simplicial and of cubical sets. The latter have a natural interpretation in concurrency - as Higher Dimensional Automata. Homology groups present another invariant of topological spaces and their combinatorial counterparts. They are more difficult to define, but much easier to calculate. One calculational tool, the Mayer-Vietoris long exact sequence, plays a fundamental role in the last lecture.

6.4.2002

Algebraic Topology and Distributed Computing.
In the past several years, a number of researchers have successfully applied techniques from Algebraic Topology to solve a number of long-standing open problems in the theory of distributed and concurrent computing. This talk will describe some basic problems in distributed computing, and how to solve them using notions from elementary Algebraic Topology. We will describe some open problems and possible future directions. This talk is intended for a general audience.

Prior knowledge of algebraic topology is not assumed, and technicalities will be suppressed as much as possible.

Back to announcement