AVOIDING SHARED CLOCKS IN NETWORKS OF TIMED AUTOMATA
Networks of timed automata (NTA) are widely used to model distributed real-time systems. Quite often in the literature, the automata are allowed to share clocks, i.e. transitions of one automaton may be guarded by conditions on the value of clocks reset by another automaton. This is a problem when one considers implementing such model in a distributed architecture, since reading clocks a priori requires communications which are not explicitly described in the model. We focus on the following question: given an NTA A(1)'parallel to A(2)' where A(2) reads some clocks reset by A(1), does there exist an NTA A(1)'parallel to| A(2)' without shared clocks with the same behavior as the initial NTA? For this, we allow the automata to exchange information during synchronizations only, in particular by copying the value of their neighbor's clocks. We discuss a formalization of the problem and define an appropriate behavioural equivalence. Then we give a criterion using the notion of contextual timed transition system, which represents the behavior of A(2) when in parallel with A(1). Finally, we effectively build A(1)' || A(2)' when it exists.
shared clocks networks of timed automata contextual timed transition system implementation on distributed architecture behavioral equivalence for distributed systems