Early detection of timing constraint violation at runtime

As real time applications become more complex and distributed, monitoring for timing constraint compliance becomes more important in facilitating the enforcement of conditional guarantees and for recovery purposes. C.E. Chodrow et al. (1991) described a O(n/sup 3/) satisfiability checking algorithm for timing constraint monitoring at each check point, where n is the number of time terms in the timing constraint specification. We show that a timing violation can be caught as early as possible by deriving and monitoring a minimum set of timing constraints from the timing constraint specification. We show that only O(n) time is needed in the worst case for checking at each check point. An implementation based on the results reported herein appears in a companion paper (A.K. Mok and G. Liu, 1997).