Accession Number:

ADA052266

Title:

Actors and Continuous Functionals,

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1977-12-01

Pagination or Media Count:

34.0

Abstract:

This paper presents precise versions of some laws that must be satisfied by computations involving communicating parallel processes. The laws take the form of stating plausible restrictions on the histories of computations that are physically realizable. The laws are very general in that they are obeyed by parallel processes executing on a time varying number of distributed physical processors. For example, some of the processors might be in orbiting satellites. The laws are justified by appeal to physical intuition and are to be regarded as falsifiable assertions about the kinds of computations that occur in nature rather than as proved theorems in mathematics. The laws are intended to be used to analyze the mechanisms by which multiple processes can communicate to work effectively together to solve difficult problems. The laws presented in this paper are intended to be applied to the design and analysis of systems consisting of large numbers of physical processors. The development of such systems is becoming economical because of rapid progress in the development of large scale integrated circuits. We generalize the usual notion of the history of a computation as a sequence of events to the notion of a partial order of events. Partial orders of events seem better suited to expressing the causality involved in parallel computations than totally ordered sequences of events obtained by considering all shuffles of the elementary steps of the various parallel processes. The utility of partial orders is demonstrated by using them to express our laws for distributed computation. These laws in turn can be used to prove the usual induction rules for proving properties of procedures.

Subject Categories:

  • Electrical and Electronic Equipment
  • Computer Programming and Software
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE