Impossibility Results for Strong Linearizability: The Difficulty of Consistent Refereeing

This paper establishes that implementing various concurrent objects with strong linearizability in lock-free or wait-free settings inherently requires a form of "consistent refereeing" that, while weaker than consensus, demands high coordination power and leads to new impossibility results for objects like window registers, interfering primitives, and stacks.

The Gist

Imagine you are running a high-stakes race where multiple runners (processes) are trying to cross a finish line, and a single referee needs to announce who won. In the world of computer science, this is called concurrent programming. The goal is to make sure that even if everyone runs at the same time, the system behaves as if they ran one by one, in a specific order. This is called linearizability.

However, there is a stricter, more demanding rule called strong linearizability. Think of it like this: In a normal race, if the referee makes a mistake and says "Runner A won," but then later realizes "Wait, actually Runner B was first," they can fix it. In a strongly linearizable race, once the referee makes a call, that call is final and unchangeable. No matter what happens later in the race, the referee cannot go back and change their mind. The outcome must be "locked in" the moment it is decided.

This paper asks a tough question: Can we build these "unchangeable" referees using only simple, common tools?

The Problem: The "Consistent Referee"

The authors discovered that creating a system where the referee's decision is permanent requires a level of coordination that simple tools just can't provide.

They introduced a new concept called the "Contest Object."

• The Setup: Imagine a room with many competitors and one referee. The competitors shout "I'm ready!" (compete). The referee looks around and picks the first person they heard.
• The Catch: The competitors don't need to agree on who won; they just shout. Only the referee needs to know the answer.
• The Twist: The referee's choice must be strongly linearizable. Once the referee picks a winner, that choice cannot be undone or changed by any future events.

The paper proves that while you can build a simple referee with basic tools (like reading and writing notes), you cannot build a strongly linearizable referee (one whose decision is permanent) using certain common tools like stacks (a pile of plates where you can only take the top one), window registers (a list that only remembers the last few things written), or interfering primitives (tools where actions can bump into each other).

The Analogy: The "Unchangeable Scoreboard"

Imagine a game show with a giant scoreboard.

1. The Competitors: Players press buttons to enter the game.
2. The Referee: A judge who looks at the scoreboard and announces the winner.
3. The Rule: Once the judge announces a winner, the scoreboard must be "glued" to that result. Even if the judge later sees a new button press, they cannot change the announcement.

The paper shows that if you try to build this game show using only:

• Stacks: A pile of notes where you can only read the top one.
• Window Registers: A whiteboard that only shows the last 2 or 3 notes written.
• Interfering Tools: Tools where two people writing at the same time might erase each other's work.

...you will fail. The system will inevitably reach a point where the judge thinks they have made a decision, but because the tools are too "fuzzy" or "short-term," the judge might later be forced to change their mind to stay consistent with the rules. This violates the "strong" rule.

The Two Types of Races

The authors studied two versions of this problem:

1. The One-Shot Race (Lock-Free):

   • Scenario: Everyone runs once. The referee picks a winner.
   • The Result: Even if we allow the system to be "lock-free" (meaning as long as someone is running, the race will eventually finish), you still can't build a permanent referee using stacks or simple windows. The tools just aren't powerful enough to "lock in" the decision.

2. The Long-Lived Race (Wait-Free):

   • Scenario: Competitors can run the race over and over again. The referee needs to count how many times everyone has run so far.
   • The Result: This is even harder. The paper proves that even with slightly better tools (like "window registers" that remember a few past actions), you cannot build a referee that permanently locks in the count for everyone. The system will eventually get confused about the order of events.

Why Does This Matter?

In computer science, we often try to build complex systems (like databases or traffic control) by combining simple, cheap building blocks. We hope that if we have enough of them, we can build anything.

This paper says: "Not quite."
It reveals a hidden cost to strong linearizability. To make a decision that can never be changed, you need "super-tools" (like the powerful compare-and-swap instruction found in modern processors). You cannot fake it with simple tools like stacks or basic memory registers.

The Takeaway

The paper uses a clever "valency" argument (a fancy way of saying "looking at all possible future outcomes") to show that consistent refereeing is a superpower.

• If you want a referee who can never change their mind, you need a referee with a very strong memory and coordination ability.
• If you only have weak, simple tools, the referee will eventually be forced to "flip-flop" or change their mind to keep the system consistent, which breaks the "strong" rule.

In short: Strong linearizability is a very high bar. You can't clear it with just a few simple sticks and stones; you need a heavy-duty hammer.

Technical Summary

Technical Summary: Impossibility Results for Strong Linearizability

Problem Statement

The paper investigates the fundamental relationship between agreement tasks (such as consensus) and the implementation of concurrent objects under the strong linearizability consistency condition. While linearizability ensures that operations appear to occur atomically, it fails to preserve certain hyperproperties (e.g., security properties and probability distributions) when composed with randomized or information-sensitive programs. Strong linearizability addresses this by requiring that the linearization of an execution be defined incrementally based on prefixes, ensuring that the linearization of a prefix remains a prefix of the linearization of any extension.

Despite its utility, constructing strongly linearizable implementations from basic primitives is challenging. Prior impossibility results have shown that common objects (e.g., max registers, snapshots, queues) cannot be implemented in a strongly linearizable manner from non-universal primitives (like read/write, test&set, swap), even when linearizable implementations exist. However, existing proofs often rely on ad-hoc valency arguments or reductions from agreement tasks that assume the underlying primitives are readable. The paper aims to elucidate the specific coordination constraints imposed by strong linearizability, particularly for lock-free and wait-free progress conditions, without relying on readability assumptions.

Methodology

The authors introduce two novel abstract objects, termed contest objects, to characterize the coordination power required for strong linearizability:

1. The One-Shot Contest Object:

   • Definition: A set of competitor processes ($p_1, \dots, p_{n-1}$) invoke compete(), and a distinguished referee process ($p_0$) invokes decide(). The compete() operation always returns true. The decide() operation returns the index of the first competitor to execute compete(), or false if none occurred.
   • Properties: This object is strictly weaker than consensus. It admits a wait-free, decisively linearizable implementation using only read/write registers. However, the paper proves it cannot be implemented in a lock-free, strongly linearizable manner from interfering primitives, $(n-2)$-window registers, and atomic stacks.

2. The Long-Lived Contest Object:

   • Definition: Similar to the one-shot version, but competitors can invoke compete() an unbounded number of times. The referee's decide() operation returns an integer $x$ such that every competitor has participated no more than $x$ times so far.
   • Properties: Like the one-shot version, it is strictly weaker than consensus and admits a wait-free, decisively linearizable implementation from read/write registers. The paper proves it cannot be implemented in a wait-free, strongly linearizable manner from read/write registers alone (for $n \ge 3$), nor from $w$-window registers and test&set objects under specific constraints.

Proof Technique:
The proofs utilize valency arguments (specifically group valency) rather than reductions from consensus. The core logic relies on the property of strong linearizability: once a "competition" is resolved (i.e., a linearization point is fixed), the outcome cannot be revised in any future extension of the execution. The authors construct "critical configurations" where the system is multivalent (capable of producing different outcomes) but any single step by a process forces the system into a univalent state. By analyzing the indistinguishability of configurations to processes (the referee and other competitors) when accessing base objects (registers, stacks, test&set), the authors derive contradictions, showing that consistent refereeing of these competitions requires coordination power exceeding that of the available primitives.

Key Contributions and Results

1. Characterization of Coordination Constraints

The paper identifies that lock-free and wait-free strongly linearizable implementations of several concurrent objects entail a form of agreement that is weaker than consensus but impossible to implement strongly linearizably with non-universal primitives. This form of agreement requires a distinguished process (referee) to resolve a competition involving all other processes, with the constraint that the outcome is irrevocable once resolved.

2. Impossibility for Lock-Free Implementations

• Theorem 5: There is no lock-free, strongly linearizable implementation of a contest object from interfering primitives, $(n-2)$-window registers, and atomic stacks for $n \ge 4$.
• Corollary 12: Consequently, there is no lock-free, strongly linearizable implementation of a queue from interfering primitives, $(n-2)$-window registers, and atomic stacks.
• Significance: This result extends previous impossibility results for queues to include atomic stacks and window registers. Crucially, the proof does not rely on the assumption that base objects are readable, addressing a gap in prior reduction-based proofs.

3. Impossibility for Wait-Free Implementations

• Theorem 25: There is no wait-free, strongly linearizable implementation of a long-lived contest object from read/write registers for $n \ge 3$.
• Theorem 30: This impossibility extends to implementations using $w$-window registers and test&set objects for $n \ge 4$ and $3w \le n$.
• Corollaries 26 & 31: These impossibility results apply to counters, snapshots, max registers, fetch&increment, and fetch&add. Specifically, while wait-free linearizable implementations of fetch&increment and fetch&add exist from read/write and test&set, they do not exist if strong linearizability is required.

4. Positive Results (Upper Bounds)

To establish that the contest objects are strictly weaker than consensus, the paper provides positive constructions:

• Theorem 3: A wait-free, decisively linearizable contest object can be implemented from read/write registers.
• Theorem 4: A wait-free, strongly linearizable contest object can be implemented from $(n-1)$-window registers.
• Lemma 14: Wait-free, strongly linearizable implementations of the long-lived contest object can be derived from strongly linearizable counters, snapshots, max registers, fetch&increment, or fetch&add.

Significance and Claims

The paper claims that the difficulty of achieving strong linearizability for certain objects stems from the requirement for consistent refereeing. Even when the agreement task does not require all processes to agree on a value (unlike consensus), the requirement that a single distinguished process's observation of a competition outcome be irrevocable imposes high coordination power.

The authors emphasize that their results:

1. Generalize Impossibility: They cover a broader class of primitives (including stacks and window registers) and remove the "readability" assumption required by previous reduction-based proofs.
2. Clarify the Gap: They demonstrate that strong linearizability enforces an "irrevocable resolution of concurrency" that is distinct from standard agreement tasks.
3. Limitations of Primitives: They show that even powerful non-universal primitives (like stacks and test&set) are insufficient for lock-free or wait-free strongly linearizable implementations of fundamental objects like queues, counters, and snapshots.

The paper concludes that while contest objects are weaker than consensus, they serve as effective building blocks for proving impossibility results in the context of strong linearizability, highlighting that the "consistent refereeing" of concurrent competitions is the primary bottleneck.