Most systems in the real world--for example, computational, physical, or biologicalones--consist of multiple components that on the one hand operateconcurrently, but on the other hand may also interact with each other. Sinceat any time many interactions are possible but not guaranteed, thesesystems exhibit nondeterministic behavior, which makes it challenging topredict in which states the systems may be. Only by modeling suchconcurrent systems in a suitable formal framework and applying rigorousmathematical/logical techniques does an adequate analysis and verificationbecome 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 thealgebraic 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 othercomponents may trigger the activation of the component; an “effect”expression describes which combination of messages the activated componentmay send to other components. These expressions take the form of formalpolynomials where addition represents nondeterministic “choice” andmultiplication represents “simultaneity.” The core topic of the book is todevelop the corresponding algebraic theory and demonstrate its applicationto concrete examples.
In fact, the interpretation of c-estructures coincides very much with the behavior ofPetri nets, another well-known model with which c-estructures share a lot ofsimilarities, in particular an intuitive graphic presentation. However,while Petri nets are described by bipartite graphs consisting of two kindsof nodes, “places” and “transitions,” c-e graphs have only one kindof node labeled by the “cause” and “effect” polynomials. Indeed,these polynomials alone define the dynamic behavior of the system, while theedges of the graph only describe its static structure. This representationof c-e structures yields a very elegant algebraic theory where a system can bedescribed by an algebraic expression and its evolution is shown byrewriting the expression according to the axioms of the quasi-semiring.
The first two chapters introduce the basic ideas in aprecise but illustrative way. In particular, chapter 1 gives the motivationfor the theory, its origins and history, and then presents a very usefulhigh-level survey over the main topics of the remaining chapters. It alsodemonstrates a software tool for developing c-e structures in a graphical wayand having their execution animated. Chapter 2 describes the basic theory ofelementary c-e structures, introduces various equivalent representation forms (aspolynomial-annotated nodes, as graphs, and as linear “arrow-expressions”),and discusses the relationship of c-e structures to Petri nets. Furthermore, it givesvarious 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 5discuss various extensions of elementary c-e structures by nodes that inhibitparticular transitions, by multiple models of “time,” and by abstractions ofc-e structures to “rough” c-e structures. Chapters 7 and 8 further develop the basic theory byanalyzing the syntactical properties of c-e structures (structural decomposition) aswell as semantic properties (verification of safety and liveness). Chapter 9provides an in-depth discussion of the actual relation of c-e structures to Petri nets, andchapters 10 through 12 discuss the properties of “processes” that describe theevolution of c-e activities. Chapter 13 returns to the topic of practicalapplication by modeling various concurrent systems, mostly describingfundamental synchronization and coordination problems in concurrency theoryas well as problems arising in traffic and systems control.
The book is very well written and structured, with information presented in avery compact form. Readers interested in a general overview of thetheory and its potential to applications will be mostly satisfied withchapters 1, 2, and 13; the remaining chapters provide more in-depth informationthat can be read according to one’s interests. The many examples provide good illustrations of the varioustheoretical concepts introduced throughout the book.
As for the potential of the theory itself, the book mainly shines whenillustrating the modeling of concurrent systems. However, actually analyzing such systems with respect to properties of interest isnot 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 processcalculi such as Milner’s calculus of communicating systems (CSS) or thepi-calculus; a comparative evaluation would have been of interest.
Despite these minor misgivings, the book is highly recommended. It presentsan interesting alternative to the well-known theory of Petri nets, withmuch potential that deserves a wider audience.