COMPUTER DESIGN FOR ASYNCHRONOUSLY REPRODUCIBLE MULTIPROCESSING
Earl C. Van Horn · DSpace@MIT (Massachusetts Institute of Technology) · 1966
A concept is presented for designing either a computing system, or a programming language system, so that the following problem is avoided: during a multiprocess computation (several processes communicate, and the relative timing of the performance of the processes is arbitrary) the output produced by the computation might not be a function of only the initial computation state; i.e., of only inputs and initial program of the computation. The design concept for avoiding this problem is explained by defining an apparently new class of abstract machines called Machines for Coordinated Multiprocessing, or MCM's. Processes are coordinated in an MCM by means of a count matrix, which may be modified by actions of processes, and which determines the processes enabled to proceed at any instant. Remarks suggest that a computing facility which behaves like an MCM can be constructed and programmed at reasonable cost. It is proved that every MCM has the properties of output functionality and output assuredness: output functionality means that each symbol in every output stream is a function only of the initial computation state; output assuredness, that for each output stream the maximum number of symbols produced in the stream (or fact that the number of such symbols has no upper bound) is a function only of the initial computation state. (Author)