<p>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.</p>

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

<blockquote>
  <p>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 <code>n</code> threads cannot reach consensus on
  <code>k</code> values, where <code>n &gt; 2</code> and <code>k &gt; 2</code>.</p>
</blockquote>

CC BY-SA 3.0
2016-02-22T20:43:29.057Z
I'm not afraid of formalism! :-)
isekaijin
CC BY-SA 3.0
2016-02-22T19:20:30.153Z
2016-02-26T20:05:25.583Z
2016-02-26T20:05:25.583Z
user650881
<p>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: </p>

<ol>
<li><p>There are many models of distributed/parallel/concurrent computation.</p></li>
<li><p>There is not a general transformation that given the specification of a sequential data structure gives you <em>the</em> specification of its concurrent version. There are various conditions (generally categorized under <a href="https://en.wikipedia.org/wiki/Safety_(distributed_computing)" rel="nofollow noreferrer">safety</a> and <a href="https://en.wikipedia.org/wiki/Liveness" rel="nofollow noreferrer">liveness</a> 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.</p></li>
</ol>

<p>Some questions about references on distributed computing:</p>

<ul>
<li><a href="https://cs.stackexchange.com/q/4793/">Start learning about Theory of Distributed Systems?</a></li>
<li><a href="https://cstheory.stackexchange.com/q/33243/">Modern distributed computing book</a></li>
<li><a href="https://cstheory.stackexchange.com/a/6338/">Books: Distributed Computing</a></li>
</ul>

<p>See also <a href="https://cstheory.stackexchange.com/q/426/">Why have we not been able to develop a unified complexity theory of distributed computing?</a></p>

CC BY-SA 3.0
2016-02-21T18:54:24.253Z
2016-02-21T18:54:24.253Z
2017-04-13T12:48:30.830Z
Kaveh
<p>The first rule of concurrent data structures is: You do not want concurrency.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-02-29T04:45:09.720Z
What do you mean by “static data structures”?
isekaijin
CC BY-SA 3.0
2016-02-29T09:23:02.430Z
@EduardoLeón Structures that can be queried but not updated efficiently, e.g. sorted arrays instead of search trees. As an added benefit, static structures tend to be smaller and faster than dynamic ones.
Jouni Sirén
CC BY-SA 3.0
2016-02-29T03:03:13.703Z
2016-02-29T03:03:13.703Z
Jouni Sirén
<p>I previously asked this question <a href="https://softwareengineering.stackexchange.com/questions/310676/">on Programmers.SE</a>, without success.</p>

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

<p>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.</p>

<p>So:</p>

<ol>
<li><p>What techniques or heuristics exist for designing concurrent data structures?</p></li>
<li><p>Are there any books, papers, blog posts, tutorials, etc. explaining these techniques and heuristics?</p></li>
</ol>

<ds.algorithms><reference-request><ds.data-structures><concurrency>
How to design concurrent data structures?
isekaijin
# How to design concurrent data structures?

(Asked by: username_0 on 2016-02-21)

I previously asked this question [on Programmers.SE](https://softwareengineering.stackexchange.com/questions/310676/), 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?

**Tags:** ds.algorithms, reference-request, ds.data-structures, concurrency

---

## 3 answers

### Answer by username_1 on 2016-02-22. Score: 5

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`.

> **Comments:**
> **username_0**: I'm not afraid of formalism! :-)  

---

### Answer by username_2 on 2016-02-21. Score: 3

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](https://en.wikipedia.org/wiki/Safety_(distributed_computing)) and [liveness](https://en.wikipedia.org/wiki/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?](https://cs.stackexchange.com/q/4793/)
* [Modern distributed computing book](https://cstheory.stackexchange.com/q/33243/)
* [Books: Distributed Computing](https://cstheory.stackexchange.com/a/6338/)

See also [Why have we not been able to develop a unified complexity theory of distributed computing?](https://cstheory.stackexchange.com/q/426/)


---

### Answer by username_3 on 2016-02-29. Score: 1

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.

> **Comments:**
> **username_0**: What do you mean by “static data structures”?  
> **username_3**: @EduardoLeón Structures that can be queried but not updated efficiently, e.g. sorted arrays instead of search trees. As an added benefit, static structures tend to be smaller and faster than dynamic ones.  

---

