Throughout the rest of the book we study the properties of live and bounded free-choice systems. In this chapter, we prove the S-coverability Theorem and the T-coverability Theorem, which state that well-formed free-choice nets can be decomposed in two different ways into simpler nets. Together with Commoner's Theorem, the Coverability Theorems are part of what can be called classical free-choice net theory, developed in the early seventies.

The S-coverability Theorem

Figure 5.1 shows a live and bounded (even 1-bounded) free-choice system that we shall frequently use to illustrate the results of this and the next chapters. Its underlying well-formed free-choice net can be decomposed into the two S-nets shown at the bottom of the figure. Observe that they are connected to the rest of the net only through transitions. We prove in this section that every well-formed free-choice net can be decomposed in this way.

Definition 5.1S-components

Let N′ be the subnet of a net N generated by a nonempty set X of nodes. N′ is an S-component of N if

• •s ∪ s• ⊆ X for every place s of X, and

• N′ is a strongly connected S-net.

The two nets at the bottom of Figure 5.1 are S-components of the net at the top. The subnet generated by {s1, t1,s3, t3,s7,t7} is not an S-component; it satisfies the second condition of Definition 5.1, but not the first.

This chapter presents the main results of the theory of S-systems and T-systems. It is divided into two sections of similar structure, one for each of these two classes. The main results of each section are a Liveness Theorem, which characterizes liveness, a Boundedness Theorem, which characterizes b-boundedness of live systems, and a Reachability Theorem, which characterizes the set of reachable markings of live systems. Additionally, both sections contain a Shortest Sequence Theorem, which states that every reachable marking can be reached by an occurrence sequence whose length is bounded by a small polynomial in the number of transitions of the net (linear in the case of S-systems and quadratic for T-systems).

S-systems

Recall from the Introduction that S-systems are systems whose transitions have exactly one input place and one output place.

Definition 3.1S-nets, S-systems

A net is an S-net if |•t| = 1 = |t•| for every transition t.

A system (N, M0) is an S-system if N is an S-net.

The fundamental property of S-systems is that all reachable markings contain exactly the same number of tokens. In other words, the total number of tokens of the system remains invariant under the occurrence of transitions.

Proposition 3.2Fundamental property of S-systems

Let (N, M0) be an S-system. If M is a reachable marking, then M0(S) = M(S), where S is the set of places of N.

A home marking of a system is a marking which is reachable from every reachable marking; in other words, a marking to which the system may always return. The identification of home markings is an interesting issue in system analysis. A concurrent interactive system performs some initial behaviour and then settles in its ultimate cyclic (repetitive) mode of operation. A typical example of such a design is an operating system which, at boot time, carries out a set of initializations and then cyclically waits for, and produces, a variety of input/output operations. The states that belong to the ultimate cyclic behavioural component determine the central function of this type of system. The markings modelling such states are the home markings.

In Section 8.1 we show that live and bounded free-choice systems have home markings. In Section 8.2 we prove a stronger result: the home markings are the reachable markings which mark all the proper traps of the net.

Existence of home markings

Definition 8.1Home marking

Let (N, M0) be a system. A marking M of the net N is a, home marking of (N, M0) if it is reachable from every marking of [M0〉.

We say that (N, M0) has a home marking if some reachable marking is a home marking.

Using the results of Chapter 3, we can easily prove the following proposition.

Proposition 8.2Home markings of live S- and T-systems

Every reachable marking of a live S-system or a live T-system is a home marking.

Petri nets are one of the most popular formal models of concurrent systems, used by both theoreticians and practitioners. The latest compilation of the scientific literature related to Petri nets, dating from 1991, contains 4099 entries, which belong to such different areas of research as databases, computer architecture, semantics of programming languages, artificial intelligence, software engineering and complexity theory. There are also several introductory texts to the theory and applications of Petri nets (see the bibliographic notes).

The problem of how to analyze Petri nets – i.e., given a Petri net and a property, how to decide if the Petri net satisfies it or not – has been intensely studied since the early seventies. The results of this research point out a very clear trade-off between expressive power and analyzability. Even though most interesting properties are decidable for arbitrary Petri nets, the decision algorithms are extremely inefficient. In this situation it is important to explore the analyzability border, i.e., to identify a class of Petri nets, as large as possible, for which strong theoretical results and efficient analysis algorithms exist.

It is now accepted that this border can be drawn very close to the class of free-choice Petri nets. Eike Best coined the term ‘free-choice hiatus’ in 1986 to express that, whereas there exists a rich and elegant theory for free-choice Petri nets, few of its results can be extended to larger classes. Since 1986, further developments have deepened this hiatus, and reinforced its relevance in Petri net theory.

This chapter introduces elementary definitions, concepts and results concerning arbitrary Petri nets. We start with a short section on mathematical notation. Section 2.2 is devoted to the definition and properties of nets, markings, the occurrence rule and incidence matrices. Section 2.3 defines net systems as nets with a distinguished initial marking. We give formal definitions of some behavioural properties of systems: liveness, deadlock-freedom, place-liveness, boundedness. Section 2.4 introduces S- and T-invariants, an analysis technique used throughout the book. The relationship between these invariants and the behavioural properties of Section 2.3 is discussed.

The chapter includes six simple but important results, which are very often used in later chapters. They are the Monotonicity, Marking Equation, Exchange, Boundedness, and Reproduction Lemma, and the Strong Connectedness Theorem. We encourage the reader to become familiar with them before moving to the next chapters.

Mathematical preliminaries

We use the standard definitions on sets, numbers, relations, sequences, vectors and matrices. The purpose of this section is to fix some additional notations.

Notation 2.1Sets, numbers, relations

Let X and Y be sets. We write X ⊆ Y if X is a subset of Y, including the case X = Y. X ⊂ Y denotes that X is a proper subset of Y, i.e., X ⊆ Y and X ≠ Y. X\Y denotes the set of elements of X that do not belong to Y. |X| denotes the cardinality of X.

Free-choice Petri nets have been around for more than twenty years, and are a successful branch of net theory. Nearly all the introductory texts on Petri nets devote some pages to them. This book is intended for those who wish to go further. It brings together the classical theorems of free-choice theory obtained by Commoner and Hack in the seventies, and a selection of new results, like the Rank Theorem, which were so far scattered among papers, reports and theses, some of them difficult to access.

Much of the recent research which found its way into the book was funded by the ESPRIT II BRA Action DEMON, and the ESPRIT III Working Group CALIBAN. The book is self-contained, in the sense that no previous knowledge of Petri nets is required. We assume that the reader is familiar with naïve set theory and with some elementary notions of graph theory (e.g. path, circuit, strong connectedness) and linear algebra (e.g. linear independence, rank of a matrix). One result of Chapter 4 requires some knowledge of the theory of NP-completeness.

The book can be the subject of an undergraduate course of one semester if the proofs of the most difficult theorems are omitted. If they are included, we suggest the course be restricted to Chapters 1 through 5, which contain most of the classical results on S- and T-systems and free-choice Petri nets. A postgraduate course could cover the whole book.

All chapters are accompanied by a list of exercises.

This book is about ways of developing software that can be executed by parallel computers. Software is one of the most complex and difficult artefacts that humans build. Parallelism increases this complexity significantly. At the moment, parallel software is designed for specific kinds of architectures, and can only be moved from architecture to architecture by large-scale rewriting. This is so expensive that very few applications have been discovered for which the effort is worth it. These are mostly numeric and scientific.

I am convinced that the only way to move beyond this state of affairs and use parallelism in a wide variety of applications is to break the tight connection between software and hardware. When this is done, software can be moved with greater ease from architecture to architecture as new ones are developed or become affordable. One of the main claims of this book is that it is possible to do this while still delivering good performance on all architectures, although not perhaps the optimal wall-clock performance that obsesses the present generation of parallel programmers.

The approach presented in this book is a generalisation of abstract data types, which introduced modularity into software design. It is based on categorical data types, which encapsulate control flow as well as data representation. The semantics of powerful operations on a data type are decoupled from their implementation. This allows a variety of implementations, including parallel ones, without altering software.

Parallel computation has been a physical reality for about two decades, and a major topic for research for at least half that time. However, given the whole spectrum of applications of computers, almost nothing is actually computed in parallel. In this chapter we suggest reasons why there is a great gap between the promise of parallel computing and the delivery of real parallel computations, and what can be done to close the gap.

The basic problem in parallel computation, we suggest, is the mismatch between the requirements of parallel software and the properties of the parallel computers on which it is executed. The gap between parallel software and hardware is a rapidly changing one because the lifespans of parallel architectures are measured in years, while a desirable lifespan for parallel software is measured in decades. The current standard way of dealing with this mismatch is to reengineer software every few years as each new parallel computer comes along. This is expensive, and as a result parallelism has only been heavily used in applications where other considerations outweigh the expense. This is mostly why the existing parallel processing community is so heavily oriented towards scientific and numerical applications – they are either funded by research institutions and are pushing the limits of what can be computed in finite time and space, or they are working on applications where performance is the only significant goal.

Chapter 2 covers desirable model properties and shows how categorical data types satisfy these properties. I developed this view of model properties during 1992 (an early survey of models using them appeared as [179]) and extended and refined it over the next two years. A preliminary version of Chapter 4 was given as a talk at the Workshop on Programming Tools for Parallel Machines at Alimini, Italy, in the summer of 1993.

Chapter 3 is based on Valiant's work which can be found in a series of papers [197,199, 200]. The results on emulation on SIMD architectures appears in [178], although they seem to have been widely understood before that.

The construction of lists as a categorical data type in Chapter 5 follows the general presentation in Grant Malcolm's thesis [138]. An alternative presentation that emphasises the role of adjunctions in the CDT construction is due to Mike Spivey [189]. Much of the category theory on which this work depends was done in the Sixties [25]. The demonstration that lists can be efficiently implemented comes from [178].

The material on software development in Chapter 6 is a selection from a much larger range of material developed in what has become known as the Bird-Meertens formalism [17,31–35]. The material on almost-homomorphisms (and the name) come from work by Murray Cole [55].

The development of operations to compute recurrences (Chapter 7) and the cost calculus for lists (Chapter 8) is joint work by myself and Wentong Cai during 1992, when he was a postdoctoral fellow.

In Chapter 2 we listed some of the requirements that a model for general-purpose parallel computation should satisfy: architecture independence, intellectual abstractness, having a software development methodology, having cost measures, having no preferred scale of granularity, and being efficiently implementable. In Chapter 3, we saw how results about emulation of arbitrary computations on architectures mean that efficient implementability can only be achieved by restricting the communication allowed in computations. In this chapter, we examine existing models and parallel programming languages and see how they measure up to these requirements.

Many of these models were not developed with such an ambitious set of requirements in mind, so it is not a criticism of them if they fail to meet some. Nevertheless, it provides a picture of the current situation. The absence of a popular or standard model, even in particular application domains, and the wide range of models that have been proposed, underline some of the difficulties of using parallelism in a general-purpose way that were discussed in Chapter 2. It is not possible to cover all proposed models for parallel computation, but a representative selection has been included.

There are several other good surveys of programming models from different perspectives. Crooks and Perrott [59] survey models for distributed-memory architectures, particularly those that provide abstractions for data partitioning and distribution. Turcotte [195] surveys models suitable for networks of workstations. Bal et al. [20] survey architecture-specific models.

The distinctions between models and programming languages are not easy to make.