A Fast Timing Separation of Events Algorithm for Concurrent Systems

Abstract

In this work, we present a fast, polynomial time implementation of the Timing Separation of Events (TSE) Algorithm, with complexity O(E × (V+E). TSE computation is a fundamental problem in the analysis of event-driven, asynchronous systems, when uncertainty is present, and event delays are specified as [min, max] intervals. The maximum or minimum TSE may be needed, based on the timing analysis required. In this work, we present a novel approach to solving the TSE computation problem, which utilises: (1) the Primal-Dual Method Algorithm of [1] to compute the system period and critical cycle, as well as annotate timing offsets to events, based on the minimum delay values, and (2) an unfolding scheme, on the event graph, to compute the maximum delay between source and target. We show that only a maximum of three unfoldings are necessary, based on the relative delays between source and target events. We present results on a set of classical TSE examples. Our results are correct and identical to [2], but our approach resolves the issue of deciding how many unfoldings are needed to achieve periodic behaviour, and is sianificantly faster than all other methods. © 2019 IEEE.