ERights Home history 
Back to: The Lambda Calculus On to: Flat Concurrent Prolog

Actors
Foundations for Open System


See this wonderful timeline of the research done by Hewitt's Message Passing Semantics group at MIT. If you know how to access these papers on-line, please tell me, the webmaster-at-erights.org. Thanks. I'd especially love a URL for Hewitt & Baker's "Laws for Communicating Parallel Processes", and for Peter Bishop's thesis.

Actors links as collected by Norm Hardy, Darius Bacon, and Kragen Sitaker.

Also on line are (currently in mostly random order):

On Open Systems specifically (What Hewitt et al meant by "Open Systems" is much like what's now called "p2p".)

How Actors history relates to E: email on eros-os hosted lists:


The following is found at pages 10 and 11 of Hewitt & Baker's "Actors and Continuous Functionals", written in 1977! Actors as a whole is a clean formal model of capability computation, as well as distributed event loop computation. These locality laws state many of the defining properties of capabilities, though not all. Notice the similarity to the partial definition of capabilities in the Ode. Also notice the prescient statement in the last paragraph below about using these laws as a basis for confinement, years before Norm Hardy and the Key Logic guys did exactly that! (Though the Key Logic guys were unaware of Actors and the locality laws at the time, they were working from the same intuitions.)

I have taken a few liberties with the formatting to better suit the web. Please see the URL above for a pdf of a scan of the original.

SECTION VII --- LAWS of LOCALITY

We would like to formalize the physical intuition that computation is local and there can be no "action at a distance". The laws of locality presented in this section are intended to capture these intuitions.

Initial Acquaintances Law

The initial acquaintances of an actor are a subset of the participants in its creation event and the actors created by its creation event:

If an actor z is the target of an event E
    such that E is the first event in the arrival ordering of z then,
        acquaintancesE(z) subset participants(creation(z)) U created(creation(z))

Precursor Acquaintances Law

The acquaintances of an actor can increase over its previous acquaintances only by the acquaintances of the messengers which it receives and the actors which it creates.

If an actor z is the target of an event E
    such that E has a precursor in the arrival ordering of z then,
        acquaintancesE(z) subset participants(precursor(E) U created(precursor(E)

Activator Acquaintances Law

An actor x can only be the target or messenger in an event E if x is newly created or is an immediate participant in activator(E).

For each event E which is not an initial event
    target(E) elementOf participants(activator(E)) U created(activator(E))
    messenger(E) elementOf participants(activator(E)) U created(activator(E)

 

These laws of locality can be used as the foundation on which to build theories of information flow in computer systems. Using the formalism, a theory can be developed to show how the imposition of initial constraints can be used to eliminate undesirable information paths. In this way, protection problems, such as the Confinement Problem may be solved. The actor message passing model can be used as the foundation for formalisms (such as Strong Dependency [45]) for describing information transmission in computational systems and for proving that information is not transmitted over certain paths.

 
Unless stated otherwise, all text on this page which is either unattributed or by Mark S. Miller is hereby placed in the public domain.
ERights Home history 
Back to: The Lambda Calculus On to: Flat Concurrent Prolog
Download    FAQ    API    Mail Archive    Donate

report bug (including invalid html)

Golden Key Campaign Blue Ribbon Campaign