[Talks] Brown CS Colloquium: Raussen talk in Lubrano on 3/23/2000 at 4 PM

[talks-admin@list.cs.brown.edu]

			       CS Colloquium 
		   The Department of Computer Science
			    BROWN UNIVERSITY

			        presents

			    Martin Raussen
		     
		     Aalborg University, Denmark

		  Thursday, March 23, 2000 at 4:00 PM

	          Lubrano Conference Room (CIT 4th floor)

	          Refreshments will be served at 3:45 PM

   ``Di(rected) topology applied to concurrency -- some examples''

			       Abstract

With the increasingly complicated architecture of modern computers,
concurrency theory has become one of the hot topics in Computer
Science. In this talk, I would like to argue that geometry and
topology can contribute in analysing complicated behaviour.

Several people have suggested topological models to ``view''
concurrent behaviour. A classical example is the so-called ``progress
graph'' due to Dijkstra that describes what can happen when several
processes are modifying shared resources. The state space is modelled
as a high-dimensional complex consisting of hypercubes together with a
partial order induced by the irreversibility of time. A schedule is
modelled as an execution path that has to respect this partial
order.

Though the state space tends to ``explode'' with an increasing number
of processes, it is still possible to analyse some of its features by
algorithms cleverly using high-dimensional (not just graph theoretic)
information. Deadlocks and the associated unsafe and unreachable
regions can be found quickly and efficiently. A topological notion
called dihomotopy captures equivalence of executions for various
schedules (joint work with Lisbeth Fajstrup (Aalborg) and \'{E}ric
Goubault (Paris)).

I will mention generalizations of progress graphs, the so-called
higher dimensional automata, that are used to model truly-concurrent
semantics geometrically. In another direction, topological properties
of protocol complexes can be used to decide about the existence of
fault-tolerant impementations of distributed programs (M.~Herlihy et
al.)


  
		 Host: Professor Maurice Herlihy