Explain overlapping intervals as ordered instantaneous operations
Concurrent queue operations may overlap. Linearizability asks whether each can be understood as taking effect at one point between invocation and response while matching a legal sequential queue behavior. Finding a convenient internal instruction is not sufficient; the resulting order and returned values must agree with the specification. Begin with a short history of completed calls.
Our sequential queue appends on put and removes the head on get. The small checker excludes empty gets and pending operations, which a general treatment must address separately. Building on the definition reading, this guide constructs candidate orders from invocation/response intervals and checks both real-time constraints and returned values. It teaches a concrete reasoning procedure rather than claiming to verify every implementation of a concurrent queue.
Choose an order for overlapping puts
Suppose put(1) runs from time zero to three and put(2) from one to two. They overlap, so the earlier response of put(2) does not force it to be first. A candidate can place put(1) before put(2). A later get from four to five returning one is then consistent with the sequential order put-one, put-two, get-one.
If one operation returns before another is invoked, however, its order must be preserved. The later get cannot move before the already completed puts. Draw overlap freedom separately from nonoverlap constraints. Neither invocation order nor response order alone completely determines the required sequence. Equally, arbitrary reordering cannot explain every history: real-time constraints and return values still restrict the candidate.
| Operation | Call | Return | Candidate sequential order |
|---|---|---|---|
| put(1) | 0 | 3 | Can be first |
| put(2) | 1 | 2 | Can be second |
| get → 1 | 4 | 5 | After both puts |
Check real time and sequential behavior separately
The checker enumerates permutations of a few completed operations. First reject orders that violate an end-before-start constraint. Then replay each remaining order from an empty queue and compare every returned get value with the head. Timestamps are one exact model ordering axis here, not automatically reliable observations from unrelated machine clocks. The example explicitly uses a strict endpoint inequality.
One legal candidate explains that finite history under the given specification. No candidate means the supplied history cannot be explained within those assumptions. It does not prove every execution of an implementation correct or incorrect. Captured operation identities and return values must themselves be trustworthy. Correct history collection and correct order checking are two separate parts of a verification argument.
from itertools import permutations
def legal(history):
for order in permutations(range(len(history))):
rank={key:i for i,key in enumerate(order)}
if any(a[2]<b[1] and rank[i]>rank[j] for i,a in enumerate(history) for j,b in enumerate(history)):continue
queue=[];ok=True
for i in order:
operation,start,end,value=history[i]
if operation=='put':queue.append(value)
elif not queue or queue.pop(0)!=value:ok=False;break
if ok:return order
return None
h=[('put',0,3,1),('put',1,2,2),('get',4,5,1)]
assert legal(h) is not None
bad=h[:2]+[('get',4,5,3)]
assert legal(bad) is None
print('legal order=',legal(h),'impossible returned value rejected')
print('finite completed histories, nonempty get specification only')
Reject impossible returns and forbidden orderings
A get returning three is impossible in the example because only one and two were inserted. Another failure is a first get returning two after a nonoverlapping put-one followed by put-two: the value exists, but FIFO requires one first. Membership checking is weaker than validating the object's sequential behavior.
A stack would instead have a different valid removal order. Define empty removal, duplicate values, bounded capacity and failed insertion before checking histories. The current checker does not implement every such operation. Feeding unsupported behavior into a narrow model and receiving no candidate is not automatically an implementation defect. A meaningful counterexample requires the model's input domain and the object's promised specification to agree.
Do not generalize one finite history into a universal proof
Implementation reasoning must cover successful, failed and retried paths. A successful CAS, an empty result and an operation helped by another thread may need different linearization arguments. The relevant effect is not always one fixed line executed by the calling thread. History checking is a small counterexample-search aid for developing that argument, not a replacement for it.
Permutation enumeration grows factorially and is unsuitable for arbitrary large production logs. Larger tools need pruning, partial-order reasoning or state reuse. Exhausting a time budget is also different from exhausting all candidates. Distinguish a found explanation, a completed search proving none within the model, and an incomplete search. The result label must report which of those events actually occurred.
Separate correctness from progress and lifetime
A lock-based queue may be linearizable while every contender waits behind a paused lock holder. Linearizability concerns return values and operation order; lock-free and wait-free progress properties ask different questions. Safe memory reclamation is another requirement. Correct returned values alone do not exclude deadlock, starvation or use-after-free.
Comparison tables should separate sequential specification, ordering, progress, lifetime and measured performance. A fast benchmark cannot establish linearizability. When connecting to distributed read/write guarantees, align the object and invocation/response boundary first. The same term can apply to different interfaces, but a memory object, database operation and complete application request do not automatically share the same guarantee scope.
Identify operations even when their values match
Two puts can both insert value one, so a get returning one does not reveal which invocation supplied it. A value-sequence specification can legitimately accept several candidate explanations. If the requirement also concerns per-request exactly-once effects or response matching, retain operation identities and invocation/response association. Equal values are not identical operations.
Define where timestamps are recorded: around a local function or around a network call gives different intervals. Multi-host clocks add uncertainty that can incorrectly impose nonoverlap constraints. The supplied integer times are an exact model order, not unqualified clock readings. Before checking a real trace, align instrumentation and identity with the interface specification. Validating the captured history is necessary because a perfect order search can still answer the wrong question when its input intervals do not describe the promised operations.
Retain the number of checked operations and the sequential specification beside a successful enumeration. Adding pending operations or empty-queue removal requires extending the history model and the specification first. A result for the current completed, nonempty-removal scope cannot silently decide those new cases. This is a boundary of the checker rather than a failure of the definition.
Turn a candidate order into an inspectable explanation
Translate a returned order such as zero, one, two back into operations and intermediate queue states: empty, then [1], then [1,2], then [2] after returning one. This shows not only matching results but also the state passed to the next operation. A candidate identifier becomes evidence a reader can check manually rather than an opaque success label.
For rejection, identify the real-time constraint fixing the order and the return value violating the sequential specification. A short exhaustive history supports that explanation; an interrupted large search does not support the same conclusion. Rechecking a regression should preserve initial state, operation set and specification. When reducing a counterexample, ensure that removing events did not remove necessary earlier effects and change the question. The quality of the explanation matters alongside the checker result.
Exercise: linearize two contrasting histories
For overlapping put-one at zero–three, put-two at one–two and get-one at four–five, the sequential order put-one, put-two, get-one works. Put-two returning first does not prohibit that order because the puts overlap. For nonoverlapping put-one at zero–one, put-two at two–three and get-two at four–five, FIFO has no valid explanation: real time fixes one before two and no intervening removal skips one.
A pending get is outside this checker's completed-history scope. A general extension must handle pending operations according to the definition rather than inventing an observed response. Explain specification, real-time constraints, candidate order and search completion separately. Those pieces make finite-history analysis a sound stepping stone toward a broader concurrent implementation argument.