Ian Ozsvald (iano@cogs.susx.ac.uk)
Book under review:
M. J. Poole (Uni. of Wales, Swansea) and J. V. Tucker (Uni. of Wales, Swansea),
Synchronous Concurrent Algorithms,
(in preparation), Department of Computer Science, University of Wales, Swansea, 1998, 133 pages.
This book is an introduction to the concept of a Synchronous Concurrent Algorithm (SCA), a mathematical notion developed to unify several related algorithms which ease the comparison and study of dynamical systems. An SCA is a ``deterministic parallel algorithm which processes infinite streams of data, and whose operation is governed by one or more clocks'' [Preface, iii].
It is written by Doctor Poole and Professor Tucker who have been teaching a course in SCAs at the University of Wales, Swansea, since 1995. This theory was first developed by Professor Tucker in 1983 and has since matured during its teaching at the University.
The book is aimed at ``mathematicians, scientists and engineers who wish to learn about the theory of computing'' [Preface, iii]. The book has a formal and clear style, as it is intended to be a teaching aid for students as well as professionals.
There are four main aims to the book:
The book opens by explaining the concept of an SCA, looking briefly at parallel hardware and physical models. Questions regarding the similarities of these disparate systems, the format they would have as SCAs, how similar SCAs can be compared and their specification and correctness be shown are addressed.
The second chapter examines a variety of hardware architectures and dynamical systems. A one-dimensional buffer is used to show the basics of an SCA specification, and then two systolic sorters are used to introduce some further concepts. Examples of dynamical systems including neural networks, cellular automata and coupled map lattices are informally introduced.
Chapters three and four rigorously define the specification of SCAs and show how to investigate their correctness. A `correctness' function is used to check that the output of an SCA is correct at each time step. Two types of correctness are shown, the first for the `global clock' (i.e. checking outputs every n clock cycles) and the second for the `external user-level clock' (i.e. checking outputs every clock cycle on an external clock).
The following several chapters examine the mathematical techniques needed to model the dynamical systems that are introduced in later chapters, and present two programming languages based on aspects of the SCA notion.
The first language has a deliberately limited notation and so acts as an introduction to the necessary ideas. The second language is that used in the Caress software, developed at Swansea University, which allows most forms of an SCA to be expressed and tested.
Chapter eight is an important part of this book, as it introduces excitable media in the context of SCAs. This chapter is split into two, the first half dealing with single-clocked systems and the second half with multi-level clocks. The use of multi-level clocks allow some parts of a system to run at one time resolution (e.g. seconds) with other areas running at a greater level of precision (e.g. milliseconds).
This chapter begins with a detailed examination of the relationship between SCAs and excitable media. They then move on to a researcher's motivations, including why an investigator would want to use an SCA model and how they could be sure of its correctness. A formal treatment is given to converting a coupled map lattice definition to an SCA. This acts as a preface to the conversion of D. R. Chialvo's coupled map lattice of cardiac tissue to an SCA.
The SCA model of cardiac tissue is used to explain several concepts of cardiac models, first using a one-dimensional fibre and then a three-dimensional ventricle. The one-dimensional fibre is used to show the effects of repeated stimulation of the tissue and the `collision' of travelling waves of excitation. The three-dimensional model shows wave propagation through the ventricle, and the creation and problems of a heart arrhythmia.
The final chapters cover the approximation partial differential equations that operate in continuous time to operating in discrete time and other advanced topics.
Many references are used throughout the book, where outside models of dynamical systems are introduced and presented as SCAs. There is no index, although the Table of Contents is very clear. There are also many suggestions for further reading material.
Assuming that the initial chapters have been covered, so that the reader is familiar with the SCA notation, then it is quite possible to read chapters in isolation without reference to earlier work. This allows a mathematician to read about techniques of model comparison, physicists to investigate the properties of dynamical systems and biologists to express Partial Differential Equation models of natural systems as SCAs without much overlap.
This book succeeds in its aim of defining and explaining the notion of SCAs and unifying this notion with other mathematical theories. As many practical examples are given it is relatively easy to pick a model not covered in the book, and follow the steps provided to convert it to an SCA. The chapter covering excitable media make this field, of which models are often complex and poorly presented, clear to follow and a pleasure to read.
