We consider Pareto analysis of multi-priced timed automata (MPTA) having multiple observers recording costs (to be minimised) and rewards (to be maximised) along a computation. We study the Pareto Domination Problem, which asks whether it is possible to reach a target location such that the accumulated costs and rewards Pareto dominate a given vector. We show that this problem is undecidable in general, but decidable for MPTA with at most three observers. We show the problem to be PSPACE-complete for MPTA recording only costs or only rewards. We also consider an approximate Pareto Domination that is decidable in exponential time with no restrictions on types and number of observers. We develop connections between MPTA and Diophantine equations. Undecidability of the Pareto Domination Problem is shown by reduction from Hilbert's 10th Problem, while decidability for three observers entails translation to a decidable fragment of arithmetic involving quadratic forms.

International audience

Abstract We investigate design-level structural transformations that aim at easier subsequent verification of real-time systems with shared data variables, modelled as networks of extended timed automata (ETA). Our contributions to this end are the following: (1) we first equip ETA with an operator for layered composition , intermediate between parallel and sequential composition. Under certain non-interference and/or precedence conditions imposed on the structure of the ETA networks, the communication closed layer (CCL) laws and associated partial-order (po-) and (layered) reachability equivalences are shown to hold. (2) Next, we investigate (under certain cycle conditions on the ETA) the (reachability preserving) transformations of separation and flattening aimed at reducing the number of cycles of the ETA. (3) We then show that our separation and flattening in (2) may be applied together with the CCL laws in (1), in order to restructure ETA networks such that the verification of layered reachability properties is rendered easier. This interplay of the three structural transformations (separation, flattening, and layering) is demonstrated on an enhanced version of Fischer’s real-time mutual exclusion protocol for access to multiple critical sections.

Abstract This paper adopts the communication closed layer (CCL) concept of Elrad and Francez to the formal reasoning of randomized distributed algorithms. We do so by enriching probabilistic automata (PA) with a layered composition operator, an intermediate between parallel and sequential composition. Layered composition is used to establish probabilistic counterparts of the CCL laws that exploit independence and/or precedence conditions between the constituent PA. The probabilistic CCL laws enable partial order (po-) equivalence when layered composition is replaced by sequential composition. Such po-equivalence induces a purely syntactic partial-order state space reduction via layered separation in compositions of PA while preserving probabilistic next-free linear-time properties. The feasibility of such layered separation is demonstrated on a randomized mutual exclusion algorithm by Kushilevitz and Rabin, complementing an algebraic approach (for analyzing this algorithm) by McIver, Gonzalia, Cohen, and Morgan.

Timed automata (TA) (Alur and Dill, 1994) have emerged as an important formalism for the formal modelling and analysis of timed systems. Reachability analysis forms the core of TA-based verification tools such as UPPAAL (Bengtsson and Yi, 2004), which implement a zone-based forward reachability analysis (FRA) algorithm. We present here a symbolic (zone-based) FRA algorithm for deciding safety (reachability) of TA, which is robust w.r.t clock-drift, and which involves minimal overhead w.r.t the standard FRA algorithm of UPPAAL and is guaranteed to terminate in a number of iterations comparable to the standard case.