Laws for Communicating Parallel Processesis analysed in terms of questions and answers so that being able to answer the questions ensure a consolidated understanding of the subject.

What is an Actor?

See: Actor definition.

What is an Actor Model

?

An Actor Model is the modelling of a computation using a network of actors sending messages to each others.

What is an *Event*?

- An event is the receipt of a message by an actor in a given actor model.
- Given an event e, the associated message is: message(e).
- The actor that received this message is: target(e).

A number of notations are useful:

- The notation:
`a:Actor —[m:Message] → b:Actor`

is equivalent to:a message

.`m`

of type`Message`

sent by the actor`a`

of type`Actor`

has been received by the actor`b`

of type`Actor`

- If we abstract away the name of the message, we write:
`a —[:Message]→ b`

. - If we abstract away the type of the message, we write:
`a —[m]→ b`

. - If we abstract away the name and the type of the message, we write:
`a → b`

. - Similarly, we can omit
`:Actor`

. - Given
`e : Event`

, we have:`a —[message(e)]→ target(e)`

.

What does e2 has been activated by e1

means?

It means that target(e1) emitted a message message(e2) that has been received by target(e2) as a consequence of processing message(e1).

- e1,e2 : Event
- What means: there is a causal relation between e1 and e2?

It means that: if one event must happen before another, we say that the first event causally precedes the second. For instance:

- If e2 cannot happen if e1 did not happen, then e1 causally precedes e2.
- e1 may happen and e2 may not happen.

How is a computation modelled?

As a set of events causally related.

How is a serial computation modelled?

As a set of events causally related. The graph of events is linear *i.e.* for any three events a, b, and c there is a path is the graph such that: a *→ b *→ c.

In other words, the set of events is totally ordered.

How is a parallel computation modelled?

As a set of events causally related. The graph of events is not linear *i.e.* it is possible to find two events a and b such that no causal links exist between a and b.

In other words, the set of events is partially ordered.

What is a strict partial order on a set?

- A strict partial order on a set S is a predicate ≺ such that:
- There is no x ∈ S such that x ≺ x.
- If x ≺ y, then: y ≺ x is false.
- If x ≺ y and y ≺ z, then: If x ≺ z.
- There may be pairs (x,y) : (S,S) such that neither x ≺ y or y ≺ x is defined.

What is an *actor computation*?

A pair (ε, →) where ε is a set of events and → is a strict partial order on ε.

What ε is complete

means?

It means that: if an event E in ε causes a message to be sent, there exists an event E' in e in which that message was received; i.e. every event which was activated has occurred

What « e1,e2 : ε, e1 and e2 are concurrent » means?

It means that neither e1 → e2 nor e2 → e1 is defined.

What « e1,e2 : ε, e1 precedes e2 » means?

It means that e1 → e2.

How is ε built?

ε is built from a postulated single event that precedes all others: ⊥.

All other events are inductively built from ⊥.

We posit that for any two events e1 and ek, the number of events in between is finite.

We posit that the number of successors of any event is finite.

Prove that: for all actor computation, there is an equivalent serial computation.

Given an actor computation, there is a monotonic injective map from (ε,→) to into (ℕ, <).

What is the Activation Sub Order

?

- If e1 activates e2, then: e1 precedes e2.
- So, for a given actor, the activations relations form a tree.
- This tree form a sub order of the actor computation.
- It is called the
Activation Sub Order

.

What is the Arrival Sub Order

?

- All messages that are sent are eventually received by their targets.
- We postulate an arbiter in front of every actor which allows only one message to be received at a time.
- In terms of the precedes ordering on the events in a computation, this means that all events with the same target are totally ordered.
- We call the sub-relation defined by the restriction of the precedes relation to the set of events with a particular target actor the
arrival ordering

for that actor.

What is a creation event

?

- Every actor is either one of a finite number of initial actors or is created during the course of a computation.
- Every created actor is created in a unique event called that actor's
creation event

. - Several actors may be created in a single event; the only restriction is that only a finite number may be created in any single event.
- we require that an actor's creation event precede the first event in which it receives a message.

What is the precursor suborder

?

- For any event E in a computation, define precursor(E) to be:
- the immediate predecessor of E in the arrival order of the target of E, if one exists ;
- else: the creation event of the target of E, if one exists ;
- else: ⊥.

- What is a relation between the precursor sub order and the precursor relation?
- What is the shape of the precursor sub order graph?

- The precursor suborder is then the transitive closure of the precursor relation and is a suborder of "→".
- The precursor suborder is a tree with ⊥ as its root.

What is the relation between: actor computations and activation and precursor suborders.

- The precedes order is precisely the transitive closure of the union of the activation and precursor suborders.
- Thus, every actor computation is the transitive closure of the union of two finitary trees, and encodes the interplay of the two.

What is Actor Induction

?

- Actor induction is defined for all of the orders defined above, and when faced with proving some property of an actor computation, one chooses which one based on the complexity of the interactions on which the property depends.
- Properties of programs without "side-effects" can usually be proved using only "activation" induction, while properties of isolated databases can usually be proved using only "arrival" induction. Complex programs with side-effects will require full-blown "precedes" induction.

"Precedes" induction states that if P(E) is true, and if P(activator(E)) and P(precursor(E)) imply P(E), then P is true of all events in the computation.

How does the Actor Model manages Fork-Join Synchronization?

It is possible to implement a fork-join behaviour using the actor model.

- F, R, G1, G2 : Actor
- F.compute("f(x)=h(g1(x),g2(x))", R)
- F computes the value
`f(x)`

which is equal to`h(g1(x),g2(x))`

and sends the result to R.

- F computes the value
- F creates the actor H.
- F sends a message to G1 requesting to compute
`g1(x)`

and to send the result to H. - F sends a message to G2 requesting to compute
`g2(x)`

and to send the result to H. - H waits for
`g1(x)`

and`g2(x)`

. - After receiving the values, H computes the result and sends it to R.

How is information shared among actors?

- My message passing only.
- The most fundamental form of knowledge which is conveyed by a message in an actor computation is knowledge about the existence of another actor.
- An actor cannot know an actor's name unless it was either created with that knowledge or acquired it as a result of receiving a message.

What is the local time axis

of an Actor?

- The arbiter gives a strict order to received messages.
- This order — local to the actor — is the time at the actor.
- Picture a clock quadrant: each message received makes the second hand to move forward a given amount of angle.
- We call the second hand axis of rotation the
local time axis at an actor

.

What is the vector of acquaintances

of an Actor?

- Choose an event α along the local time axis of an actor.
- List in order the addresses of all actors received up to α.
- This list is called the
vector of acquaintances

of the actor at α.

What is a participant

?

- e : Event
- participant(e) is:
- target(e)
- ∨ an acquaintance of target(e)
- ∨ an actor mentioned in the message(e)
- ∨ an actor created in e

At creation, how big can be the vector of acquaintance of an Actor?

- The biggest vector of acquaintances contains:
- its parents
- acquaintances of its parents
- its siblings

Define a request

?

- A request
`r`

is kind of Message `content :≡ content(r)`

`spec(content)`

is the request itself.`dest(content)`

is the address of the actor to receive the reply.

What is a reply?

- A reply
`r`

is a kind of Message. `content(r)`

should satisfy the associated request or explain why a satisfactory answer could not have been produced.

What is a Goal Directed Activity

?

- q : Request
- r : Any reply to q
- activity(q) :≡ the set of events which follow
`q`

in the partial order but precede`r`

- Informally,
`activity(q)`

is the set of events that contribute to`r`

- The publication publication has been analyzed.