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.