How Live Can a Transactional Memory Be

Rachid GuerraouiInfoscience 2009

Introduction

Transactional Memory (TM) simplifies concurrent programming by allowing blocks of code to execute with the appearance of atomicity. While significant research has focused on the safety of TMs—ensuring that transactions do not observe inconsistent states (e.g., opacity)—the question of liveness is equally critical. In real-world asynchronous systems, processes may crash, or "zombie transactions" may enter infinite loops. This paper investigates the fundamental theoretical limits of liveness: what is the strongest progress guarantee a TM can provide in such an environment?

Defining the Liveness Hierarchy

To analyze these limits, the authors establish a formal framework that maps TM progress to classical distributed computing properties:

  1. Total Progress (Wait-freedom): Every correct transaction eventually commits, regardless of the behavior of other transactions.
  2. Global Progress (Lock-freedom): If there are pending correct transactions, at least one is guaranteed to eventually commit.
  3. Solo Progress (Obstruction-freedom): A transaction is guaranteed to commit if it eventually executes in isolation for a sufficient period.

The Impossibility of Wait-Freedom

A central contribution of this work is the proof that Total Progress (wait-freedom) is impossible in asynchronous systems where processes can crash. The authors identify what they call the "Black Box Fallacy": the mistaken assumption that transactions can be treated as single atomic operations on shared objects.

In reality, transactions are not black boxes; the results of intermediate operations are visible to the application before a commit occurs. Using a property termed $(n-1)$-prioritization, the authors demonstrate that if a TM attempts to guarantee progress for too many concurrent transactions, it can be forced into a state that violates safety (specifically, the property of opacity). Theorems 8 and 11 formally prove that any liveness property stronger than Global Progress cannot be implemented in an asynchronous system with crashes.

Zombies and Crashes: A Functional Equivalence

The paper also addresses "zombie transactions"—those that perform an infinite number of operations without ever attempting to commit. A common concern in TM design is whether these zombies pose a unique threat to system liveness compared to simple process crashes.

The authors prove that zombies are precisely equivalent to crashes regarding their impact on liveness. They provide a transformation algorithm that can take a TM designed for a crash-free system (but capable of handling zombies) and adapt it to handle crashes by replicating the TM state across processes. This equivalence simplifies the theoretical landscape: if a TM can handle one, it can be transformed to handle the other.

The Liveness Ceiling

The research concludes that Global Progress is the strongest achievable liveness property in an asynchronous system with crashes. This finding has significant implications for existing TM implementations. For instance, the authors identify that certain existing implementations, such as Object-based Software Transactional Memory (OSTM), already provide Global Progress. This makes such implementations theoretically optimal from a liveness perspective.

Conclusion and Future Directions

While this paper establishes a clear "ceiling" for TM liveness, several avenues for future research remain:

  • Timing Assumptions: The current results are bound to asynchronous models. Exploring partially synchronous models might reveal higher liveness bounds where timing assumptions can be made.
  • Safety vs. Liveness Trade-offs: The proofs assume the maintenance of "opacity." Relaxing this safety requirement might allow for stronger progress guarantees.
  • Efficiency Costs: While Global Progress is possible, the overhead required to reach this ceiling—in terms of time and space complexity—remains to be fully quantified compared to weaker guarantees like Solo Progress.

By formalizing the relationship between crashes, zombies, and progress, this work provides a definitive map of the liveness landscape for Transactional Memory, proving that while we cannot guarantee every transaction succeeds, we can ensure the system as a whole always moves forward.

Summary updated

Abstract

This paper asks how much liveness a transactional memory (TM) implementation can guarantee. We first devise a formal framework for reasoning about liveness properties of TMs. Then, we prove that the strongest liveness property that a TM can ensure in an asynchronous system with transaction crashes is a property that we call "global progress". This property is analogous to lock-freedom for shared-memory objects and is indeed guaranteed by certain TM implementations, e.g., OSTM. We also prove that the presence of zombie transactions, which perform infinitely many operations but never attempt to commit, does not impact our result. In fact, we show that zombie transactions are, in a precise sense, equivalent to crashed transactions.
BibTeX
@inproceedings{guerraoui2009how,
  author = {Rachid Guerraoui},
  title = {{How Live Can a Transactional Memory Be}},
  booktitle = {Infoscience},
  year = {2009},
}
Figure