What Is Message Passing?

Message passing is a computational paradigm in which processes or nodes exchange information by sending discrete packets of data, called messages, rather than sharing a common memory space. It is the primary model for coordination in distributed computing, parallel processing on multi-processor systems, and probabilistic inference over graphical models. The fundamental abstraction is that a sender composes a message, transmits it to one or more receivers, and the receivers act on the contents without needing direct access to the sender's internal state.

Message passing has roots in two distinct traditions. In computer science, it became the dominant programming model for distributed systems and high-performance computing, formalized in the Message Passing Interface (MPI) standard in 1994. In probabilistic inference, the sum-product algorithm and related belief propagation techniques, developed through the 1980s and 1990s, showed that iterative message exchange over a graph could efficiently compute marginal probabilities that would be intractable by direct enumeration.

Belief Propagation

Belief propagation (BP) is a message-passing algorithm for performing exact or approximate inference in probabilistic graphical models, including Bayesian networks and Markov random fields. In the sum-product variant, each node in the factor graph passes a probability distribution over its variable to its neighbors; these incoming messages are combined to compute updated marginal beliefs, and the process repeats until convergence. On tree-structured graphs, BP converges in a finite number of passes and produces exact marginals. On graphs with loops, the algorithm is run as "loopy belief propagation" and typically converges to a good approximate solution despite the lack of exactness guarantees. Belief propagation is the computational foundation for turbo decoding in error-correcting codes, where it was independently developed as a decoder for turbo codes and low-density parity-check (LDPC) codes. The Stanford lecture notes on belief propagation by Montanari and Mezard provide a rigorous treatment of the algorithm's derivation and convergence properties.

Message Passing in Distributed Computing

In distributed systems, message passing decouples processes by requiring them to communicate only through explicit send and receive operations, with no shared mutable memory. This model scales to thousands of processors because each process maintains its own address space, eliminating the synchronization bottlenecks of shared memory. The Message Passing Interface (MPI) standardizes point-to-point and collective communication operations for parallel scientific computing, supporting operations such as broadcast, scatter-gather, and reduction that distribute or aggregate data across process groups. MPI is used in large-scale numerical simulations for climate modeling, structural mechanics, and computational fluid dynamics. Actor-based models, such as those in the Erlang programming language and the Akka framework, apply message passing to concurrent software systems, with actors exchanging immutable messages and maintaining private state that no other actor can directly modify.

Message Passing Algorithms in Machine Learning

Recent research has extended message-passing principles to graph neural networks (GNNs), where nodes in a graph iteratively aggregate feature vectors from their neighbors through learned message functions. This framework, known as the message passing neural network (MPNN) architecture, generalizes many GNN variants, including graph convolutional networks and attention-based models. MPNNs are applied to molecular property prediction, social network analysis, and knowledge graph reasoning. A research paper on deep learning via message passing and belief propagation demonstrated that BP-based optimization can train multi-layer neural networks with discrete weights, providing an alternative to gradient descent for certain architectures. The IPAM UCLA lecture notes on graphical models and belief propagation connect probabilistic inference to the broader message passing framework used in these learning systems.

Applications

Message passing has applications in a wide range of disciplines, including:

• Error-correcting code decoding for communications and data storage
• Distributed scientific computing using MPI for large-scale simulations
• Molecular and drug property prediction using graph neural networks
• Probabilistic inference in Bayesian networks for medical diagnosis
• Actor-based concurrent software architectures in cloud systems
• Combinatorial optimization via survey propagation algorithms