Actors: a Model of Concurrent Computation in Distributed Systems (Parallel Processing, Semantics, Open, Programming Languages, Artificial Intelligence).
Gul Agha · Deep Blue (University of Michigan) · 1985
A foundational model of concurrency is developed in this thesis. We examine issues in the design of parallel systems and show why the actor model is suitable for exploiting large-scale parallelism. Concurrency in actors is constrained only by the availability of hardware resources and by the logical dependence inherent in the computation. Unlike dataflow and functional programming, however, actors are dynamically reconfigurable and can model shared resources with changing local state. Concurrency is spawned in actors using asynchronous message-passing, pipelining, and the dynamic creation of actors. We define an abstract actor machine and provide a minimal programming language for it. A more expressive language, which includes higher level constructs such as delayed and eager evaluation, can be defined in terms of the primitives. Examples are given to illustrate the ease with which concurrent data and control structures can be programmed. To send a communication, an actor must specify the target. Communications are buffered by the mail system and eventually delivered. Two different transition relations are needed to model the evolution of actor systems. The possibility transition models events from some view-point. It captures the nondeterminism in the order of delivery of communications. The subsequent transition captures fairness arising from the guarantee of delivery. We provide a denotational semantics for our minimal actor language in terms of the transition relations. Abstraction in actors is achieved by a model in which the only observable communications are those between actors within a system and actors outside it. Our model makes no closed-world assumption since communications may be received from the outside at any point in time. The model provides for the composition of independent modules using message-passing between actors that interface the systems composed with their external environment. This thesis deals with some central issues in distributed computing. Specifically, problems of divergence and deadlock are addressed. For example, actors permit dynamic deadlock detection and removal. The problem of divergence is contained because independent transactions can execute concurrently and potentially infinite processes are nevertheless available for interaction.