How to design concurrent data structures?

Question

I previously asked this question on Programmers.SE, without success.

I'm looking for written learning resources on how to design concurrent data structures. I'm more interested in the design process (e.g., identifying the right invariants) than in the final product (a full code listing).

For a concrete example: I really enjoyed Chris Okasaki's book “Purely Functional Data Structures”, because it's more than just a reference - it guides the reader through the design of its data structures and algorithms. Often, the book motivates a tricky or non-obvious design by first giving a more naïve version, and only then refining it until the desired time complexity (either worst-case or amortized) is achieved. This is the kind of thing I'm looking for.

So:

1. What techniques or heuristics exist for designing concurrent data structures?

2. Are there any books, papers, blog posts, tutorials, etc. explaining these techniques and heuristics?

Answer 1

While I have not read deeply in this area, I found The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit to be a helpful introduction and survey of techniques. It explores different algorithms, reasons about how they work and examines the trade-offs, features and limitations of the different approaches. While it has some formalism I expect it is a fairly introductory and accessible text.

For a flavor of the text, here is the introduction to the section on Atomic Registers from the 2008 edition:

The obvious place to begin is to ask whether we can solve consensus using atomic registers. Surprisingly, perhaps, the answer is no. We will show that there is no binary consensus protocol for two threads. We leave it as an exercise to show that if two threads cannot reach consensus on two values, then n threads cannot reach consensus on k values, where n > 2 and k > 2.

Answer 2

The answer is not as simple as functional programming. In functional programming here we have a general concept of what is functional programming and the specification of data structures themselves do not change by the fact that they are functional. However that is not the case with concurrency:

1. There are many models of distributed/parallel/concurrent computation.

2. There is not a general transformation that given the specification of a sequential data structure gives you the specification of its concurrent version. There are various conditions (generally categorized under safety and liveness conditions) that we can require from a concurrent version of a data structure, there are various new outcomes (e.g. pausing operations, aborting operations, crashes, etc.). So there can be many different specifications for concurrent versions of a sequential data structure.

Some questions about references on distributed computing:

• Start learning about Theory of Distributed Systems?
• Modern distributed computing book
• Books: Distributed Computing

See also Why have we not been able to develop a unified complexity theory of distributed computing?

Answer 3

The first rule of concurrent data structures is: You do not want concurrency.

In the ideal case, distributed/parallel/concurrent computing means that you have a number of completely independent sequential processes. Each process has its own data and resources, and the process is not even aware of any other processes.

In the worst case, you have a shared memory system with multiple threads querying and updating the same data structures concurrently. Something has probably gone horribly wrong, if you are seriously considering this.

Of course, when we are talking about concurrent data structures, some degree of concurrency is unavoidable. We still want to minimize it. The longer a process can work sequentially without touching mutexes, doing atomic operations, or passing messages, the more likely everything works correctly and the performance is acceptable.

Static data structures with batch updates require less synchronization than dynamic data structures. You should try to make your concurrent data structures static, or at least as close to static as possible. If your algorithm requires interleaving queries with updates, try changing the algorithm before resorting to shared dynamic structures.

The same design principle also applies to updating static data structures. The more independent you can make the processes updating the structure, the better everything works.