How to design concurrent data structures? 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:


What techniques or heuristics exist for designing concurrent data structures?
Are there any books, papers, blog posts, tutorials, etc. explaining these techniques and heuristics?
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 &gt; 2 and k &gt; 2.