Concurrency: The Works of Leslie Lamport

by Dahlia Malkhi (editor)

This book is a celebration of Leslie Lamport's work on concurrency, interwoven in four-and-a-half decades of an evolving from the introduction of the first personal computer to an era when parallel and distributed multiprocessors are abundant. His works lay formal foundations for concurrent computations executed by interconnected computers. Some of the algorithms have become standard engineering practice for fault tolerant distributed computing - distributed systems that continue to function correctly despite failures of individual components. He also developed a substantial body of work on the formal specification and verification of concurrent systems, and has contributed to the development of automated tools applying these methods. Part I consists of technical chapters of the book and a biography. The technical chapters of this book present a retrospective on Lamport's original ideas from experts in the field. Through this lens, it portrays their long-lasting impact. The chapters cover timeless notions Lamport the Bakery algorithm, atomic shared registers and sequential consistency; causality and logical time; Byzantine Agreement; state machine replication and Paxos; temporal logic of actions (TLA). The professional biography tells of Lamport's career, providing the context in which his work arose and broke new grounds, and discusses LaTeX - perhaps Lamport's most influential contribution outside the field of concurrency. This chapter gives a voice to the people behind the achievements, notably Lamport himself, and additionally the colleagues around him, who inspired, collaborated, and helped him drive worldwide impact. Part II consists of a selection of Leslie Lamport's most influential papers. This book touches on a lifetime of contributions by Leslie Lamport to the field of concurrency and on the extensive influence he had on people working in the field. It will be of value to historians of science, and to researchers and students who work in the area of concurrency and who are interested to read about the work of one of the most influential researchers in this field.

Genres: Programming, Computer Science, Technology, Software

365 pages, Paperback

Published September 16, 2019

Reviews

[Warren Mcpherson · Rating 4 out of 5]

This is a history of algorithms relating to concurrent processing. It follows the contributions of one person but shows many others participating in the development.
Exclusive access to shared memory is a foundational problem. Several algorithms have addressed it over time, the Bakery Algorithm is a clever and simple solution. There is an interesting discussion of the notion of global time. The challenge of ordering events in a distributed system has limitations that need to be accommodated. The problem of Byzantine Faults is considered mostly from the perspective of system reliability but as with many of these issues, several levels are considered.
The discussion of formal proof or verification of algorithms is interesting. One point made was that mathematic proof of the correctness of an algorithm can give engineers working on today's cloud systems confidence to tune them more aggressively for performance.
The Paxos essay is an elaborate story designed to demonstrate state replication with benign failures. The analogy is imperfect as all analogies are but the detail leads the reader's interest in a way that might not be best for demonstrating the algorithm. But the development is critical as it demonstrates a system with no single point of failure; an important precursor to big data and blockchain systems.
Grace Hopper anticipated the significance of concurrent algorithms saying "If one ox could not do the job they did not try to grow a bigger ox, but used two oxen. When we need greater computer power, the answer is not to get a bigger computer, but to build systems of computers and operate them in parallel." Today we are using graphics processors to do hundreds of calculations in parallel yet people often misunderstand some of the foundational problems. This book does a good job of reviewing those problems and often covering them a couple of times in different voices, something that can help solidify your understanding.

[Carter · Rating 5 out of 5]

The quality of Leslie Lamport's writing varies a great deal. A lot of them are early seminal contributions in the field however. Theorizing about the details of concurrency in a single machine, or in some cases a distributed setting, is still of great interest. Better recent research articles can be found in PODC. Worth the read.

[Jose Sanz]

I will try learning about this in a book that is explained for dummies (like me), like a distributed systems book.