Stabilizing Logs for Eventually Linearizable Shared Objects

Abstract

Eventual linearizability allows a finite prefix of an execution to be inconsistent but demands linearizable behavior thereafter, making one-shot objects such as consensus easy while long-lived objects such as fetch-and-increment stay hard. We develop a Herlihy-style hierarchy for this setting, built on the observation that the right universal primitive is not consensus but a long-lived operation log. Our main tool is a \emph{stabilizing log}: we prove that an eventually linearizable $n$-process log is universal for wait-free eventually linearizable implementations of deterministic $n$-process objects, and we show that every eventually linearizable log implementation from linearizable base objects has a reachable configuration from which removing one finite prefix from every response yields a fully linearizable log. The removed prefix is the entire post-cut log state rather than only the cut operation's response, which is what makes the quotient well defined for fetch-and-cons. Together these results give an exact hierarchy: for state-robust types the largest $n$ implementable from linearizable type-$T$ objects is Herlihy's consensus number $c(T)$, and under the weaker eventual-base interpretation we obtain $\elog(T)\le c(T)$. We also characterize when the hierarchy number is a complete reduction criterion: a finite-level target type $S$ admits an exact implementability threshold $T\Rightarrow S\iff\elog(T)\ge\elog(S)$ if and only if $S$ is equivalent to the canonical eventual log at its own level. Finally, we prove a collapse theorem for solo-explainable one-shot types, covering consensus and test-and-set, and we give the first exact eventual-base lower bound for a long-lived primitive, $\elog(\FAA)=2$, via self-describing predecessor certificates that confine the base object's finite anomalies to a finite log prefix.

Topics & keywords