Computing Reviews

Cause-effect structures : an algebra of nets with examples of applications
Czaja L., Springer International Publishing, New York, NY, 2019. 160 pp. Type: Book
Date Reviewed: 04/12/22

Most systems in the real world--for example, computational, physical, or biological ones--consist of multiple components that on the one hand operate concurrently, but on the other hand may also interact with each other. Since at any time many interactions are possible but not guaranteed, these systems exhibit nondeterministic behavior, which makes it challenging to predict in which states the systems may be. Only by modeling such concurrent systems in a suitable formal framework and applying rigorous mathematical/logical techniques does an adequate analysis and verification become possible. This book presents such a formal framework, that of cause-effect (c-e) structures, which has been mainly developed by the author himself.

The basic idea is to represent a network of interacting components by the algebraic structure of a quasi-semiring whose elements are the components. Two algebraic expressions are associated to each element: a “cause” expression describes which combinations of messages sent by other components may trigger the activation of the component; an “effect” expression describes which combination of messages the activated component may send to other components. These expressions take the form of formal polynomials where addition represents nondeterministic “choice” and multiplication represents “simultaneity.” The core topic of the book is to develop the corresponding algebraic theory and demonstrate its application to concrete examples.

In fact, the interpretation of c-e structures coincides very much with the behavior of Petri nets, another well-known model with which c-e structures share a lot of similarities, in particular an intuitive graphic presentation. However, while Petri nets are described by bipartite graphs consisting of two kinds of nodes, “places” and “transitions,” c-e graphs have only one kind of node labeled by the “cause” and “effect” polynomials. Indeed, these polynomials alone define the dynamic behavior of the system, while the edges of the graph only describe its static structure. This representation of c-e structures yields a very elegant algebraic theory where a system can be described by an algebraic expression and its evolution is shown by rewriting the expression according to the axioms of the quasi-semiring.

The first two chapters introduce the basic ideas in a precise but illustrative way. In particular, chapter 1 gives the motivation for the theory, its origins and history, and then presents a very useful high-level survey over the main topics of the remaining chapters. It also demonstrates a software tool for developing c-e structures in a graphical way and having their execution animated. Chapter 2 describes the basic theory of elementary c-e structures, introduces various equivalent representation forms (as polynomial-annotated nodes, as graphs, and as linear “arrow-expressions”), and discusses the relationship of c-e structures to Petri nets. Furthermore, it gives various concrete application examples of systems modeled as c-e structures.

After these must-read chapters, the book pursues different directions, each of which is covered by a sequence of short chapters. Chapters 3 to 5 discuss various extensions of elementary c-e structures by nodes that inhibit particular transitions, by multiple models of “time,” and by abstractions of c-e structures to “rough” c-e structures. Chapters 7 and 8 further develop the basic theory by analyzing the syntactical properties of c-e structures (structural decomposition) as well as semantic properties (verification of safety and liveness). Chapter 9 provides an in-depth discussion of the actual relation of c-e structures to Petri nets, and chapters 10 through 12 discuss the properties of “processes” that describe the evolution of c-e activities. Chapter 13 returns to the topic of practical application by modeling various concurrent systems, mostly describing fundamental synchronization and coordination problems in concurrency theory as well as problems arising in traffic and systems control.

The book is very well written and structured, with information presented in a very compact form. Readers interested in a general overview of the theory and its potential to applications will be mostly satisfied with chapters 1, 2, and 13; the remaining chapters provide more in-depth information that can be read according to one’s interests. The many examples provide good illustrations of the various theoretical concepts introduced throughout the book.

As for the potential of the theory itself, the book mainly shines when illustrating the modeling of concurrent systems. However, actually analyzing such systems with respect to properties of interest is not given the same depth. Furthermore, while the theory has drawn much inspiration from Petri nets, the resulting algebraic structure has much more in common with process calculi such as Milner’s calculus of communicating systems (CSS) or the pi-calculus; a comparative evaluation would have been of interest.

Despite these minor misgivings, the book is highly recommended. It presents an interesting alternative to the well-known theory of Petri nets, with much potential that deserves a wider audience.

Reviewer:  Wolfgang Schreiner Review #: CR147429

Reproduction in whole or in part without permission is prohibited.   Copyright 2022™
Terms of Use
| Privacy Policy