Toggle Main Menu Toggle Search

Open Access padlockePrints

An Extension of the Taxonomy of Persistent and Nonviolent Steps

Lookup NU author(s): Professor Maciej KoutnyORCiD, Dr Lukasz Mikulski, Dr Marta Koutny

Downloads


Licence

This work is licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0).


Abstract

The design and analysis of concurrent computing systems is often concerned with fundamental behavioural propertiesinvolving 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, whereasnonviolence 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 aredifferent 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 persistentand 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.


Publication metadata

Author(s): Koutny M, Mikulski L, Pietkiewicz-Koutny M

Publication type: Article

Publication status: Published

Journal: Information Sciences

Year: 2017

Volume: 394-395

Pages: 299-314

Print publication date: 01/07/2017

Online publication date: 31/01/2017

Acceptance date: 31/01/2017

Date deposited: 31/01/2017

ISSN (print): 0020-0255

ISSN (electronic): 1872-6291

Publisher: Elsevier Inc.

URL: http://dx.doi.org/10.1016/j.ins.2017.01.037

DOI: 10.1016/j.ins.2017.01.037


Altmetrics

Altmetrics provided by Altmetric


Funding

Funder referenceFunder name
2013/09/D/ST6/03928
EP/I038551/1
EP/K001698/1EPSRC

Share