Events and their orderings
From the definition of an Actor, it can be seen that numerous events take place: local decisions, creating Actors, sending messages, receiving messages, and designating how to respond to the next message received. However, this article focuses on just those events that are the arrival of a message sent to an Actor. This article reports on the results published in HewittActivation ordering
The activation ordering (-≈→
) is a fundamental ordering that models one event activating another (there must be energy flow in the message passing from an event to an event which it activates).
*Because of the transmission of energy, the activation ordering is '' relativistically invariant''; that is, for all events e1
.e2
, if e1 -≈→ e2
, then the time of e1
precedes the time of e2
in the relativistic e -≈→ e
.
*''Law of Finite Predecession in the Activation Ordering'': For all events e1
the set
is finite.
Arrival orderings
The arrival ordering of an Actorx
( -x→
) models the (total) ordering of events in which a message arrives at x
. Arrival ordering is determined by ''arbitration'' in processing messages (often making use of a digital circuit called an arbiter). The arrival events of an Actor are on its x
happen on the world line of x
, the arrival ordering of an actor is ''relativistically invariant''. ''I.e.'', for all actors x
and events e1
.e2
, if e1 -x→ e2
, then the time of e1
precedes the time of e2
in the relativistic frames of reference of all observers.
*''Law of Finite Predecession in Arrival Orderings'': For all events e1
and Actors x
the set
is finite.
Combined ordering
The combined ordering (denoted by→
) is defined to be the e1
.e2
, if e1→e2
. then the time of e1
precedes the time of e2
in the relativistic frames of reference of all observers.
*''Law of Strict Causality for the Combined Ordering'': For no event does e→e
.
The combined ordering is obviously transitive by definition.
In aker and Hewitt 197? it was conjectured that the above laws might entail the following law:
:''Law of Finite Chains Between Events in the Combined Ordering'': There are no infinite chains (''i.e.'', linearly ordered sets) of events between two events in the combined ordering →.
Independence of the Law of Finite Chains Between Events in the Combined Ordering
However, linger 1981surprisingly proved that the Law of Finite Chains Between Events in the Combined Ordering is independent of the previous laws, ''i.e.'', Theorem. ''The Law of Finite Chains Between Events in the Combined Ordering does not follow from the previously stated laws.'' Proof. It is sufficient to show that there is an Actor computation that satisfies the previously stated laws but violates the Law of Finite Chains Between Events in the Combined Ordering. :Consider a computation which begins when an actor ''Initial'' is sent aStart
message causing it to take the following actions
:#Create a new actor ''Greeter1'' which is sent the message SayHelloTo
with the address of ''Greeter1''
:#Send ''Initial'' the message Again
with the address of ''Greeter1''
:Thereafter the behavior of ''Initial'' is as follows on receipt of an Again
message with address ''Greeteri'' (which we will call the event Againi
):
:#Create a new actor ''Greeteri+1'' which is sent the message SayHelloTo
with address ''Greeteri''
:#Send ''Initial'' the message Again
with the address of ''Greeteri+1''
:Obviously the computation of ''Initial'' sending itself Again
messages never terminates.
:The behavior of each Actor ''Greeteri'' is as follows:
:*When it receives a message SayHelloTo
with address ''Greeteri-1'' (which we will call the event SayHelloToi
), it sends a Hello
message to ''Greeteri-1''
:*When it receives a Hello
message (which we will call the event Helloi
), it does nothing.
:Now it is possible that Helloi -''Greeteri''→ SayHelloToi
every time and therefore Helloi→SayHelloToi
.
:Also Againi -≈→ Againi+1
every time and therefore Againi → Againi+1
.
:Furthermore all of the laws stated before the Law of Strict Causality for the Combined Ordering are satisfied.
:However, there may be an infinite number of events in the combined ordering between Again1
and SayHelloTo1
as follows:
:Again1→...→Againi→......→Helloi→SayHelloToi→...→Hello1→SayHelloTo1
However, we know from physics that infinite energy cannot be expended along a finite trajectory. Therefore, since the Actor model is based on physics, the Law of Finite Chains Between Events in the Combined Ordering was taken as an axiom of the Actor model.
Law of Discreteness
The Law of Finite Chains Between Events in the Combined Ordering is closely related to the following law: :''Law of Discreteness'': For all eventse1
and e2
, the set {e, e1→e→e2}
is finite.
In fact the previous two laws have been shown to be equivalent:
:Theorem linger 1981 ''The Law of Discreteness is equivalent to the Law of Finite Chains Between Events in the Combined Ordering'' (without using the axiom of choice.)
The law of discreteness rules out Denotational semantics
ClingerSee also
* Actor model early history * Actor model and process calculi * Actor model implementationReferences
*Carl Hewitt, '' et al.'' Actor Induction and Meta-evaluation Conference Record of ACM Symposium on Principles of Programming Languages, January 1974. *Irene Greif. Semantics of Communicating Parallel Processes MIT EECS Doctoral Dissertation. August 1975. *Edsger Dijkstra. A discipline of programming Prentice Hall. 1976. *Carl Hewitt and Henry Baker Actors and Continuous Functionals Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1–5, 1977. * Henry Baker and Carl Hewitt The Incremental Garbage Collection of Processes Proceedings of the Symposium on Artificial Intelligence Programming Languages. SIGPLAN Notices 12, August 1977. *Carl Hewitt and Henry Baker Laws for Communicating Parallel Processes IFIP-77, August 1977. *Aki Yonezawa Specification and Verification Techniques for Parallel Programs Based on Message Passing Semantics MIT EECS Doctoral Dissertation. December 1977. *Peter Bishop Very Large Address Space Modularly Extensible Computer Systems MIT EECS Doctoral Dissertation. June 1977. *Carl Hewitt. Viewing Control Structures as Patterns of Passing Messages Journal of Artificial Intelligence. June 1977. *Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978. *Carl Hewitt and Russ Atkinson. Specification and Proof Techniques for Serializers IEEE Journal on Software Engineering. January 1979. *Carl Hewitt, Beppe Attardi, and Henry Lieberman. Delegation in Message Passing Proceedings of First International Conference on Distributed Systems Huntsville, AL. October 1979. *Russ Atkinson. Automatic Verification of Serializers MIT Doctoral Dissertation. June, 1980. *Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981. *Gerry Barber. Reasoning about Change in Knowledgeable Office Systems MIT EECS Doctoral Dissertation. August 1981. *Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981. *Will Clinger. Foundations of Actor Semantics MIT Mathematics Doctoral Dissertation. June 1981. *