Stabilizing Logs Solve Long-Standing Distributed Consistency Problem

Tong Che's paper tackles a fundamental challenge in distributed computing: making long-lived shared objects (like fetch-and-increment) eventually linearizable. While eventual linearizability allows a finite prefix of inconsistent behavior before stabilizing, prior work showed that long-lived objects remain hard to implement compared to one-shot objects like consensus. Che introduces the stabilizing log, a new universal primitive proven to be sufficient for wait-free eventually linearizable implementations of any deterministic n-process object. This log acts as a long-lived operation log that can be stabilized by removing a finite prefix, effectively making the quotient well-defined for operations like fetch-and-cons.

The paper builds a Herlihy-style hierarchy for eventual linearizability, showing that the consensus number of a type T (c(T)) determines its implementability from linearizable base objects. Under a weaker "eventual-base" interpretation, the hierarchy number elog(T) is at most c(T). Che also provides the first exact lower bound for a long-lived primitive: elog(FAA)=2, meaning fetch-and-add requires at least two base objects (like consensus). Additionally, a collapse theorem for solo-explainable one-shot types (covering consensus and test-and-set) simplifies the hierarchy. These results give system designers precise guidance on when weaker consistency models can achieve high performance without sacrificing correctness.