Message passing is a method of organizing computation in which separate entities interact by sending and receiving messages. The entities may be processes, threads, objects, computers, or nodes in a mathematical model. A message carries information that a recipient interprets according to an agreed protocol. Unlike interaction through shared memory, message passing makes communication an explicit operation, although an implementation may still use shared memory internally.
The concept is fundamental to concurrent computing, distributed computing, and parallel computing. It supports applications ranging from communication between programs on one computer to coordination across large computing clusters. Related uses occur in probabilistic inference and graph-based machine learning, where “messages” are mathematical quantities exchanged along edges rather than necessarily network transmissions.
Message passing is not a single protocol or a guarantee of reliable delivery. Different systems define different rules for addressing, buffering, ordering, synchronization, and failure. These rules determine whether a send operation waits, whether messages survive a crash, and what a receiver can infer from receiving—or not receiving—a message.
Foundations and historical development
The central abstraction of message passing is a set of computational participants with local state and explicitly defined communication operations. A participant performs internal computation, sends information, or receives information that can change its subsequent behavior. Communication may occur between processes with separate address spaces, between threads in one address space, or between machines connected by a network. The abstraction does not require any particular physical transport: the same conceptual exchange can be implemented using memory buffers, operating-system facilities, or network packets.
Message passing became particularly important as computing moved beyond sequential execution on a single processor. Operating systems needed mechanisms through which isolated programs could cooperate, while networked systems needed communication that did not depend on a common memory address space. It consequently became a major form of interprocess communication. In distributed systems, it also exposed a fundamental distinction: a local memory access and an exchange with a remote participant have different latency, failure, and coordination properties, even when a programming interface makes them look similar.
Several influential research traditions developed explicit theories of communication. In 1973, Carl Hewitt, Peter Bishop, and Richard Steiger presented the actor model, in which actors react to messages, create actors, send messages, and determine their subsequent behavior. In 1978, C. A. R. Hoare published “Communicating Sequential Processes,” introducing a language-oriented account of concurrent processes communicating through input and output operations. His 1985 book developed Communicating Sequential Processes into a broader mathematical framework for describing and reasoning about interactions. These traditions differ in their treatment of synchronization and identity, but both make communication part of the computational model rather than an incidental implementation detail.
Practical systems developed related ideas in different settings. Smalltalk made sending messages to objects central to its programming model. Erlang, whose development began at Ericsson in 1986, combined lightweight processes, asynchronous messages, and fault-isolation mechanisms for telecommunications software. High-performance computing developed message-passing libraries for machines with distributed memory; the first Message Passing Interface standard appeared in 1994. These developments did not establish one universal meaning of “message.” Instead, they produced a family of abstractions suited to object interaction, service coordination, concurrency, and numerical computation.
The term therefore identifies a common organizing principle rather than a uniform execution model. A Smalltalk message may result in a method executing within one process, an actor message may enter a mailbox, and an MPI message may transfer an array between processors. Their shared feature is an explicit interaction addressed to a recipient or communication endpoint. Their differences become decisive when reasoning about concurrency, performance, and failures.
Communication operations and synchronization semantics
A basic message-passing interface provides operations resembling , which sends message to destination , and , which accepts a message from source or from an eligible set of sources. Actual interfaces often include channel identifiers, tags, type descriptions, priorities, or correlation identifiers. These fields help match an incoming message with the operation or conversation to which it belongs. A request identifier, for example, allows a client to distinguish responses when several requests are outstanding simultaneously.
The most important semantic distinction concerns when operations complete. In synchronous communication, a transfer can require sender and receiver to participate in a rendezvous. The sender cannot finish the interaction merely by depositing data somewhere for later consumption. In asynchronous communication, sending and receiving are decoupled, commonly through a buffer or mailbox. This distinction is separate from whether an interface is blocking. A blocking operation suspends its caller until a specified condition holds; a nonblocking operation initiates work and returns a handle, callback arrangement, or other means of observing later completion. Asynchronous programming describes how programs manage such pending operations, not a universal delivery guarantee.
Completion itself has several possible meanings. A send may complete when the system has copied the data, when the sender may safely reuse its buffer, when a remote machine has accepted the message, or when the receiving application has processed it. These milestones are not interchangeable. In MPI, for example, completion of a standard-mode send establishes that its send buffer can be reused; it does not generally establish that the matching receive has completed. Similarly, a broker acknowledgment may confirm storage by the broker without confirming execution of the consumer’s business operation.
Buffer capacity links communication semantics to resource management. An unbounded mailbox is a useful theoretical abstraction, but a real implementation has finite memory or storage. When producers outpace consumers, the system must block producers, reject work, discard selected messages, spill data to storage, or grow a backlog. Backpressure is the propagation of capacity constraints toward upstream producers. A bounded channel can provide backpressure by making a send wait until space becomes available, while a streaming protocol may explicitly communicate demand.
A simple producer–consumer example illustrates the consequences. With a zero-capacity channel, each item requires a rendezvous. With a bounded queue of 100 items, the producer can run ahead by at most that amount before being constrained. With an effectively unbounded queue, temporary bursts are absorbed, but sustained overload increases memory use and waiting time. None of these designs is intrinsically equivalent to the others: buffering changes scheduling possibilities, failure exposure, and the points at which participants synchronize.
Actors, channels, objects, and messaging architectures
Different programming models attach messages to different kinds of identity. In actor systems, a message is directed to an actor address, and each actor encapsulates its own state and behavior. Implementations commonly provide a mailbox and arrange that an actor processes messages without concurrent access to its private state. This reduces the need for explicit locks within that actor, but does not automatically make a multi-actor workflow atomic. Two actors can still make incompatible decisions based on messages received at different times, and a slow actor can accumulate a large mailbox.
Channel-based models instead emphasize a communication connection rather than a recipient object. A channel may connect one sender and one receiver, many senders and one receiver, or a larger set of participants. Languages differ on whether channels are typed, buffered, transferable, or associated with ownership restrictions. In Go, for example, channels support communication between goroutines, and a select statement can choose among communication operations that are ready. Channel topology can express a pipeline in which one stage parses records, another transforms them, and a third writes results.
Object-oriented message sending has a related but distinct meaning. In Smalltalk, sending a message asks an object to respond to a selector, potentially with arguments. Method lookup determines the behavior that executes. This is an important form of object-oriented programming, but it need not involve concurrency, buffering, or communication between machines. Treating every object message as a network-style asynchronous event would therefore confuse a language-level dispatch mechanism with a distributed execution model.
Service architectures add intermediaries and routing rules. A message queue stores messages until consumers retrieve or receive them. In a work queue, several consumers may compete to process different items, distributing independent tasks among workers. In publish–subscribe communication, publishers send information to topics or subjects, and subscribers receive information according to subscriptions. A single publication can therefore reach several consumers. Delivery details vary: some systems retain records for replay, some keep separate consumer positions, and some provide only transient notification.
A remote procedure call presents communication as an invocation with arguments and a result. This request–response pattern can be implemented through direct connections or messaging infrastructure. It differs from one-way event publication because the caller normally expects a corresponding response and often waits for it. Nevertheless, an RPC timeout does not establish that the remote operation failed to execute. The boundary between a function-like interface and a message-based implementation is consequently a source of important semantic differences.
These models can coexist. A service may use RPC for queries, publish events after state changes, distribute background tasks through queues, and use actors internally. The relevant architectural choice concerns identity, state ownership, interaction patterns, and failure behavior—not simply whether bytes travel over a network.
Representation, transport, and communication cost
A message needs a representation that both sender and receiver can interpret. Within one runtime, that representation may be an immutable object reference or a transferred buffer. Across process or machine boundaries, it commonly requires serialization: encoding structured values into a sequence of bytes. Formats may be textual, such as JSON and XML, or binary, using a schema or runtime-specific encoding. Choices about integer width, character encoding, field identifiers, and optional values become part of the communication contract.
Message boundaries must also be established. Transmission Control Protocol provides an ordered byte stream, not an application message service. If an application writes two messages, a receiver cannot assume that two reads will reproduce those boundaries. Protocols therefore use framing, such as a length prefix, a delimiter with escaping rules, or a fixed-size header that states the payload size. Datagram transports preserve datagram boundaries but introduce their own size and delivery constraints. Application messages may also be fragmented or combined by lower layers without changing their logical meaning.
Communication time is often approximated by the latency–bandwidth model
where is message size, is fixed startup latency, and is time per unit of data. This model explains why combining many small messages can improve throughput: batching pays the startup cost fewer times. It also explains a trade-off, since waiting to assemble a batch increases the delay experienced by individual items. Real systems add serialization costs, copying, queueing, contention, and protocol-specific thresholds, so the equation is a model rather than a complete performance prediction.
Implementations reduce overhead through shared-memory queues, buffer reuse, zero-copy techniques, and remote direct memory access. “Zero-copy” generally means avoiding particular copies in a data path, not that a message incurs no processing or movement. Passing a reference is safe only when ownership and lifetime rules prevent the sender from invalidating or unexpectedly modifying the recipient’s data. On distributed-memory machines, direct-memory-access hardware can reduce processor involvement, but synchronization and visibility still require well-defined rules.
Protection is another part of the implementation boundary. A message from outside a trust domain is input that must be authenticated, authorized, and decoded under resource limits. Transport Layer Security can protect a connection’s confidentiality and integrity, but it does not determine whether a particular participant may issue a particular command. Schema validation also does not establish that the requested action is legitimate. Large payloads, malformed lengths, deeply nested structures, and unrestricted object deserialization can create security or availability problems.
Long-lived systems must additionally manage schema evolution. Adding an optional field is often easier than changing an existing field’s meaning, but compatibility depends on the encoding and decoder behavior. Messages stored for replay may outlive the software version that produced them, making format versioning a persistent data-management concern rather than merely an interface detail.
Ordering, delivery guarantees, and partial failure
Message ordering is defined relative to a scope. A channel may preserve messages from one sender while leaving messages from different senders unordered. A broker may order records within one partition but not across partitions. A recipient that sees message before message cannot generally conclude that every other recipient saw the same order. Total-order delivery requires stronger coordination than independent per-sender ordering, and that coordination has latency and availability costs.
Causal order captures dependencies rather than physical simultaneity. If an event sends information that contributes to a later event, the former causally precedes the latter. Leslie Lamport’s 1978 account of the “happened-before” relation formalized this reasoning for distributed systems. Logical clocks represent aspects of event ordering without requiring perfectly synchronized wall clocks. Lamport timestamps respect causal precedence, but timestamp order alone does not prove that one event caused another; additional mechanisms, such as vector clocks, can represent more detailed causal relationships.
Failures make delivery guarantees more subtle than successful transmission. Under at-most-once delivery, a message is delivered zero or one times, so loss is possible but duplication is excluded within the guarantee’s scope. At-least-once delivery allows retries to improve eventual delivery under stated conditions, but duplicates can occur. A sender may retransmit because an acknowledgment was lost even though the recipient already processed the original message. Permanent failures, expired retention periods, and exhausted retry policies can prevent eventual completion despite an at-least-once design.
“Exactly once” requires a precise account of what is counted and within which boundary. A messaging platform may atomically record consumed input and produced output within its own transactional facilities. That does not automatically make an unrelated payment, email, or external database update occur exactly once. If a consumer updates an external system and crashes before acknowledging a message, redelivery can repeat the effect. Avoiding that outcome requires coordination, deduplication, or an operation whose repetition is harmless.
Idempotence is especially useful in this setting. An operation is idempotent when . Setting an account’s notification preference to a specified value is naturally idempotent; incrementing a balance is not. A non-idempotent request can sometimes be made retry-safe by associating it with a unique operation identifier and atomically recording both the identifier and the effect. The record must remain available for the period during which duplicates are possible.
Timeouts do not resolve all uncertainty. A missing reply can mean a lost request, a slow receiver, a completed operation with a lost reply, or a failed connection. Consequently, timeout handling is a protocol decision, not a direct observation of remote state. Retry limits, exponential backoff, expiration times, and dead-letter queues manage particular consequences of this uncertainty without eliminating it.
Message passing in parallel numerical computing
In distributed-memory numerical computing, each process owns part of a problem’s data and exchanges information needed by other processes. A simulation might divide a three-dimensional grid into subdomains, assign each subdomain to one process, and exchange values along neighboring boundaries. These boundary transfers are often called halo exchanges. Each process computes most interior values locally, while messages supply the neighboring values required to update cells near the edges of its subdomain.
MPI standardizes a broad interface for this style of computation. Processes are identified by ranks within communicators, which establish communication contexts and groups. Point-to-point operations match sends and receives using information that includes the communicator, source, and tag. Communicators help separate independent communication activities, so a library’s messages need not accidentally match an application’s receives. MPI defines bindings and semantics rather than prescribing one network technology or one internal implementation.
Collective operations express communication involving a communicator’s participating processes. A broadcast distributes one process’s data; scatter and gather distribute or collect portions; reduction combines values using an operation such as addition or maximum. An all-reduce makes the reduced result available to every participant. These operations are important in linear algebra, scientific simulation, and distributed model training. Implementations can use tree structures, rings, or other algorithms selected according to message size, process count, and machine topology.
Collectives are not interchangeable with barriers. A barrier explicitly coordinates arrival of participating processes, whereas a blocking collective generally provides the completion conditions required by that collective, not an automatic guarantee that every participant has returned from it. Programs must also respect collective ordering rules. If processes invoke incompatible collective sequences on the same communicator, execution can become erroneous or hang. Correctness therefore depends on a global communication structure even though each process executes local code.
Nonblocking communication can overlap data movement with useful computation. A grid solver may initiate halo exchanges, update interior cells that do not depend on incoming data, wait for completion, and then update boundary cells. Overlap is not guaranteed merely because a nonblocking interface is used: progress can depend on the implementation, hardware, and whether the process re-enters the communication library. Programs must also preserve send buffers and avoid using receive data before the relevant operations complete.
Scaling is constrained by communication geometry and workload size. For a cubic subdomain with side length , interior work commonly grows as , while face communication grows as . Subdividing a fixed problem among more processes reduces , increasing the communication-to-computation ratio. Modern systems therefore often combine MPI between nodes with OpenMP or other shared-memory mechanisms within nodes. Such hybrid arrangements reflect the fact that memory hierarchy, network topology, and communication granularity jointly determine performance.
Protocol design, coordination, and verification
A message-passing program is often best understood as a collection of interacting state machines. A participant’s legal actions depend on its current state and the messages it has already processed. An order service, for example, might distinguish created, payment-pending, confirmed, and cancelled states. A late payment acknowledgment must be interpreted against that state: it cannot simply be treated as an unconditional command to confirm an order. Explicit state transitions make such protocol requirements visible.
Safety and liveness describe different correctness obligations. Safety means that an undesirable event never occurs, such as two workers both being granted exclusive ownership of the same resource. Liveness means that a desired event eventually occurs, such as a submitted request eventually completing. A protocol can preserve safety by refusing all work, yet fail liveness entirely. Liveness arguments normally require assumptions about scheduling, message delivery, and which participants can fail; those assumptions must not be silently substituted for guarantees supplied by the transport.
Deadlock can arise when participants wait in a cycle. If two processes both perform a blocking send that requires a matching receive, neither may reach its receive operation. Buffering can hide this defect for small messages and expose it when larger messages trigger a different communication path. Other failures include starvation, where a participant repeatedly loses access to progress, and livelock, where participants remain active but continually undo or defer useful work. Avoiding shared variables does not eliminate these coordination problems.
Formal verification studies such properties using explicit models. Process algebras describe communication and composition mathematically; model checking explores reachable states under alternative interleavings and failures. Type systems can also constrain protocols. Session types, for example, describe sequences of communication actions and compatible roles, potentially detecting a participant that sends an integer when its peer expects a termination signal. The guarantees depend on the language and model: a locally well-typed exchange does not by itself establish resilience to arbitrary machine failures.
Distributed agreement is a particularly demanding form of coordination. Distributed consensus protocols arrange for participants to agree on a value or an ordered sequence despite specified failures. Algorithms such as the Raft consensus algorithm use message exchanges, persistent state, and quorums to maintain agreement under their assumptions. The 1985 Fischer–Lynch–Paterson result showed that a deterministic consensus protocol in a fully asynchronous model cannot guarantee termination in every admissible execution with even one possible crash failure. Practical protocols obtain progress through additional timing assumptions, failure-detection behavior, or other mechanisms.
Operational verification complements mathematical reasoning. Request identifiers, causal tracing, queue-depth measurements, and recorded protocol transitions reveal what happened across service boundaries. Testing can inject delayed, duplicated, reordered, and lost messages to exercise failure paths. Such tests explore particular executions; they do not replace proofs of all possible behaviors, but they are valuable because implementation details and operational assumptions are often richer than the formal model.
Message passing in probabilistic inference
In probabilistic inference, message passing is a family of algorithms that compute quantities by exchanging local summaries over a graph. The participants are mathematical nodes rather than necessarily independent operating-system processes. A message may be an array of probabilities, a probability density, or a compact set of parameters. The shared principle is locality: each update uses information from adjacent nodes rather than directly processing the entire model at once.
Belief propagation is a central example. A factor graph represents a distribution using variable nodes and factor nodes. If variables are collected in , a factorization can be written
where is a nonnegative factor over a subset , and is a normalizing constant. The graph records which variables participate in which factors. This structure makes it possible to express global inference as a sequence of local computations.
For discrete variables, the sum-product algorithm uses variable-to-factor messages
and factor-to-variable messages
Here and denote neighboring factors and variables, respectively. Excluding the destination’s contribution prevents a message from immediately returning the same information to its source. After suitable messages have been computed, the marginal belief at variable is proportional to the product of its incoming factor messages.
On a tree-structured factor graph, a schedule passing information inward and outward computes exact marginals when the operations are well-defined. The absence of cycles means that each message summarizes a distinct portion of the graph. On graphs containing cycles, repeated updates produce loopy belief propagation. It can work well, but convergence is not guaranteed, and convergence does not in general imply exact marginals. Update scheduling, damping, factor strengths, and graph structure can materially affect behavior.
Changing the local algebra produces related algorithms. Replacing summation with maximization leads to max-product methods for maximum-probability configurations, while logarithmic representations transform products into sums and can improve numerical stability. Computational cost depends strongly on factor size: summing over a factor containing many discrete variables can require exponentially many combinations. Graph locality alone therefore does not guarantee inexpensive inference.
Applications include decoding error-correcting codes, hidden-state sequence models, and graphical models in perception. Judea Pearl’s work in the 1980s helped establish local probabilistic propagation, while the factor-graph formulation later unified many algorithms under the sum-product framework. Although these algorithms may be distributed across hardware, their defining messages are statistical summaries, not delivery envelopes or acknowledgments.
Learned message passing on graphs
A graph neural network uses local exchanges to construct learned representations of nodes, edges, or whole graphs. In a message-passing layer, a node receives functions of its neighbors’ current representations and combines them to update its own representation. This gives the model a structural bias: graph connectivity determines which information can interact directly. Unlike belief propagation, the messages are usually learned vectors, and their coordinates need not have an explicit probabilistic interpretation.
A common formulation is
where is node ’s representation at layer , contains edge information, constructs messages, and updates the node. The aggregation operation is commonly a sum, mean, or maximum. Permutation-invariant aggregation prevents an arbitrary ordering of a node’s neighbors from changing the result. For graph-level tasks, a separate readout combines node representations into a graph representation.
Earlier graph neural networks were developed before the terminology became standardized. The 2017 paper “Neural Message Passing for Quantum Chemistry” by Justin Gilmer and colleagues presented a framework that unified several existing graph-learning architectures. Molecular graphs provide a concrete example: atoms are nodes, bonds supply edges and edge features, and repeated message-passing steps combine information about chemical neighborhoods. A final prediction can concern a molecular property rather than any individual atom. Related methods support node classification, link prediction, and physical-system modeling.
These networks are typically trained using backpropagation, which differentiates a loss through message construction, aggregation, and state updates. The local computations may run in parallel, but the mathematical graph should not be confused with the hardware network. A single graphics processing unit can evaluate a large graph using indexed tensor operations. Conversely, distributing one graph across several machines introduces actual communication of node features and gradients, creating a separate systems-level message-passing problem.
The architecture has characteristic limitations. After local layers, a node ordinarily depends only on information within graph hops, unless additional long-range mechanisms are present. Increasing depth can cause oversmoothing, in which node representations become difficult to distinguish, or oversquashing, in which information from a rapidly expanding neighborhood is compressed into fixed-size vectors. Many standard neighborhood-aggregation networks also have expressive power bounded by a form of the one-dimensional Weisfeiler–Leman graph-refinement procedure, so some distinct graph structures remain indistinguishable to them.
Attention-weighted messages, richer edge states, positional information, and modified graph connectivity can change these properties, but also alter computational cost and structural assumptions. In molecular and physical applications, architectures may additionally enforce invariance or equivariance under translations, rotations, and permutations. These constraints determine how representations and outputs transform when coordinates or node labels change, connecting learned local messages to the symmetries of the modeled system.