Message Passing and Shared Memory

Message passing and shared memory are the two fundamental abstractions through which concurrent processes interact, and much of distributed computing studies how to simulate one with the other.

Definition

In the message-passing model processes communicate only by sending and receiving messages over channels; in the shared-memory model they communicate by reading and writing shared objects such as registers. Each is a precise computational model with its own correctness conditions.

Scope

This topic covers point-to-point and broadcast message-passing models with their delivery and ordering semantics, shared-memory models built from read/write registers and stronger synchronization objects, and the classical results showing how shared memory can be emulated atop message passing (and vice versa) under various failure assumptions. It also covers the register hierarchy and the consensus hierarchy that rank the power of shared objects.

Core questions

• What delivery and ordering guarantees does a channel provide, and how do they affect algorithm design?
• Can a shared-memory abstraction be reliably built on top of an unreliable message-passing network?
• How do synchronization objects differ in their power to solve consensus?

Key theories

Register and consensus hierarchy

Shared objects are ranked by their consensus number—the maximum number of processes for which they can solve wait-free consensus—placing simple read/write registers at the bottom and universal objects such as compare-and-swap at the top.

Register constructions

Lamport's hierarchy of safe, regular, and atomic registers, and constructions that build stronger registers from weaker ones, formalize exactly what it means for concurrent reads and writes to behave correctly.

Simulating shared memory over message passing

Atomic single-writer and multi-writer registers can be emulated over an asynchronous message-passing network tolerating a minority of crash failures using quorum techniques, unifying the two communication models.

Clinical relevance

The message-passing/shared-memory distinction maps directly onto real platforms: clusters and the cloud are message-passing systems, multicore servers expose shared memory, and distributed key-value stores effectively present a shared-register abstraction over a message-passing network.

History

Lamport's 1986 papers formalized concurrent registers; Herlihy's wait-free hierarchy in 1991 ranked synchronization primitives by consensus number; and Attiya and Welch's text consolidated the simulations relating message passing and shared memory, establishing the duality at the heart of the field.

Key figures

• Leslie Lamport
• Maurice Herlihy
• Nir Shavit
• Hagit Attiya
• Jennifer Welch

Seminal works

• herlihy2008
• attiya2004
• lamport1986

Frequently asked questions

Are message passing and shared memory equivalent?

They are equivalent in computational power under suitable failure assumptions—each can simulate the other—but they differ sharply in programming convenience and performance, which is why systems pick one as their native model.