Home
Scholarly Works
An extension of the taxonomy of persistent and...
Journal article

An extension of the taxonomy of persistent and nonviolent steps

Abstract

The design and analysis of concurrent computing systems is often concerned with fundamental behavioural properties involving system activities, e.g., boundedness, liveness, and persistence. This paper is about the latter property and a complementary property of nonviolence. Persistence means that an enabled activity cannot be disabled, whereas nonviolence means that executing an activity does not disable any other enabled activity.Since its introduction in the 1970s, persistence has been investigated assuming that each system activity is a single atomic action, but in the design of Globally Asynchronous Locally Synchronous (GALS) systems one also needs to allow activities represented by steps, each step being a set of simultaneously executed atomic actions. Dealing with step based execution semantics creates a wealth of new fundamental problems and questions. In particular, there are different ways in which the standard notion of persistence (and nonviolence) could be lifted to the level of steps.We provide a rich classification of different types of step based persistence and nonviolence. We first do this for a general model of (step) transition systems. After that, we focus on Petri nets, and introduce a taxonomy of persistent and nonviolent steps and markings. We also characterise key structural properties of persistence and nonviolence, linking these behavioural notions with the presence of self-loops in Petri nets.

Authors

Koutny M; Mikulski Ł; Pietkiewicz-Koutny M

Journal

Information Sciences, Vol. 394, , pp. 299–314

Publisher

Elsevier

Publication Date

July 1, 2017

DOI

10.1016/j.ins.2017.01.037

ISSN

0020-0255

Contact the Experts team