The art of multiprocessor programming

About the book

The Art of Multiprocessor Programming addresses a specific engineering problem: how to write correct software when several processors share memory and act at once. Maurice Herlihy treats that problem as a discipline with its own vocabulary, proof techniques, and failure modes. The book assumes readers will need to reason formally about what their code does under interleaving.

The work moves through the machinery of shared-memory concurrency: mutual exclusion, locks, atomic registers, consensus, and the impossibility results that constrain what any algorithm can promise. Abstract definitions sit alongside concrete algorithms, so a reader sees both the property being claimed and the code meant to deliver it. The emphasis falls on why a construction works and where it breaks, which places the book closer to a theory text with engineering consequences than to a cookbook of patterns.

Herlihy writes for people who will implement or evaluate concurrent systems. Correctness is treated as something to establish, not assume, and the gap between a plausible-looking algorithm and one that survives adversarial scheduling runs through the material.

How to read it

Approach the book as a sequence of arguments to follow rather than a reference to skim. The definitions matter, and later material depends on earlier distinctions, so skipping the foundational sections tends to make the algorithm discussions harder than they need to be. Keep paper or a scratch file nearby for the proof sketches and for tracking the properties each construction claims.

The difficulty is real but uneven. Readers comfortable with discrete mathematics and basic algorithm analysis will find the formal passages manageable; those without that background should expect to slow down and reread. The examples reward attention to assumptions about memory models and scheduling, since those assumptions often decide whether an algorithm is correct.

Who it suits

This book suits programmers who already write concurrent code and want to understand the principles beneath the libraries they use. Students in systems or theory courses will find a coherent treatment of shared-memory concurrency with formal grounding. Engineers who need to judge whether a synchronization scheme is sound, or who want to read the research literature on multiprocessors, will get the most from it. Complete beginners to programming should build fundamentals first.

Reading considerations

Hardware and language memory models have moved since the book appeared, and some examples reflect the systems of that period. Treat the theoretical results as durable and the practical details as needing cross-checking against current platforms. The book is demanding, and readers seeking quick recipes for a specific language will need to translate its abstractions themselves.