Overtaking in Asynchronous Periodic Systems
David H. Pitt, Michael W. Shields · Formal Aspects of Computing · 1999
Abstract. In this paper, we investigate the structure of the asynchronous behaviour of systems of cyclical, deterministic sequential processes. Specifically, we find conditions which, under certain finiteness assumptions, characterise periodic behaviours and pseudo-periodic behaviours, where a behaviour is periodic if it goes through a sequence of periods, i.e. of behaviours in which each active process executes one complete cycle, and a behaviour is pseudo-periodic, if it can be viewed as being composed of periods, possibly not happening in sequence. Thus, every periodic behaviour is pseudo-periodic. We identify a property, no overtaking, which a pseudo-periodic behaviour must have in order to be periodic.