Actors and Asynchronous Distributed Systems

Pradeep Loganathan

Information Systems Engineering (ISE II)

Department of Computing

Imperial College of Science, Technology and Medicine

"The concept of a unique global clock is not meaningful in the context of a distributed system of self-contained parallel agents."

Hewitt and Baker 1977a

1. Introduction

A distributed system may be defined as a collection of processes and a strongly connected network capable of implementing communication channels between pairs of processes for message exchange. In an asynchronous communications architecture the sender does not block waiting for a reply but continues processing as soon as the message is sent. Actors are based on asynchronous message passing, hence may only be "accessed" this way.

2. Global Synchrony and Asynchrony

For a distributed system, a linear global clock may not be definable. The lack of a global clock does not imply that it is impossible to create a distributed system whose performance is such that the components of the system can be abstractly interpreted to be acting synchronously. The problem of constructing a synchronous system is essentially one of defining protocols to cope with the communications limitations in a distributed system. The important point to be made is that any such global synchronisation produces a bottleneck which can be inefficient in the context of a distributed environment.

3. Interaction Between Processes

Distributed processes may have local clocks that proceed at different rates. This may be due to the clock speeds of the different processors, or the way that different logical processors are scheduled on the physical processors. Also, there may be varying time delays in communication between different processors, hence leading to unpredictable ordering of events. If two processes A and B receive communication from two others C and D indicating the completion of a task. If communication from C to A proceeds faster than from C to B, and from process D to B is quicker than from D to A, the process A may "think" that C completes before D whereas B "thinks" that D completes before C! This problem could be solved by ‘tagging’ messages with a sequence number, so that the receiver could rearrange the messages into the correct order.

Methods of interaction between computational elements can be broken down into two different classes:

Variables shared between different processes.
Communication using special primitives.

3.1 Shared Variables

Various processes are allowed to read and write to a shared set of variables common to more than one process. Obviously, this technique does not provide any mechanism for abstraction and information hiding. Because this model fixes the level of atomicity of the actions, the programmer has the burden of specifying the appropriate details to accomplish meaningful interaction. The actor model does not use this technique for interaction.

3.2 Communication

Communication for sharing information allows a greater degree of independence between the processes. Communication can be considered to be either synchronous or asynchronous, asynchronous communication (please refer Figure 1) will be discussed in the next section. In the synchronous model, the sender is blocked until the destination process actually receives the message. The destination process is suspended until the source has executed the send, the sender and receiver are thus synchronised. This tight coupling means that a delay at the receiver would hence delay the sender. Mechanisms have been introduced to handle such problematic situations by withdrawing the send operation.

4. Asynchronous Message Passing

Advantages of Asynchronous Communication:

Since communication takes time, communication intended for a process may arrive at the same time or scattered with communication from another source. Hence the system has to be able to sort out parts of a communication, which is easier to do with asynchronous communication.
The sending process may run quicker than the receiving process, these situations could be handled easier with asynchronous communication.
Synchronous communication could be defined in the framework of asynchronous communication by using "acknowledge" messages.
Synchronous communication does not allow a process to send itself a message. A recursive computation may require this facility.
Asynchronous communication is important for real-time applications where the component may be performing a time-critical activity and hence cannot waste time waiting for confirmation of successful transmission.

4.1 Buffered Communication

Communications may get lost with a system built on the asynchronous model without buffers. Buffered asynchronous communication affords us efficiency in execution by not arbitrarily delaying a computation which does not need to wait for another process to receive a given communication.

4.2 Fairness

Eventual delivery of a message is a convenient programming assumption. However, it is not entirely feasible for an implementation to satisfy this assumption. If a system did not eventually deliver a communication it was buffering, it would have to buffer the communication indefinitely, hence consuming storage. The guarantee of delivery does not assume that all processes are meaningfully processed.

5. General Properties of Actors (summary)

The actor model is asynchronous, with no global clock.
Communication is:

explicit, through mail addresses, without shared variables,
buffered and asynchronous.

Every message that is sent is eventually delivered, although at the time of delivery an actor may not be prepared to process the message at a given time.
All computations eventually progresses, i.e. each process is eventually scheduled and allowed to perform part of its computation.

6. Conclusion

Asynchronous distributed systems may be realistic models for actual systems. Physical components from which we construct distributed systems are often synchronous. However, as we bring layers of software to multiplex these physical resources to create abstractions such as processes and reliable communication channels, the resulting system may be better classified as asynchronous.

References

G. Agha. Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press, Cambridge, Mass., 1986

M. Sloman, J. Kramer: Distributed Systems and Computer Networks. Department of Computing, Imperial College, 1987