💻 computer science

Towards Proving Liveness on Weak Memory (Extended Version)

This paper introduces the first proof calculus for reasoning about liveness properties in concurrent programs under weak memory models, extending Manna and Pnueli's response rules with memory fairness and weak memory ranking functions to formally prove starvation freedom for the Ticket lock algorithm.

Original authors: Lara Bargmann, Heike Wehrheim

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lara Bargmann, Heike Wehrheim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive orchestra where every musician is playing a different instrument, but they are all wearing noise-canceling headphones that only let them hear a few seconds of the music at a time. This is what happens in modern computer processors when they run multiple programs (threads) at once.

In the "old days" of computing, we assumed everyone heard the music perfectly in sync (this is called Sequential Consistency). If the violinist played a note, the drummer heard it instantly. But modern computers are faster and more complex; they use Weak Memory Models. Here, the drummer might hear the violinist's note a split second later, or even hear an old note while the violinist has already moved on.

This paper tackles a very specific headache: How do we prove that this chaotic orchestra will eventually finish the song, rather than getting stuck in an infinite loop of confusion?

Here is the breakdown of the paper's solution, using simple analogies:

1. The Problem: The "Stuck in Traffic" Scenario

Most computer scientists have been very good at proving Safety: "Will the orchestra crash into each other?" (e.g., "Will two drummers try to play the same drum at the same time?"). They have tools to say, "No, they won't crash."

But they haven't been good at proving Liveness: "Will the orchestra ever finish the song?"
In a weak memory world, a thread (musician) might be waiting for a signal that was sent, but because of the "noise-canceling headphones" (weak memory), they haven't seen it yet. If the system isn't fair, that musician might wait forever, even though the signal was sent. This is called Starvation.

2. The Solution: A New Rulebook (The Proof Calculus)

The authors, Lara Bargmann and Heike Wehrheim, have created the first "rulebook" (a proof calculus) specifically designed to prove that these programs will eventually finish, even with the confusing memory delays.

They built this rulebook on top of an existing famous logic system (Manna and Pnueli's rules), but they had to add two special ingredients:

Ingredient A: The "Memory Fairness" Clause

Imagine a traffic light. In a normal world, if you are waiting at a red light, eventually it turns green. In this computer world, the "traffic light" is the memory system.
The authors added a rule that says: "If a thread is waiting for a memory update, the system must eventually let that thread see the update."
They call this Memory Fairness. It ensures that the "noise-canceling headphones" don't stay stuck on a stale channel forever. The system must eventually "flush" the new information to the waiting thread.

Ingredient B: The "Progress Scorecard" (Ranking Functions)

To prove the song will end, you need a way to measure progress. Imagine a hiker trying to reach a mountain peak.

Old way: "I am getting closer." (Vague).
New way: The authors use a Ranking Function. This is like a scorecard that counts down.
- Score: (Steps taken by Thread A) + (How close Thread B is to seeing the update) + (How many steps until the loop ends).
- Every time a helpful action happens (like a memory update or a thread moving forward), the score goes down.
- Since the score can't go below zero, the process must stop eventually.

3. The Magic Tool: "Potentials" and "Piccolo"

The tricky part is that in a weak memory world, Thread A might see the world differently than Thread B. Thread A might see "Free = 0" while Thread B sees "Free = 1". How do you write a rule that works for both?

The authors use a logic system called Piccolo.

The Analogy: Imagine a "Potential Store" is like a time-lapse photo album.
- Instead of just seeing the current state of a variable, the photo album shows a sequence: "It was 0, then it became 1, then it became 2."
- Thread A might be looking at the first photo (seeing 0). Thread B is looking at the last photo (seeing 2).
- The Piccolo logic allows the proof to say: "Thread A is currently looking at the '0' photo, but we know the '1' photo exists in the album, and eventually, Thread A will flip the page to see it."

This allows them to write rules that are valid for any memory model that respects these "photo album" rules, rather than having to write a new rulebook for every single type of computer chip.

4. The Test Drive: The Ticket Lock

To prove their method works, they tested it on a famous algorithm called the Ticket Lock.

The Scenario: Imagine a bakery where customers take a number (a ticket) and wait for their number to be called.
The Challenge: In a weak memory world, Customer A might take a ticket, but Customer B (the baker) might not see that ticket immediately. Customer A might spin in a circle waiting, thinking the baker is ignoring them.
The Result: Using their new rulebook, the authors proved that no matter how many customers there are, and no matter how "weak" the memory is, everyone will eventually get their turn. They proved the "Ticket Lock" is Starvation-Free.

Summary

This paper is like inventing a new set of traffic laws and a new GPS system for a city where cars sometimes drive on different timelines.

The Problem: Cars (threads) might get stuck waiting for a signal that exists but hasn't reached them yet.
The Fix: A new logic system that tracks "time-lapse photos" of the road (Potentials) and ensures the traffic lights (Memory Fairness) eventually turn green for everyone.
The Proof: They proved that with these new rules, a busy intersection (the Ticket Lock) will never get stuck in an infinite traffic jam.

This is a huge step forward because it moves computer verification from just "making sure we don't crash" to "making sure we actually finish the job."

1. Problem Statement

Verifying concurrent programs is inherently complex due to fine-grained interleavings. This complexity is exacerbated by weak memory models (e.g., Release-Acquire, Strong Coherence), which allow hardware and compilers to reorder memory operations, deviating from Sequential Consistency (SC).

The Gap: Existing verification techniques for weak memory models predominantly focus on safety properties (e.g., mutual exclusion, absence of data races).
The Challenge: Proving liveness properties (e.g., termination, starvation freedom) on weak memory is significantly harder. Liveness proofs require reasoning about infinite executions and fairness. In weak memory, threads may observe stale values of shared variables, making standard invariants (like "if signal is set, lock is free") ill-defined or unstable. Furthermore, existing fairness definitions often ignore internal memory model steps (like propagation or flushing) which are crucial for ensuring threads eventually see updated values.

2. Methodology

The authors propose a generic proof calculus for reasoning about liveness on weak memory models. Their approach combines three main components:

A. Extension of Manna and Pnueli's Rules

The core of the methodology adapts Manna and Pnueli's (MP) Rule WELL-J (Well-founded response under Justice).

Standard MP Rule: Uses ranking functions to measure progress toward a target state and relies on "helpful transitions" that are guaranteed to be taken under weak fairness.
Adaptation: The authors extend this rule to handle weak memory by:
1. Incorporating memory fairness: Internal memory model transitions (e.g., propagation of writes) are treated as "helpful transitions" that must be taken fairly.
2. Defining ranking functions over weak memory states: Instead of just program counters, the ranking functions measure the "distance" a thread is from seeing the most recent value of a shared variable.

B. The Piccolo Logic and Potentials

To reason about weak memory states generically (valid across multiple models), the authors utilize the Piccolo logic based on potentials.

Potentials: A potential store represents a thread's view of memory as a list of historical writes (values, timestamps, thread IDs). This captures the phenomenon where a thread might see a sequence of values (stale to recent) rather than a single current value.
Logic Extensions: The authors extend Piccolo with specific constructs for liveness:
- $\vec{x}$ (Current Value): Access to the most recent value in the potential list.
- $dist(\tau, x)$ : A function measuring the number of steps (writes) a thread $\tau$ is away from seeing the latest value of $x$ .
- $C(x)$ : A predicate indicating if a location is "covered" (relevant for Read-Modify-Write operations).
Stability: Unlike safety proofs where assertions must be stable against memory steps, liveness proofs explicitly rely on assertions changing (e.g., $dist$ decreasing) due to internal memory transitions.

C. Generic Soundness via Lifting

Instead of defining rules for a single memory model, the authors define a lifting function ( $map_M$ ) that maps concrete memory model states (e.g., Release-Acquire message queues) to the abstract potential domain.

Soundness Conditions: A memory model is valid for the calculus if the lifting function satisfies specific "healthiness conditions," ensuring that internal memory transitions (like propagation) effectively decrease the $dist$ metric (view advancement).

3. Key Contributions

First Liveness Calculus for Weak Memory: This is the first proof calculus specifically designed to prove liveness properties (response properties) for concurrent programs under weak memory models.
Integration of Memory Fairness: The framework formally incorporates internal memory model steps (propagation, flushing) as "helpful transitions" in the fairness definition, allowing proofs to reason about how threads eventually observe updates.
Ranking Functions on Potentials: Introduction of ranking functions that operate on the "distance" to the latest memory value, enabling termination proofs even when threads initially see stale data.
Generic Validity: The approach is model-agnostic. Proofs are constructed in the Piccolo logic and are valid for any memory model where the specific proof rules are shown to be sound via the lifting function.
Case Studies:
- Program Waiting: A simple lock-release pattern. The authors prove termination under Release-Acquire (RA) and Strong Coherence (StrCOH). They demonstrate that under StrCOH, specific invariants used in RA fail, highlighting the nuance of different models.
- Ticket Lock Algorithm: A parameterized mutual exclusion algorithm. Using a parameterized version of the rule (WELL-JP), they prove starvation freedom for any number of threads under RA and StrCOH.

4. Results

Soundness: The authors prove that the extended proof rules are sound for the Release-Acquire (RA) and Strong Coherence (StrCOH) memory models. They also note that the rules hold for Sequential Consistency (SC) and Total Store Ordering (TSO).
Verification Success:
- The Ticket Lock algorithm is proven to be starvation-free on both RA and StrCOH.
- The Waiting program is proven to terminate on RA. However, the authors note a limitation: under StrCOH, the specific invariant required for the Waiting proof (relying on message ordering) does not hold, meaning the specific proof for Waiting is not valid for StrCOH, though the Ticket Lock proof is.
Formal Mapping: The paper provides the formal mapping (lifting) of RA states to potentials, demonstrating how timestamps and view updates in RA correspond to the $dist$ metric in Piccolo.

5. Significance

Bridging a Critical Gap: Prior to this work, liveness verification on weak memory was largely limited to automatic model checking or restricted to safety. This paper provides a deductive, manual verification framework for liveness.
Handling "Stale" Views: By using potentials and distance metrics, the methodology directly addresses the core difficulty of weak memory: threads seeing different values at different times. It moves beyond simple state predicates to reasoning about the history of memory updates.
Modularity: The separation of the proof calculus (Piccolo + WELL-J) from the specific memory model semantics allows researchers to verify algorithms once and apply the proof to multiple memory models, provided the soundness conditions are met.
Foundation for Future Work: The paper sets the stage for verifying more complex synchronization primitives and exploring stronger fairness notions (like compassion) in weak memory contexts.

In summary, Bargmann and Wehrheim successfully extend the classical Manna-Pnueli liveness framework to the complex domain of weak memory by leveraging the Piccolo logic and the concept of potentials, providing the first deductive method to prove starvation freedom and termination in this setting.