Concurrent Objects – The Art of Multiprocessor Programming – Part 2


June 7, 2012


Maurice Herlihy


Brown University


The behavior of concurrent objects is best described through their safety and liveness properties, often referred to as correctness and progress. In this lecture, we examine various ways of specifying correctness and progress.

The Relative Power of Synchronization Operations:
Imagine you are in charge of designing a new multiprocessor. What kinds of atomic instructions should you include? The literature includes a bewildering array of different choices. Supporting them all would be complicated and inefficient, but supporting the wrong ones could make it difficult or even impossible to solve important synchronization problems. Our goal is to identify a set of primitive synchronization operations powerful enough to solve synchronization problems likely to arise in practice.

Linked Lists: Locking, Lock-Free, and Beyond:
This lecture introduces several useful techniques that go beyond locking to allow multiple threads to access a single object at the same time.


Maurice Herlihy

Maurice Herlihy has an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He served on the faculty of Carnegie Mellon University, on the staff of DEC Cambridge Research Lab, and is currently Professor in the Computer Science Department at Brown University. He is an ACM Fellow, and is the recipient of the 2003 and 2012 Dijkstra Prizes in Distributed Computing, and the 2004 Goedel Prize in theoretical computer science. He won the 2008 ISCA influential paper award for the 1993 paper that coined the term “Transactional Memory”. He is a fellow of the ACM. His interests include practical and theoretical aspects of parallel and distributed computing.