Working Through Herlihy's Concurrent Programming Exercises
The exercises in Michael Herlihy and Shavit's The Art of Multiprocessor Programming are widely considered one of the tougher introductions to lock-free and wait-free concurrency. People look for a Herlihy Answers Study Guide because working through the problems without a clear understanding of the underlying lemmas and construction patterns is genuinely painful. The material assumes you already understand basic concurrency primitives at a comfortable level. If you're struggling, that's normal. Here is how I approached it and what actually helped. I spent roughly six weeks working through the major synchronization problems — the read-write registers, the test-and-set object, the stack, the queue, and the counter constructions. The key realization that changed my entire approach was that Herlihy's proofs are constructive. Each impossibility result comes with a topological argument, and each possibility result comes with an explicit algorithm. If you treat the answers as algorithms to implement and verify rather than proofs to memorize, you learn significantly more in less time. The common trap beginners fall into is trying to verify correctness by tracing execution step by step. With concurrent algorithms, especially the wait-free constructions in Chapter 11, that approach breaks down almost immediately because the number of interleavings is unbounded. Instead, I learned to look for the invariant the authors are building toward. In the read-write register construction using test-and-set objects, for example, the critical invariant is that every process reads the latest written value. Once you see that the construction enforces this through the ordering of test-and-set acquisitions, the rest of the analysis follows mechanically. Skipping straight to the answer without attempting this invariant identification yourself is where most people waste time.
I ran into a specific problem with the lock-free stack exercise in Chapter 6. The standard algorithm uses a version-tagged pointer to avoid the ABA problem, and the exercise asks you to prove wait-freedom. When I tried to construct the proof directly from the algorithm pseudocode, I kept getting stuck on the case where two processes compare-and-swap the same node. The issue was that I was treating the operations as sequential rather than recognizing the linearization points embedded in the CAS instructions. My workaround was to write out the linearization points explicitly for each method before attempting the proof. Once I mapped them — push linearizes at its successful CAS, pop at its successful CAS on the updated head — the correctness argument became straightforward. This technique of finding linearization points first rather than last saved me probably ten hours across several chapters. For the Herlihy Answers Study Guide, the most useful resource I found was a combination of the textbook solutions manual available through academic channels and a set of annotated implementations. Having the code alongside the proof meant I could see exactly which operation corresponded to which step in the topological argument. The textbook's companion website at mhp.cs.rutgers.edu/MultiprocessorProgramming has additional material, though it's not always up to date with the second edition's numbering. One counter-intuitive thing about these exercises: the harder problems are often easier to understand than the early ones. The foundational chapters build a lot of notation and topological machinery before you apply it to a concrete problem. By the time you reach the later chapters on the snapshot object and the universal construction, you've internalized the pattern and the proofs feel routine. Don't skip ahead thinking you'll come back. The notation carries forward and later problems assume fluency with the terminology from Chapter 3.
Here is a practical study sequence that I found effective. Start with the consensus number results in Chapter 4. Understand why test-and-set has consensus number 2 and why compare-and-swap has consensus number infinity. This single concept underpins almost everything else in the book. Then move to the wait-free hierarchy and the constructions in Chapter 11. The universal construction is the most important algorithm in the book — it shows how to build any wait-free object from any shared primitive. Understanding it will make the later material feel much less abstract. Implementation practice matters more than proof reading. I wrote a small Java library that implemented each data structure from the book and then stress-tested it with multiple threads. The herlihy-style lock-free queue, for instance, behaves completely differently under high contention than the textbook examples suggest. Adding instrumentation to track linearization point violations turned out to be more educational than any number of proof exercises. A simple helper that records the state of shared variables at each operation's linearization point and then checks the invariant post-hoc caught several subtle bugs in my implementations that I would have missed otherwise.
Get the Full Details
Limits and Honest Downsides
The Herlihy framework is not the only way to think about concurrency, and it has real blind spots. The book focuses heavily on the theoretical model — the shared memory PRAM with atomic snapshots and linearizability. It does not cover real-world concerns like memory reclamation in lock-free data structures (you need something like hazard pointers, epoch-based reclamation, or RCU), hardware memory models beyond the sequential consistency assumption, or the performance characteristics that matter on actual hardware. A solution that is theoretically wait-free can perform terribly on a system with NUMA topology or strong cache coherency overheads. If your goal is to write production concurrent code, you will need supplementary material on these topics. The proofs using topological arguments are elegant but dense. I have seen people spend days on a single impossibility result because they do not know the combinatorial topology prerequisites. If you find yourself stuck for more than a few hours on a proof, look for an informal explanation or a video lecture first before diving back into the formalism. The material is better understood intuitively and then formalized, not the other way around. A few additional practical notes that came up during my own work. The second edition revised several exercises from the first edition, so make sure you are working from the correct problem set. Some online solution repositories still reference first-edition numbering, which causes confusion when you are looking for a specific exercise. The counter construction in Chapter 5 has a well-known optimization using a binary tree of add-one objects that the book introduces later — attempting to derive this on your own before seeing it is a valuable exercise even if you do not succeed.
The snapshot object in Chapter 10 is another area where the textbook presentation is compressed. The algorithm uses a double-scan technique that is tricky to get right. I found it helpful to draw the timeline of operations across all processes before reading the proof. Seeing the two-scan guarantee visually made the correctness argument click in a way that reading the formal version did not. If you are using this as part of a course, check whether your instructor expects you to produce full formal proofs or to understand the constructions at a higher level. The book is demanding either way, but the time investment is very different. A full formal proof of wait-freedom for the counter can take an hour or more. Understanding the construction and being able to explain why it is wait-free usually takes twenty minutes. Knowing which level your situation requires will save you a lot of unnecessary effort. For the Herlihy Answers Study Guide, I recommend pairing whatever solution material you use with your own attempt first. Reading through someone else's proof without having wrestled with the problem for at least thirty to forty-five minutes tends to create an illusion of understanding. You will recognize the steps and think you get it, but when you try to reconstruct the argument from scratch later, the gaps become obvious. The struggle is the learning. That is the main thing I wish I had understood better going in.
