A systolic array is a collection of synchronized, communicating finite state machines. During each “cycle,” each machine receives one message over each of its input channels (from an immediately neighboring machine or from the external world) and then sends one message over each of its output channels; this means that each internal channel exhibits a one-cycle delay. The paper expresses the action of a machine during a cycle as a sequence of steps, one step for each input channel followed by one step for each output channel. This seems a gratuitously complex level of detail, since the observable behavior of a machine, its outputs, is determined exactly by its inputs; in fact, a machine begins each cycle in the same state, and therefore has no memory from cycle to cycle. The paper divides all messages into two categories: null (one special message) and data (all other messages), ignoring any differences among data messages. Whether a given output message is null or data is determined only by the null or data character of the inputs. This seems a severe restriction in practice because, in general, one would expect that some data inputs would give rise to data outputs, while others might give rise to null outputs.

The main points of the paper are two algorithms: for liveness and for termination. An array is live if at least one infinite sequence of external inputs provokes an infinite sequence of cycles in which no machine ever receives a set of inputs, corresponding to which it does not have a set of outputs. (The table relating the inputs to the outputs of a machine may not have an entry for every set of input values.) The algorithm is given a description of an array and an infinite history for every (internal as well as external) channel; it then verifies whether these are mutually consistent.

Your reviewer must confess to the feeling that this is a rather trivial algorithm. In the most reasonable practical situation one would know the histories of only the external (not the internal) channels. The real challenge would be to find an algorithm that would construct a live set of histories, given only the array. The other algorithm, for termination, which establishes whether a live set of histories repeats itself in a certain way, is similarly trivial.

This is a harsh assessment. If there is some consideration that belies the charge of triviality, the authors have unfortunately failed to make it clear. As your reviewer sees it, this is another of an all-too-common breed of paper, which sets up an elaborate mathematical model and proves some modest facts about that model, without considering: (1) whether, in practical situations, these facts are of any interest or value, and if so, (2) whether the methods of the paper are likely to be used in preference to less abstract “common sense” modes of analysis.