Deadlocks and critical regions in concurrent systems

In parallel computations, processors using shared resources may lock each other when the resources can only handle one or few requests at a time. The distributed program they execute in collaboration will then stop in a "deadlock''. In certain critical configurations, such a deadlock cannot be avoided regardless the schedule allocating the resources. Dually, one may search for unreachable regions in such a computation. There is a geometric picture for distributed computations and schedules in the framework of ``higher dimensional automata''; 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. This geometric point of view has allowed us to devise and implement algorithms that detect deadlocks and the associated critical or unreachable regions very fast. Generalisations of the algorithms to models that allow branches and loops are under development. Cooperation with Éric Goubault, CEA, Saclay, France and Stefan Sokolowski, Academy of Sciences, Gdansk, Poland