[Paper] Pending Conflicts Make Progress Impossible

Source: arXiv - 2602.04013v1

Overview

The paper investigates how commutativity—the fact that some operations can be reordered without affecting the final state—affects progress guarantees for linearizable shared objects. The authors propose a new progress condition, conflict‑obstruction‑freedom (COF), which promises that an operation will finish as long as it only runs into step contention with commuting operations. They then prove that, despite its appealing intuition, COF cannot be realized for universal constructions in the classic asynchronous read‑write shared‑memory model.

Key Contributions

• Introduces Conflict‑Obstruction‑Freedom (COF): a progress condition that relaxes obstruction‑freedom by allowing contention with commuting operations while still guaranteeing completion when only conflicting (non‑commuting) operations are present.
• Formalizes “conflict‑aware” progress: provides precise definitions of conflicting vs. commuting operations in the context of linearizable objects.
• Impossibility proof: shows that any universal construction that satisfies COF cannot be implemented using only asynchronous read‑write registers.
• Theoretical insight: demonstrates that merely invoking a conflicting operation incurs an unavoidable synchronization cost, even if the operation never actually executes.

Methodology

1. Model & Definitions

• The authors work in the standard asynchronous shared‑memory model with processes communicating via atomic read/write registers.
• Commuting operations are defined as those whose effects can be swapped without changing the abstract state; conflicting operations are the opposite.
• COF is defined formally: a process p’s operation completes if p runs long enough without step contention from any conflicting operation (step contention from commuting ops is ignored).

2. Universal Construction Framework

• They consider a generic “universal construction” that can implement any linearizable object using a shared‑memory base.
• The construction is assumed to be conflict‑aware: it can detect whether a concurrent operation conflicts with the current one.

3. Impossibility Argument

• Using a reduction to the classic consensus impossibility, they construct an execution where two processes invoke conflicting operations that never actually perform any steps on the object but still block each other under COF.
• By carefully interleaving reads and writes, they show that any COF‑compliant universal construction would solve consensus in a wait‑free manner, contradicting the known impossibility result for read/write memory.

Results & Findings

• COF is strictly stronger than obstruction‑freedom (it allows more parallelism) but strictly weaker than wait‑freedom (it still tolerates some contention).
• Universal constructions cannot satisfy COF in the pure read/write model; any attempt to do so would implicitly provide a wait‑free consensus solution, which is impossible.
• Pending conflicts are costly: even if a conflicting operation is only pending (i.e., has been invoked but not yet taken steps), it can block progress of other operations under COF.

Practical Implications

• Design of concurrent libraries: Developers cannot rely on COF to guarantee progress for generic lock‑free data structures built solely on read/write registers. Additional synchronization primitives (e.g., compare‑and‑swap, fetch‑and‑add) are required to bypass the impossibility.
• Optimizing commutative workloads: While COF itself is unattainable universally, the insight that commuting operations need not block each other can guide the design of specialized data structures (e.g., CRDTs, concurrent counters) that explicitly separate commuting from conflicting paths.
• Debugging and performance tuning: Understanding that merely invoking a conflicting operation introduces hidden synchronization overhead can help engineers spot unexpected stalls in high‑contention systems.
• Language/runtime support: The result suggests that runtime systems aiming for “conflict‑aware” progress should expose low‑level primitives (like LL/SC) or provide built‑in conflict detection mechanisms beyond plain reads/writes.

Limitations & Future Work

• Model restrictions: The impossibility holds only for the asynchronous read/write memory model. It does not rule out COF implementations that use stronger primitives (e.g., atomic RMW, transactional memory).
• Scope to universal constructions: The proof targets universal constructions; specialized objects with limited operation sets might still achieve COF.
• Future directions:
  • Explore COF feasibility under richer base objects (e.g., fetch‑and‑add, compare‑and‑swap).
  • Identify concrete object families (e.g., commutative counters, sets) where COF can be realized efficiently.
  • Develop practical conflict‑detection APIs that let developers explicitly separate commuting and conflicting paths, mitigating the hidden cost of pending conflicts.

Authors

• Petr Kuznetsov
• Pierre Sutra
• Guillermo Toyos-Marfurt

Paper Information

• arXiv ID: 2602.04013v1
• Categories: cs.DC
• Published: February 3, 2026
• PDF: Download PDF