Message passing

This article is about the computer science concept. For other uses, see Message passing (disambiguation).

Message passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages (comprising zero or more bytes, complex data structures, or even segments of code) to other processes. By waiting for messages, processes can also synchronize.

Overview

Message passing is the paradigm of communication where messages are sent from a sender to one or more recipients. Forms of messages include (remote) method invocation, signals, and data packets. When designing a message passing system several choices are made:

• Whether messages are transferred reliably
• Whether messages are guaranteed to be delivered in order
• Whether messages are passed one-to-one, one-to-many (unicasting or multicast), or many-to-one (client–server).
• Whether communication is synchronous or asynchronous.

Prominent theoretical foundations of concurrent computation, such as the Actor model and the process calculi are based on message passing. Implementations of concurrent systems that use message passing can either have message passing as an integral part of the language, or as a series of library calls from the language. Examples of the former include many distributed object systems. Examples of the latter include Microkernel operating systems pass messages between one kernel and one or more server blocks, and the Message Passing Interface used in high-performance computing.

Message passing systems

Distributed object and remote method invocation systems like ONC RPC, Corba, Java RMI, DCOM, SOAP, .NET Remoting, CTOS, QNX Neutrino RTOS, OpenBinder, D-Bus and similar are message passing systems.

Message passing systems have been called "shared nothing" systems because the message passing abstraction hides underlying state changes that may be used in the implementation of sending messages.

Message passing model based programming languages typically define messaging as the (usually asynchronous) sending (usually by copy) of a data item to a communication endpoint (Actor, process, thread, socket, etc.). Such messaging is used in Web Services by SOAP. This concept is the higher-level version of a datagram except that messages can be larger than a packet and can optionally be made reliable, durable, secure, and/or transacted.

Messages are also commonly used in the same sense as a means of interprocess communication; the other common technique being streams or pipes, in which data are sent as a sequence of elementary data items instead (the higher-level version of a virtual circuit).

Synchronous versus asynchronous message passing

Synchronous message passing systems require the sender and receiver to wait for each other to transfer the message. That is, the sender will not continue until the receiver has received the message.

Synchronous communication has two advantages. The first advantage is that reasoning about the program can be simplified in that there is a synchronisation point between sender and receiver on message transfer. The second advantage is that no buffering is required. The message can always be stored on the receiving side, because the sender will not continue until the receiver is ready.

Asynchronous message passing systems deliver a message from sender to receiver, without waiting for the receiver to be ready. The advantage of asynchronous communication is that the sender and receiver can overlap their computation because they do not wait for each other.

Synchronous communication can be built on top of asynchronous communication by ensuring that the sender always wait for an acknowledgement message from the receiver before continuing.

The buffer required in asynchronous communication can cause problems when it is full. A decision has to be made whether to block the sender or whether to discard future messages. If the sender is blocked, it may lead to an unexpected deadlock. If messages are dropped, then communication is no longer reliable.

Message passing versus calling

Message passing should be contrasted with the alternative communication method for passing information between programs – the Call. In a traditional Call, arguments are passed to the "callee" (the receiver) typically by one or more general purpose registers or in a parameter list containing the addresses of each of the arguments. This form of communication differs from message passing in at least three crucial areas:

• total memory usage
• transfer time
• locality

In message passing, each of the arguments has to have sufficient available extra memory for copying the existing argument into a portion of the new message. This applies irrespective of the size of the original arguments – so if one of the arguments is (say) an HTML string of 31,000 octets describing a web page (similar to the size of this article), it has to be copied in its entirety (and perhaps even transmitted) to the receiving program (if not a local program).

By contrast, for the call method, only an address of say 4 or 8 bytes needs to be passed for each argument and may even be passed in a general purpose register requiring zero additional storage and zero "transfer time". This of course is not possible for distributed systems since an (absolute) address – in the callers address space – is normally meaningless to the remote program (however, a relative address might in fact be usable if the callee had an exact copy of, at least some of, the callers memory in advance). Web browsers and web servers are examples of processes that communicate by message passing. A URL is an example of a way of referencing resources that does depend on exposing the internals of a process.

A subroutine call or method invocation will not exit until the invoked computation has terminated. Asynchronous message passing, by contrast, can result in a response arriving a significant time after the request message was sent.

A message handler will, in general, process messages from more than one sender. This means its state can change for reasons unrelated to the behaviour of a single sender or client process. This is in contrast to the typical behaviour of an object upon which methods are being invoked: the latter is expected to remain in the same state between method invocations. (in other words, the message handler behaves analogously to a volatile object).

Message passing and locks

Message passing can be used as a way of controlling access to resources in a concurrent or asynchronous system. One of the main alternatives is mutual exclusion or locking. Examples of resources include shared memory, a disk file or region thereof, a database table or set of rows.

In locking, a resource is essentially shared, and processes wishing to access it (or a sector of it) must first obtain a lock. Once the lock is acquired, other processes are blocked out, ensuring that corruption from simultaneous writes does not occur. After the process with the lock is finished with the resource, the lock is then released.

With the message-passing solution, it is assumed that the resource is not exposed, and all changes to it are made by an associated process, so that the resource is encapsulated. Processes wishing to access the resource send a request message to the handler. If the resource (or subsection) is available, the handler makes the requested change as an atomic event, that is conflicting requests are not acted on until the first request has been completed. If the resource is not available, the request is generally queued. The sending programme may or may not wait until the request has been completed.

Mathematical models

The prominent mathematical models of message passing are the Actor model^[1] and Pi calculus^[2].

In the terminology of some object-oriented programming languages, a message is the single means to pass control to an object. If the object "responds" to the message, it has a method for that message. In pure object-oriented programming, message passing is performed exclusively through a dynamic dispatch strategy.^{[citation needed]}

Objects can send messages to other objects from within their method bodies. Message passing enables extreme late binding in systems. Sending the same message to an object twice will usually result in the object applying the method twice. Two messages are considered to be the same message type, if the name and the arguments of the message are identical. Some languages support the forwarding or delegation of method invocations from one object to another if the former has no method to handle the message, but "knows" another object that may have one. See also Inversion of Control.

Alan Kay has argued^[3] that message passing is more important than objects in OOP, and that objects themselves are often over-emphasized. The live distributed objects programming model builds upon this observation; it uses the concept of a distributed data flow to characterize the behavior of a complex distributed system in terms of message patterns, using high-level, functional-style specifications.

Examples

• Actor model implementation
• Amorphous computing
• Flow-based programming
• SOAP (protocol)

See also

• Active message
• Database-centric architecture
• Distributed computing
• Dynamic dispatch
• Event loop
• Inter-process communication
• Message loop in Microsoft Windows
• Message-oriented middleware
• Messaging pattern

References

1. ^ Actor Model of Computation: Scalable Robust Information Systems
2. ^ Elements of interaction: Turing award lecture
3. ^ http://lists.squeakfoundation.org/pipermail/squeak-dev/1998-October/017019.html

External links

• Future of Concurrent Programming

Further reading

• Ramachandran, U.; M. Solomon, M. Vernon (1987). "Hardware support for interprocess communication". Proceedings of the 14th annual international symposium on Computer architecture. ACM Press. http://portal.acm.org/citation.cfm?id=30371&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618. 
• McQuillan, John M.; David C. Walden (1975). "Some considerations for a high performance message-based interprocess communication system". Proceedings of the 1975 ACM SIGCOMM/SIGOPS workshop on Interprocess communications. ACM Press. http://portal.acm.org/citation.cfm?id=810905&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618. 
• Shimizu, Toshiyuki; Takeshi Horie, Hiroaki Ishihata (1992). "Low-latency message communication support for the AP1000". Proceedings of the 19th annual international symposium on Computer architecture. ACM Press. http://portal.acm.org/citation.cfm?id=140385&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618.