Skip to content

Shared memory

Did it behave like one thing at a time?

The right question to ask of a concurrent data structure, and the one that can actually be answered.

12 minutes · linearizability · sequential specification · operation windows

“Correct” is not a question you can ask a queue

Ask whether a concurrent counter returned the right values and you get nowhere: two increments that overlap have no single right answer, because there is no single order they happened in. The question that does work is narrower and much more useful — **is there some order, consistent with how the calls actually overlapped, that explains every result that came back?**

If there is, then each operation behaved as though it took effect at one instant somewhere inside its own window, and every caller can reason about the structure as if it were sequential. That is linearizability, and it is what people mean when they say a concurrent container is correct.

If there is not, no rearrangement will help. Two increments that both returned 1 cannot be explained by any sequence, because the second one to take effect must return more than the first. The structure did something no sequential counter can do, and that is a fact rather than a matter of taste.

Everything you do here stays in this browser.