ebdilo

Proving Linearisability of Treiber's Stack


Treiber's stack represents shared state as a linked list whose head changes through compare and swap so that concurrent pushes and pops can be analysed against an ordinary sequential stack specification. The argument below assumes sequentially consistent accesses and retained immutable nodes while Lean checks the sequential equations and a finite history example whose proof does not extend to the concurrent heap implementation.

Model

The shared pointer top identifies either an empty stack or the first node of a chain whose values and next pointers remain immutable after publication throughout the executions considered here. Every push allocates a fresh node that cannot be freed or reinserted during the argument because another thread may still hold a pointer obtained before a concurrent pop removed it.

Loads and strong CAS operations on top follow a single sequentially consistent order that respects each thread's execution while initialising node fields before publication makes those immutable fields available to later readers. A native C or C++ implementation consequently needs a separate justification for its publication and lifetime rules because the atomicity of a CAS instruction does not establish the required memory ordering or reclamation guarantees.

Address reuse can make a saved successor invalid even when CAS encounters its expected address again because the current allocation at that address may no longer be the node that the reader originally inspected. Michael's hazard pointer paper explains the reclamation problem and a protection scheme for concurrent structures while the retained immutable nodes assumed here make a return to the same node harmless without covering later reuse or reinsertion.

Sequential specification

The abstract stack is a list whose first element represents the top and whose operations either prepend a value or remove the first element while reporting whether a value was available in the original state. The definitions and equations below are checked with Lean 4.24.0 so that the abstract behaviour used by the concurrency argument has an executable specification with explicitly stated return values.

abbrev Stack (α : Type) := List α

def push (a : α) (s : Stack α) : Stack α := a :: s

def pop : Stack α → Option (α × Stack α)
  | [] => none
  | a :: s => some (a, s)

theorem pop_push (a : α) (s : Stack α) : pop (push a s) = some (a, s) := rfl

theorem pop_empty : pop ([] : Stack α) = none := rfl

inductive Action (α : Type) where
  | push : α → Action α
  | pop : Action α

def step (s : Stack α) (action : Action α) : Stack α × Option α :=
  match action with
  | .push value => (value :: s, none)
  | .pop =>
      match s with
      | [] => ([], none)
      | value :: rest => (rest, some value)

theorem step_push (a : α) (s : Stack α) : step s (.push a) = (a :: s, none) := rfl

theorem step_pop (a : α) (s : Stack α) : step (a :: s) .pop = (s, some a) := rfl

theorem step_pop_empty : step ([] : Stack α) .pop = ([], none) := rfl

Algorithm

A push repeatedly reads top and attempts to publish a private node linked to that observation while a pop attempts to replace the observed head with its immutable successor and return the value from the detached node. The listing is pseudocode for the stated atomic model and does not introduce a native CAS implementation because the proof treats pointer identity and the publication of initialised nodes as explicit assumptions.

push(value):
  node = allocate_fresh(value)
  repeat:
    expected = load_SC(top)
    node.next = expected
  until CAS_SC(top, expected, node)

pop():
  repeat:
    expected = load_SC(top)
    if expected == null:
      return None
    successor = expected.next
  until CAS_SC(top, expected, successor)
  return Some(expected.value)

Figure 1 compares the private node before publication with the reachable chain after a successful CAS and shows how its existing link to a changes the represented list from [a, b] to [x, a, b].

Before publication top points to a while private x points to a. After CAS top points to x, then a, then b
Figure 1 shows how a private node acquires its successor before the successful CAS publishes it as the new head while preserving every link in the chain that was already reachable.

Histories

Herlihy and Wing's definition requires a legal sequential explanation whose ordering preserves the precedence between completed calls whenever one operation returns before another operation is invoked in the concurrent execution. Merely finding a permutation that reproduces the observed values would leave that requirement unchecked because an otherwise legal stack execution could reverse an order that the original calls and responses already fixed.

A completed push followed by a pop returning empty cannot be justified by placing the pop first because that proposed explanation contradicts the order established by the completed push before the later invocation. Each record therefore keeps the operation identifier together with its invocation and response positions and its observed result so that reordering preserves the association between each action and the value that it returned.

structure Operation (α : Type) where
  id : Nat
  invoked : Nat
  responded : Nat
  action : Action α
  result : Option α

def Legal : Stack α → List (Operation α) → Prop
  | _, [] => True
  | state, operation :: rest =>
      operation.result = (step state operation.action).2 ∧
        Legal (step state operation.action).1 rest

def Before (order : List (Operation α)) (first second : Operation α) : Prop :=
  ∃ before between after, order = before ++ first :: between ++ second :: after

def WellFormed (history : List (Operation α)) : Prop :=
  history.Pairwise (fun first second => first.id ≠ second.id) ∧
    (∀ operation ∈ history, operation.invoked < operation.responded) ∧
    (history.flatMap (fun operation => [operation.invoked, operation.responded])).Nodup

def Linearisable (history : List (Operation α)) : Prop :=
  WellFormed history ∧ ∃ order,
    order.Perm history ∧ Legal [] order ∧
      ∀ first ∈ history, ∀ second ∈ history,
        first.responded < second.invoked → Before order first second

WellFormed requires unique operation identifiers and distinct event positions with valid call and return intervals while Legal follows the evolving stack and Before records precedence between operations in the proposed sequential order. This criterion covers finite records of completed calls and leaves per thread event streams and pending invocations to the fuller history construction that Herlihy and Wing use when defining linearisability for concurrent objects.

def sample : List (Operation Nat) :=
  [⟨0, 0, 1, .push 1, none⟩,
   ⟨1, 2, 3, .push 2, none⟩,
   ⟨2, 4, 5, .pop, some 2⟩]

example : Legal [] sample := by
  simp [Legal, sample, step]

theorem sample_linearisable : Linearisable sample := by
  refine ⟨?_, sample, List.Perm.refl _, ?_, ?_⟩
  · simp [WellFormed, sample]
  · simp [Legal, sample, step]
  · intro first firstMember second secondMember precedence
    simp [sample] at firstMember secondMember
    rcases firstMember with rfl | rfl | rfl <;>
      rcases secondMember with rfl | rfl | rfl
    all_goals simp only at precedence
    all_goals first
      | omega
      | exact ⟨[], [], sample.drop 2, rfl⟩
      | exact ⟨[], (sample.drop 1).take 1, [], rfl⟩
      | exact ⟨sample.take 1, [], [], rfl⟩

The final theorem uses the recorded order as its witness because the event positions require both pushes to precede the later pop and therefore let Lean check the observed stack results together with the real time condition.

Linearisation

A push and a pop that returns a value take effect at their successful CAS operations while an empty pop takes effect at the load that observes null and therefore witnesses an empty abstract stack at that instant. Failed CAS attempts contribute no separate abstract operation because they change no shared state and merely cause the current invocation to retry before it reaches the event selected for its eventual result.

Abstract states empty, a, b followed by a, then a after pop returns b
Figure 2 shows the abstract stack after each selected event so that the return value of the pop follows from the list state established by the two preceding pushes.

Figure 2 records the abstract stack after each selected CAS and gives one legal sequential order whose state transitions explain the returned value without attempting to depict the invocation and response intervals of the concurrent calls. To establish linearisability for a finite complete history generated by the model we must connect the selected atomic events to their enclosing calls and show that their ordered effects preserve the abstract representation.

Interval containment follows because each successful push or pop performs its chosen CAS after invocation and before response while an empty pop performs the selected null observing load within the corresponding interval before returning.

Real time preservation follows from the sequentially consistent order because the selected event of an earlier completed call lies before its response and the selected event of a later call lies after that later invocation.

Sequential legality follows by maintaining an invariant that identifies the chain reachable from top with the abstract list and by observing that the initially null pointer represents precisely the empty state required by the specification. When a push succeeds its newly published node already points at the current head so that the resulting chain prepends exactly the pushed value without changing the representation of the previously reachable elements.

At a successful pop CAS the expected pointer identifies the current head whose immutable next pointer represents the remainder of the abstract list so that installing that successor removes exactly the first element and preserves the required state. Retaining removed nodes keeps the dereference valid while forbidding reinsertion prevents the saved node from acquiring a different link before the CAS that decides whether the operation can complete with that observation.

An empty pop returns no value because its selected load observes the null pointer at a point where the representation invariant identifies the reachable chain with an empty list and leaves the abstract state unchanged. Reads and failed CAS attempts preserve that invariant between selected events so induction over the ordered operations establishes sequential legality while interval containment ensures that the resulting explanation also respects the required real time precedence.

Checked scope

Lean checks the sequential equations and proves the sample history linearisable while the relationship between the heap invariant and arbitrary concurrent executions remains the mathematical argument given under the model assumptions above. Verifying a native implementation would additionally require a formal connection to its memory ordering and reclamation scheme together with a separate progress argument if lock freedom were among the properties that the implementation claimed.

References

Maurice Herlihy and Jeannette Wing's Linearizability: A Correctness Condition for Concurrent Objects appeared in ACM TOPLAS 12(3) in 1990 and gives the history construction and real time condition in Section 2 on pages 467 to 469.

Maged Michael's Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects appeared in IEEE TPDS 15(6) in 2004 and explains reclamation and ABA in Section 2 before applying the protection scheme to a stack in Section 4.2.

← ebdilo