Lambda the Ultimate

According to Lamport:

"There are two kinds of communication acts: transient and persistent. In a transient communication act, the medium’s state is changed only for the duration of the act, immediately afterwards reverting to its “normal” state. A message sent on an Ethernet modifies the transmission medium’s state only while the message is in transit; the altered state of the air lasts only while the speaker is talking. In a persistent communication act, the state change remains after the sender has finished its communication. Setting a voltage level on a wire, writing on a blackboard, and raising a flag on a flagpole are all examples of persistent communication.

Transient communication is possible only if the receiver is observing the communication medium while the sender is modifying it. This implies an a priori synchronization—the receiver must be waiting for the communication to take place. Communication between truly asynchronous processes must be persistent, the sender changing the state of the medium and the receiver able to sense that change at a later time."

There is no global state space of communications media, e.g., fiber optics cables, etc. Sending a message does not require a state change in an alleged global state space.

The paper doesn't mention global state spaces. Actually, it doesn't even mention local state spaces. It does talk about state changes. Again from Lamport:

"All communication ultimately involves a communication medium whose state is changed by the sender and observed by the receiver. A sending processor changes the voltage on a wire and a receiving processor observes the voltage change; a speaker changes the vibrational state of the air and a listener senses this change."

An alleged global state is part of a global state space allowing transitions between states.

Global state spaces have problems with real concurrent systems:
* Some computational components (e.g. arbiters and laser fiber communication links) are not properly modeled
* Global state spaces mean bounded nondeterminism with the consequence that simple properties of concurrent systems cannot be proved. This deficiency motivated a fundamental change from CSP-78 (bounded nondeterminism) to CSP-85 (allowing unbounded nondeterminism as in the Actor Model).
* In practice, global state spaces are inadequate for modeling concurrent systems.

So the Actor model passes messages without any change of state in anything, anywhere?

Just by itself, sending a message does not require any Actor to change.
It is possible for an Actor to change as a result of receiving a message.

Before a message is sent, there are no messages "in flight". After a message is sent, there is a message "in flight". That sounds like a change of state in the actor system to me. An actor system in which a message was never sent is presumably different from an actor system in which a message was sent (even if the message has not yet been received).

In a general denotational model of Actor message passing, a countable number of different future arrival times can be chosen for the arrival of a message. Of course, in special cases, there can be greater information about possible arrival times.

The denotational model for Actors is different from the global state space model in that it does not have the problem of requiring bounded nondeterminism.

There are some pretty fine hairs to split here.

Lamport posits a global state space when he talks about persistent communication acts for which is paradigm is a single-writer, multiple-reader register. In his lowest level model, reads from such a register are undefined during a concurrent write. Between writes, reads return the most recently written value. The register itself is the global state shared by the writer and the readers.

In Lamport's "persistent" communication, readers "poll". Communication is received by a periodically reading the shared register and noting changes to the value read.

In Lamport's abstraction, there are two kinds of entity: processes on either side of a shared register, and a shared register which is a kind of quirky buffer. The shared buffer, distinct from the processes on either end, is global, mutable state.

In the actor model, there are no processes-with-registers-in-between there are just actors exchanging messages.

At the risk of creating confusion: The actor model of a piece of hardware like Lamport's shared register is an actor. The register would be an actor. The actor would respond to write messages that change the contents of the register and read messages that access the contents of the register.

The simplest (higher level) actor model of a shared register would be stronger than Lamport's weakest shared register model:

A simplistic actor shared register would be typed to accept WRITE and READ messages. To a WRITE it would reply DONE. to a READ it would reply with a value. Reads and writes would be strictly atomic, never over lapping.

A fancier actor, modeling lower level hardware, would have to allow concurrent reads and writes, providing only weak guarantees about what a read returns.

In the fancier model a shared register would reply to a WRITE with an ACCEPTED reply, meaning the write occurred but readers might not yet see it yet. Upon sending an ACCEPTED reply, the register actor would send itself a COMMIT message. That COMMIT message might take a while to arrive. A READ message would return the value at the time of the most recent COMMIT unless there has been a subsequent WRITE. In the latter case, a WRITE subsequent to the most recent COMMIT, the value returned by READ could be unspecified.

Lamport's weakest semantics for a shared register -- a register than if read during a write can be unsettled -- finds a natural mathematical model in the semantics of actor message passing. The period of time between the WRITE message and the self-sent COMMIT message is the time when a READ can return the unsettled contents of the register. Eventual message delivery means the COMMIT eventually completes.

So if Actors don't involve (but can model) a shared global state between processes like a shared register, does that mean actors use transient communication (in Lamport's sense of transient)? Must actor communication be of the sort:

"Transient communication is possible only if the receiver is observing the communication medium while the sender is modifying it. This implies an a priori synchronization—the receiver must be waiting for the communication to take place. "

Well, yes, but with one caveat. As Hewitt led off:

"Actor Model message passing involves no periodic testing by a receiver."

Which is to say, actor messages don't follow anything like a shared register semantic, as I unpacked a bit, above.

Therefore messages must be of the transient sort but here... I would say ... Lamport was a little too casual in his formulation. Lamport goes a little amiss where he says:

"only if the receiver is observing the communication medium while the sender is modifying it"

The problematic word here is "while".

The word is a problem because it is physically unrealistic, at least if we take "while" to mean that the write and read are simultaneous with space-like separation. This is physically unrealistic because it means a transient write does not causally precede the corresponding read! That would require some pretty fancy hardware.

Where Lamport loosely says:

Transient communication is possible only if the receiver is observing the communication medium while the sender is modifying it. This implies an a priori synchronization—the receiver must be waiting for the communication to take place

we might, from an actor point of view, correct:

Transient communication is possible only if the receiver is listening for messages on some world-line on which the sender has a bearing (aka an "actor address"). Transient communication commences when the sender transmits a message towards another actor (transmitting to the receivers' address). Transient communication completes later, when the signal transmitted is received at the reader's world-line.

The "a priori synchronization" Lamport mentions is not the general case. The general case is just that the sender has a priori knowledge of the receiver's "address".

The shared buffer, distinct from the processes on either end, is global, mutable state.

It's not clear to me why you call this "global" state. It can be local to the two interacting processes, and completely invisible to all other processes in the system.

In the actor model, there are no processes-with-registers-in-between there are just actors exchanging messages.

Which is an abstraction over actual implementation details. As Carl made clear on a different thread when he discussed how actor messaging might be implemented on an x86 or ARM core. Granted, you can model the implementation in terms of actors. But you're still talking about an implementation. A hardware implementation of an actor that behaves like a register is presumably going to look a whole lot like a register. Lamport appears interested in the implementation rather than the abstraction. And in how (if you want to look at at this way) primitive actors with minimal guarantees can be used to construct stronger guarantees.

It's not clear to me why you call this "global" state.

Global is relative to the narrower scopes under discussion. E.g., a global variable in a pascal program is global relative to the local variables in procedures of the same program. Of course, it is not "absolutely global" in that it is not shared by other pascal programs.

Lamport appears interested in the implementation rather than the abstraction.

I guess I have failed to convey:

The fancy actor model of a shared register illustrates that at heart, the actor message passing semantic is lower level than Lamport's. We can use the logic of actors to design the hardware for Lamport's shared register. Lamport's algorithms assume the shared register already exists.

We can use the logic of actors to design the hardware for Lamport's shared register.

Probably individual logic gates is about the lowest level you'd want to consider modelling as actors. The continuous phenomena that provide message passing in such systems would appear in the types of these actors. (The point is not that you'd get new results you couldn't get without actors. Only that the actor model applies pretty directly from levels that low to very high levels of abstraction.)

I suppose so.

Although a logic gate does not, by itself, know the "addresses" of the gates to which its output is connected. It just puts a signal on its output line. So you either need to make the signal wires into Actors as well (even though we tend to think of wires as channels rather than Actors), or you need to come up with some scheme for representing the circuit topology in terms of a set of output addresses within each gate Actor (information that a real gate does not hold or care about).

Additionally, it's not really obvious how a gate Actor could manage something like fanout unless it sent multiple messages--one to each gate it fans out to--even though the actual gate simply makes a single transition on its output line. I guess that's where a wire Actor might come in handy, since it could handle the message multiplication (presumably representing differing signal transition wavefronts on different parts of the fanout net) for the outputting gate.

Also, your gate Actor would probably have to retain internal state representing the current signal level on its inputs (or send a query to its input wire Actors any time it received a signal-level transition message, or use Lamport's scheme for converting transient communications into persistent communications using a sub-Actor and a buffer) in order to generate an input when a signal transition message was received, whereas a real gate is stateless and simply responds to the levels at its inputs continuously. Probably not a big deal, but it does mean your model holds state where the real implementation does not, which might lead to some interesting edge cases that don't quite line up with reality.

Anyway, I guess my point is that the mapping you're describing is not as simple, direct, or intuitive as you seem to think. Which is not to say that I think an Actor system couldn't simulate the behavior of a digital logic system. But you can't just say "gate = actor" and call it done.

Edit: come to think of it, the output of a gate could also be viewed as a binary-valued version of Lamport's shared registers

I think your use of global is incorrect. What is described is just a local variable in a wider scope that contains the other two objects in question. Global is defined in terms of accessibility. It means the variable can be read or mutated from any function in the program. There is a further implication with global state, that a single global lock must be held to mutate it. The case of a message queue shared between two objects is neither of these, and is clearly local.

The Actor Model is directly implementable without any loss of efficiency in processing, storage, or communications.

Also, the Actor Model directly models digital concurrent systems without requiring any extraneous elements, e.g., channels, registers, etc.

Theoreticians have used global states because of the lack of machinery to deal properly with interacting asynchronous local states.

Are there any examples you can point us to of directly implemented Actors? It'd be interesting to see how it actually works, and may clear up some of my confusion around how the Actor model translates to an implementation.

ActorScript is for the direct implementation of Actor Model. There are lots of examples in the article linked in the previous sentence.

However, ActorScript is a work in progress.

Comments and suggestions for improvement are greatly appreciated.

Thanks. I've looked at it before. But while a metacircular interpreter is neat, I was rather hoping for a hardware implementation, physical manifestation, or software implementation that would show how the message passing mechanism actually works.

There is a simple hardware example on page 49.

That appears to be an Actor that specifies the behavior of a piece of hardware (an ALU). I was looking for a hardware implementation of the Actor model rather than an Actor model of a hardware implementation.

Conceptually, particles are actors exchanging messages via force carriers. Of course, given QM this model requires global simultaneity of messaging in configuration space, since Bell's inequalities demonstrated the need for non-locality given hidden variables.

Sure, there are things in the world (including particles) that exchange messages. Is it truly a direct implementation of all of the semantics of the Actor model though? My impression was that there's more to Actors than just the fact that messages get sent and received (guarantees of eventual message arrival for starters). Not to mention the fact that force carriers travel through space, whereas Actor messages are, if I understand what Carl's been saying, passed directly from one Actor to another without going through any sort of communications channel or medium. In fact, I'm a little fuzzy on whether the force carrier itself counts as a "medium". Or possibly even an Actor.

I hadn't come across Bell's inequality before. That's an interesting twist. QM just gets weirder every time I learn something new about it.

The word is a problem because it is physically unrealistic, at least if we take "while" to mean that the write and read are simultaneous with space-like separation. This is physically unrealistic because it means a transient write does not causally precede the corresponding read! That would require some pretty fancy hardware.

This argument seems reasonable if both the read and the write are operations that occur at a single point in time. However it is not so clear that it still holds if the read and write are operations that occur over an interval of time. As interval comparisons yield more individual cases than points the word "while" has some additional interpretations.

I've programmed this particular kind of system a couple of times before (once bit-banging a shared bus and once building a distributed system on top of a wifi network). In both cases the sensors could not both read and write at the same time so a mode switch was required. Both the sender and receiver had to overlap in time longer than some minimum threshold for the transient communication to take place (the transient medium being something like a pulse encoding on the persistent medium beneath).

There tends to be a relationship between the the length of the overlapping interval and the error rate in the transmission that causes a strong relationship between the system choosing to enter a reading / writing state and the achievable latency / bandwidth on the line. Rather than being physically impossible, this type of communication is realisable under certain constraints.

Causality may be a total ordering from some perspectives, but a partial ordering can also work if the model is more refined than simple points. I should emphasise that I am only speaking of causality in this one setting, not in general.