Search papers, labs, and topics across Lattice.
This paper builds on the work of Gilbert and Golab to formally prove the relativistic linearizability of a replicated state machine and variations of the ABD read/write register construction. By utilizing their theoretical tools, the authors establish a stronger form of relativistic linearizability than previously conjectured, addressing gaps in the existing literature. This advancement is significant as it provides a rigorous foundation for understanding the behavior of distributed systems under relativistic conditions, which are increasingly relevant in modern computing environments.
Relativistic linearizability can be rigorously established for key distributed algorithms, revealing deeper insights into their behavior under the constraints of relativity.
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.
