On Interplanetary and Relativistic Distributed Computing

Interplanetary distributed systems, such as the Interplanetary Internet, and the Global Positioning System (GPS) are subject to the effects of Einstein's theory of relativity. In this paper, we study relativistic distributed systems, which are subject to the relativity of simultaneity. We formulate a unified computational model for relativistic and classical distributed systems and study the relationship between properties of distributed algorithms deployed on the two types of systems. Classical executions are totally ordered in time, whereas the steps of a relativistic execution are only partially ordered by the relation of relativistic causality. We relate these two physics-dependent execution types through a third—purely mathematical—notion of a computational execution, which partially orders steps by the relation of computational causality. We relate relativistic, classical, and computational executions of distributed algorithms through a central theorem, which states that the following are equivalent for any distributed algorithm A: (1) A satisfies a property P classically; (2) every relativistic execution of A satisfies P in the reference frame of every observer; and (3) every total ordering of every computational execution of A satisfies P. As a direct consequence, we prove the equivalence of the standard, relativistic, and computational formulations of linearizability. Our results show that a host of algorithms originally designed for classical distributed systems will behave consistently when deployed in relativistic, interplanetary distributed systems.