Jean Krivine (PPS)

Understanding stochastic systems with non local causality analysis.

When distributed systems are combinatorial enough it becomes impossible to represent their state space explicitly, say in terms of a Petri Net. It is however possible to sample computation traces from an initial state given as an algebraic term, equipped with rewriting rules. We may then analyze these traces in order to give programmers or modelers information about the mechanisms of actions that lead to a particular, and possibly unexpected, observable. In order to do so one traditionally defines non- interleaving semantics that allows one to single out true causal event ordering from temporal ordering of events, that mainly result from the non-determinism intrinsic to concurrent systems. An “explanation” of the observable can be given in terms of a sub- trace restricted to the events that (transitively) caused the observation. Yet, this traditional view of causality in concurrency theory such as Mazurkiewicz traces or event structures are essentially too coarse to capture only relevant informations about mechanisms of actions at stake in these large systems. This combinatorial complexity in causality analysis is due to two main factors: first, numerous events that are formally causally related to an observable are in fact delaying the appearance of the observable in the system. Second, traditional definitions of events tend to distinguish occurrences of actions that are essentially the same as far as the observable is concerned. We will discuss a possible extension of classical concurrency theory in order to tackle these two issues. It will consists in a generalization of the notion of commuting (ie concurrent) events.