Analyzing Linearizability in Relativistic Distributed Systems
2026-06-29 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors discuss a problem in distributed systems where time doesn't always flow the same way for different parts of the system, due to effects like relativity. Gilbert and Golab made a new definition called relativistic linearizability to handle this, but they didn't fully prove it for all common algorithms. This paper shows how their methods can be used to prove relativistic linearizability for certain distributed algorithms, improving on previous work by Jayanti. The authors focus on ensuring these systems behave correctly even when events can't be globally ordered by time.
Einstein's relativitytime dilationdistributed systemslinearizabilityrelativistic linearizabilityreplicated state machineABD algorithmasynchronous algorithmsevent ordering
Authors
Kahbod Aeini, Wojciech Golab
Abstract
Einstein's theory of relativity correctly predicted that time is relative, and subject to both kinematic and gravitational dilation. Therefore, executions of distributed systems cannot always be modeled as sequences of events totally ordered according to wall clock time. To address this fundamental problem, Gilbert and Golab formulated a generalization of Herlihy and Wing's linearizability property for shared objects, which they called \emph{relativistic linearizability}, and introduced a collection of theoretical tools to facilitate rigorous analysis. While they conjectured that several widely-studied classically linearizable algorithms are also relativistically linearizable, their work stopped short of presenting formal proofs of correctness, as pointed out recently by Jayanti. In this paper, we explain how Gilbert and Golab's techniques can be used to establish relativistic linearizability for a replicated state machine, as well as variations of the widely studied read/write register construction of Attiya, Bar-Noy and Dolev (ABD). Our results establish a stronger form of relativistic linearizability than Jayanti's central theorem for these asynchronous algorithms.