How will interstellar database systems look like? This problem has fascinated me ever since I read Krugman's treatise on interstellar trade theory [1]. In this article, I will attempt to share my rudimentary thoughts on how the design of interstellar database systems might differ from our terrestrial database systems. The crux of this problem is that the ordering of two spatially separated events that occur at the same time is no longer absolute, as we often take for granted, and is instead relative to the reference frame of the observer [2, 3, 4].
Consider an interstellar database system that is managing a database spread across two machines A and B -- with the former machine located on earth, and the latter placed on an interstellar vehicle that travels nearly as fast as the speed of light (c). In this scenario, as illustrated in Figure 1, the laws of motion vary depending on the acceleration of B's non-inertial reference frame. More importantly, given the cost of communication across an interstellar network, the ordering of two events might not only defined by the messages that are actually sent between the machines A and B, but also by those that could have been sent between them.
We must, therefore, first reexamine the notion of ordering of events in the context of an interstellar database system. I will later make the case for a multi-world protocol that is inspired by the many-worlds interpretation of quantum mechanics [5].
In a relativistic non-Euclidean setting, events are the fundamental elements of spacetime. An event corresponds to a unique position at a unique time in any given spacetime. Every event is, thus, represented by a spacetime point.
The separation between two points in a Euclidean space is purely spatial. However, in spacetime, the distance between two events is a function of both the spatial displacement vector ΔS and the temporal displacement vector ΔT. This separation between two events is referred to as the invariant spacetime interval, and is given by the displacement four-vector ΔD:
Spacetime intervals can be classified into three types depending on whether the interval is positive, negative, or zero. In order to establish a causal relationship between two events, enough time must pass between them so that there is no reference frame in which the two events can occur at the same time. This is feasible only when the events are separated by time-like and light-like intervals, wherein ΔD2 < 0 and ΔD2 = 0 respectively. When ΔD2 > 0, not enough time passes between these events for there to exist a causal relationship that can span the spatial distance between them at a speed less than or equal to the speed of light. Such events are considered as being separated by space-like intervals.
By computing the spacetime interval between two events, we can determine whether they can be ordered or not. With this mechanism for ordering events in a relativistic setting, the transaction manager of our interstellar DBMS can determine the ordering of transactions whose operations correspond to a set of events. We can generalize the timestamp-ordering concurrency control protocol to a spacetime-ordering protocol that ensures the isolation of concurrent interstellar transactions. For every tuple in the interstellar database, the DBMS must keep track of the spacetime points at which it was read and updated respectively with respect to a well-defined reference frame.
The spacetime-ordering protocol must handle the relativity of simultaneity [2]. Consider a scenario wherein two transactions attempt to concurrently mutate the same tuple, and these events are separated by a space-like interval. In this scenario, the transaction manager should abort one of these unorderable transactions.
In our vanilla spacetime-based protocol, there can exist atmost one valid version of a tuple at a given spacetime point. To ensure this invariant, the DBMS needs to employ a distributed atomic commitment protocol that might incur a high communication cost. A more pragmatic approach would be to relax this invariant, thereby allowing multiple versions of a tuple to co-exist at a given spacetime point.
Let's say the agent aboard the interstellar vehicle wants to create a new version T' of an existing tuple T. The DBMS should allow the agent to do so even when it is unable to communicate with the machine on earth. Let us assume that there exists a time-like interval between this update operation and the spacetime point at which T was created. Now, depending on the reference frame with respect to which an agent chooses to observe, the DBMS can either return T or T'.
In this sense, there are can exist many versions of the same tuple in different worlds. We refer to this generalization of the multi-versioned spacetime-ordering protocol as a multi-world protocol. The additional metadata that the DBMS stores to track the tuple versions is shown in Figure 2. When the interstellar vehicle eventually lands on earth, the DBMS must allow the agent to create a new world view wherein it converges its perspectives.
This article highlighted the utility of spacetime intervals in ordering events within an interstellar database system. I think that a multi-world spacetime-ordering concurrency control protocol might be a good fit for an interstellar database system.
[1] The Theory of Interstellar Trade, Paul Krugman, 1978
[2] Relativity - The Special and General Theory, Albert Einstein, 1916
[3] The Measure of Time, Henri Poincaré, 1898
[4] Time, Clocks, and the Ordering of Events in a Distributed System, Leslie Lamport, 1978
[5] The Road to Reality, Roger Penrose, 2004
Consider an interstellar database system that is managing a database spread across two machines A and B -- with the former machine located on earth, and the latter placed on an interstellar vehicle that travels nearly as fast as the speed of light (c). In this scenario, as illustrated in Figure 1, the laws of motion vary depending on the acceleration of B's non-inertial reference frame. More importantly, given the cost of communication across an interstellar network, the ordering of two events might not only defined by the messages that are actually sent between the machines A and B, but also by those that could have been sent between them.
 |
| Figure 1: Interstellar Database System - The locations of the two machines that contain a distributed database managed by an interstellar database system. |
We must, therefore, first reexamine the notion of ordering of events in the context of an interstellar database system. I will later make the case for a multi-world protocol that is inspired by the many-worlds interpretation of quantum mechanics [5].
SPACETIME INTERVALS
In a relativistic non-Euclidean setting, events are the fundamental elements of spacetime. An event corresponds to a unique position at a unique time in any given spacetime. Every event is, thus, represented by a spacetime point.
The separation between two points in a Euclidean space is purely spatial. However, in spacetime, the distance between two events is a function of both the spatial displacement vector ΔS and the temporal displacement vector ΔT. This separation between two events is referred to as the invariant spacetime interval, and is given by the displacement four-vector ΔD:
ΔD2 = ΔS2 -
c2 ΔT2
Spacetime intervals can be classified into three types depending on whether the interval is positive, negative, or zero. In order to establish a causal relationship between two events, enough time must pass between them so that there is no reference frame in which the two events can occur at the same time. This is feasible only when the events are separated by time-like and light-like intervals, wherein ΔD2 < 0 and ΔD2 = 0 respectively. When ΔD2 > 0, not enough time passes between these events for there to exist a causal relationship that can span the spatial distance between them at a speed less than or equal to the speed of light. Such events are considered as being separated by space-like intervals.
By computing the spacetime interval between two events, we can determine whether they can be ordered or not. With this mechanism for ordering events in a relativistic setting, the transaction manager of our interstellar DBMS can determine the ordering of transactions whose operations correspond to a set of events. We can generalize the timestamp-ordering concurrency control protocol to a spacetime-ordering protocol that ensures the isolation of concurrent interstellar transactions. For every tuple in the interstellar database, the DBMS must keep track of the spacetime points at which it was read and updated respectively with respect to a well-defined reference frame.
The spacetime-ordering protocol must handle the relativity of simultaneity [2]. Consider a scenario wherein two transactions attempt to concurrently mutate the same tuple, and these events are separated by a space-like interval. In this scenario, the transaction manager should abort one of these unorderable transactions.
MULTI-WORLD PROTOCOL
In our vanilla spacetime-based protocol, there can exist atmost one valid version of a tuple at a given spacetime point. To ensure this invariant, the DBMS needs to employ a distributed atomic commitment protocol that might incur a high communication cost. A more pragmatic approach would be to relax this invariant, thereby allowing multiple versions of a tuple to co-exist at a given spacetime point.
Let's say the agent aboard the interstellar vehicle wants to create a new version T' of an existing tuple T. The DBMS should allow the agent to do so even when it is unable to communicate with the machine on earth. Let us assume that there exists a time-like interval between this update operation and the spacetime point at which T was created. Now, depending on the reference frame with respect to which an agent chooses to observe, the DBMS can either return T or T'.
 |
| Figure 2: Multi-World Spacetime-Ordering Protocol - The metadata that the interstellar DBMS stores to track tuple versions. We depict four-coordinate spacetime points using integers for ease of reading. |
In this sense, there are can exist many versions of the same tuple in different worlds. We refer to this generalization of the multi-versioned spacetime-ordering protocol as a multi-world protocol. The additional metadata that the DBMS stores to track the tuple versions is shown in Figure 2. When the interstellar vehicle eventually lands on earth, the DBMS must allow the agent to create a new world view wherein it converges its perspectives.
CONCLUSION
This article highlighted the utility of spacetime intervals in ordering events within an interstellar database system. I think that a multi-world spacetime-ordering concurrency control protocol might be a good fit for an interstellar database system.
REFERENCES
[1] The Theory of Interstellar Trade, Paul Krugman, 1978
[2] Relativity - The Special and General Theory, Albert Einstein, 1916
[3] The Measure of Time, Henri Poincaré, 1898
[4] Time, Clocks, and the Ordering of Events in a Distributed System, Leslie Lamport, 1978
[5] The Road to Reality, Roger Penrose, 2004
No comments :
Post a Comment