Geometric analysis of mutual exclusion models

In parallel computations, processors using shared resources may lockeach other when the resources can only handle one or few requests at atime.  The distributed program they execute in collaboration will thenstop in a ``deadlock''. In certain critical configurations, such a deadlock cannot be avoided regardless the schedule allocating theresources.  Dually, one may search for unreachable regions in such a computation.There is a geometric picture for distributed computations andschedules in the framework of ``higher dimensional automata'' (HDA); it models, in particular, non-commutativity with respect to access to shared resources. In this picture, a schedule corresponds to a geometric path respecting monotonicity properties modelling the time-flow; a deadlock corresponds to a point from which no such path can propagate; an unreachable point cannot be accessed by a directed path. The geometric point of view has allowed us to devise and implement algorithms that detect deadlocks and the associated criticalor unreachable regions very fast.Current research focuses on algorithms that determine the essentially different (non-dihomotopic) schedules through a concurrent program and on an algorithmic determination of the components of the fundamental category of a HDA. Joint with Éric Goubault, CEA, Saclay, France