Following Tsitsiklis and Papadimitriou [1], the authors use queueing theory to investigate the stability and performance of parallel processing systems, assuming that precedence constraints among job executions are their most essential characteristic. A basic model of systems with an infinite number of processors is developed, in which the input process N also defines a set of random precedences on jobs. The basic model, in contrast to earlier work, assumes only stationaryness and ergodicity of the input. The parallel traffic intensity &ggr;, defined by the authors as a particular functional of the input N, allows them to specify the stability condition of the system. In theorem 1, the stability condition is shown to be &ggr; < 1. A disconcerting misprint occurs here; the instability condition should read &ggr; > 1. The asymptotic behavior of a number of performance measures is studied, including completion time, workload, processor number (that is, the number of active processors), and waiting time.

In stable parallel processing systems, define the degree of parallelism &pgr; as the expected number of active processors in the stationary state. Theorem 4 shows this to be equal to the (ordinary) traffic intensity &rgr;. In Section 5, the need for a good statistical estimator of the parallel traffic intensity &ggr; is pointed out. Also, since only a finite number of processors of stable systems are active in the stationary state, this provides a bridge to more realistic models with a finite number of processors. The methods of this paper, which investigate how queueing phenomena arising from precedence constraints limit the full use of all the processors, may shed light on choosing the number of processors required for good performance. Section 6 studies more complex models, including one motivated by two-phase locking. In Section 8 (the conclusion), the authors argue that the “essentially qualitative nature” of their methods allows them to be applied to a broad range of queueing and processing systems.