On the invariants of coloured Petri Nets

In this paper, we develop a theorem that enables computation of the place invariants of the union of a finite collection of coloured Petri Nets when the individual nets satisfy certain conditions and their invariants are known. We consider the illustrative examples of the Readers-Writers problem, a resource sharing system, and a network of databases and show how this theorem is a valuable tool in the analysis of concurrent systems.

Coloured Petri net models for automated manufacturing systems

In this paper, we propose an approach, using Coloured Petri Nets (CPN) for modelling flexible manufacturing systems. We illustrate our methodology for a Flexible Manufacturing Cell (FMC) with three machines and three robots. We also consider the analysis of the FMC for deadlocks using the invariant analysis of CPNs.

Performance modelling of a fault-tolerant real-time multiprocessor using stochastic Petri nets

The fault-tolerant multiprocessor (ftmp) is a bus-based multiprocessor architecture with real-time and fault- tolerance features and is used in critical aerospace applications. A preliminary performance evaluation is of crucial importance in the design of such systems. In this paper, we review stochastic Petri nets (spn) and developspn-based performance models forftmp. These performance models enable efficient computation of important performance measures such as processing power, bus contention, bus utilization, and waiting times.

Graphical simulation of Petri Nets

An interactive graphics package for modeling with Petri Nets has been implemented. It uses the VT-11 graphics terminal supported on the PDP-11/35 computer to draw, execute, analyze, edit and redraw a Petri Net. Each of the above mentioned tasks can be performed by selecting appropriate items from a menu displayed on the screen. Petri Nets with a reasonably large number of nodes can be created and analyzed using this package. The number of nodes supported may be increased by making simple changes in the program. Being interactive, the program seeks information from the user after displaying appropriate messages on the terminal. After completing the Petri Net, it may be executed step by step and the changes in the number of tokens may be observed on the screen, at each place. Some properties of Petri Nets like safety, boundedness, conservation and redundancy can be checked using this package. This package can be used very effectively for modeling asynchronous (concurrent) systems with Petri Nets and simulating the model by “graphical execution.”

A new methodology for analyzing distributed systems modeled by petri nets

Distributed computing systems can be modeled adequately by Petri nets. The computation of invariants of Petri nets becomes necessary for proving the properties of modeled systems. This paper presents a two-phase, bottom-up approach for invariant computation and analysis of Petri nets. In the first phase, a newly defined subnet, called the RP-subnet, with an invariant is chosen. In the second phase, the selected RP-subnet is analyzed. Our methodology is illustrated with two examples viz., the dining philosophers' problem and the connection-disconnection phase of a transport protocol. We believe that this new method, which is computationally no worse than the existing techniques, would simplify the analysis of many practical distributed systems.

S-nets: A Petri net based model for performance evaluation of real-time scheduling algorithms

A new class of nets, called S-nets, is introduced for the performance analysis of scheduling algorithms used in real-time systems Deterministic timed Petri nets do not adequately model the scheduling of resources encountered in real-time systems, and need to be augmented with resource places and signal places, and a scheduler block, to facilitate the modeling of scheduling algorithms. The tokens are colored, and the transition firing rules are suitably modified. Further, the concept of transition folding is used, to get intuitively simple models of multiframe real-time systems. Two generic performance measures, called �load index� and �balance index,� which characterize the resource utilization and the uniformity of workload distribution, respectively, are defined. The utility of S-nets for evaluating heuristic-based scheduling schemes is illustrated by considering three heuristics for real-time scheduling. S-nets are useful in tuning the hardware configuration and the underlying scheduling policy, so that the system utilization is maximized, and the workload distribution among the computing resources is balanced.

Reflexive Incidence Matrx (RIM) Representation of Petr Nets

Although incidence matrix representation has been used to analyze the Petri net based models of a system, it has the limitation that it does not preserve reflexive properties (i.e., the presence of selfloops) of Petri nets. But in many practical applications self-loops play very important roles. This paper proposes a new representation scheme for general Petri nets. This scheme defines a matrix called "reflexive incidence matrix (RIM) c which is a combination of two matrices, a "base matrix Cb,,, and a "power matrix CP." This scheme preserves the reflexive and other properties of the Petri nets. Through a detailed analysis it is shown that the proposed scheme requires less memory space and less processing time for answering commonly encountered net queries compared to other schemes. Algorithms to generate the RIM from the given net description and to decompose RIM into input and output function matrices are also given. The proposed Petri net representation scheme is very useful to model and analyze the systems having shared resources, chemical processes, network protocols, etc., and to evaluate the performance of asynchronous concurrent systems.

Invariant-preserving Petri net reduction and conditions for invariant-existence

The use of invariants is an important tool for analysis of distributed and concurrent systems modeled by Petri nets. For a large practical system, the computation of desired invariants by the existing techniques is a time-consuming task. This paper proposes a theoretical foundation for simplified computation of desired invariants. We provide invariant-preserving Petri net reduction rules followed by the conditions for the existence of invariants in various well-structured nets. If an invariant exists, it can be found directly from the net structure using the formulas derived, or by applying the existing techniques on the reduced net.

Extended colored Petri net: An efficient tool for analyzing concurrent systems

This paper proposes a novel and simple definition of general colored Petri nets. This definition is coherent with that of (uncolored) Petri nets, preserves the reflexivity of the original net and is extended to represent inhibitors. Also suggested are systematic and formal merging rules to obtain a well-formed structure of the extended colored Petri net by folding a given uncolored net. Finally, we present a technique to compute colored invariants by selecting colored RP-subnets. On the average, the proposed technique performs better than the existing ones. The analysis procedure is explained through an illustrative example of a three-level interrupt-priority-handler scheme.

Petri net-based modeling of a class of complex digital systems

We present through the use of Petri Nets, modeling techniques for digital systems realizable using FPGAs. These Petri Net models are used for logic validation at the logic design phase. The technique is illustrated by modeling practical circuits. Further, the utility of the technique with respect to timing analysis of the modeled digital systems is considered. Copyright (C) 1997 Elsevier Science Ltd

Decision support requirements for intelligent operation of southern grid in India

Control centers (CC) play a very important role in power system operation. An overall view of the system with information about all existing resources and needs is implemented through SCADA (Supervisory control and data acquisition system) and an EMS (energy management system). As advanced technologies have made their way into the utility environment, the operators are flooded with huge amount of data. The last decade has seen extensive applications of AI techniques, knowledge-based systems, Artificial Neural Networks in this area. This paper focuses on the need for development of an intelligent decision support system to assist the operator in making proper decisions. The requirements for realization of such a system are recognized for the effective operation and energy management of the southern grid in India The application of Petri nets leading to decision support system has been illustrated considering 24 bus system that is a part of southern grid.

Modelling and analysis of the variance in parallelism in parallel computations

In this paper, we introduce an analytical technique based on queueing networks and Petri nets for making a performance analysis of dataflow computations when executed on the Manchester machine. This technique is also applicable for the analysis of parallel computations on multiprocessors. We characterize the parallelism in dataflow computations through a four-parameter characterization, namely, the minimum parallelism, the maximum parallelism, the average parallelism and the variance in parallelism. We observe through detailed investigation of our analytical models that the average parallelism is a good characterization of the dataflow computations only as long as the variance in parallelism is small. However, significant difference in performance measures will result when the variance in parallelism is comparable to or higher than the average parallelism.

Stochastic modelling of flexible manufacturing systems

Mathematical modelling plays a vital role in the design, planning and operation of flexible manufacturing systems (FMSs). In this paper, attention is focused on stochastic modelling of FMSs using Markov chains, queueing networks, and stochastic Petri nets. We bring out the role of these modelling tools in FMS performance evaluation through several illustrative examples and provide a critical comparative evaluation. We also include a discussion on the modelling of deadlocks which constitute an important source of performance degradation in fully automated FMSs.

A decidable temporal logic with repeating values

Various logical formalisms with the freeze quantifier have been recently considered to model computer systems even though this is a powerful mechanism that often leads to undecidability. In this paper, we study a linear-time temporal logic with past-time operators such that the freeze operator is only used to express that some value from an infinite set is repeated in the future or in the past. Such a restriction has been inspired by a recent work on spatio-temporal logics. We show decidability of finitary and infinitary satisfiability by reduction into the verification of temporal properties in Petri nets. This is a surprising result since the logic is closed under negation, contains future-time and past-time temporal operators and can express the nonce property and its negation. These ingredients are known to lead to undecidability with a more liberal use of the freeze quantifier.