Abstract

In this thesis, we address part of the predicate detection problem on distributed computations. We introduce two new classes of predicates, the monotonic predicates and the separable predicates. These classes generalize several classes of well-known predicates as the conjunctive predicates. We show that these classes are detected efficiently on distributed computations having the series-parallel property. This deviates from the approach used in the past where the detection problem was addressed for small classes of predicates to be detected on general distributed computations. The detection algorithm is based on a decomposition of the state lattice into simple subsets called concurrent intervals. This decomposition has its own interest since it helps understanding the relation between the complexity of the state lattice and the complexity of the event structure. At the heart of this relation is a new structure: the communication graph. We show that the communication graph gives a suitable level of abstraction to deal with the predicate detection problem.