Perturbation Tracking

The complexity of tracking perturbations in discrete event dynamic systems (DEDS) depends on the systems' perturbation propagation mechanism and on the length of the event trace. Existing perturbation propagation algorithms assume that all unperturbed event times are observed and that all perturbed times are required. This paper concerns a complementary approach, termed perturbation tracking (PT), that accurately tracks perturbations in systems for which only a subset of event times are known. We apply PT to a class of partiallyobserved, timed Petri nets and show that for accurate tracking it is necessary and sufficient to know the token holding times between observations. We conclude with an example, motivated by a practical software monitoring problem, that illustrates how this information can be derived from structural and event trace analysis. Not surprisingly, the perturbation propagation rules of our PT algorithm are closely related to the existing algorithms when all event timin..