Relationship between concurrency and relativity

  • 1
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

The first time I realized that concurrency and relativity is related to each other was when reading the book SICP. It mentioned that

The basic phenomenon here is that synchronizing different processes, establishing shared state, or imposing an order on events requires communication among the processes. In essence, any notion of time in concurrency control must be intimately tied to communication. It is intriguing that a similar connection between time and communication also arises in the Theory of Relativity, where the speed of light (the fastest signal that can be used to synchronize events) is a fundamental constant relating time and space. The complexities we encounter in dealing with time and state in our computational models may in fact mirror a fundamental complexity of the physical universe.

For concurrency, the basic problem is synchronization, that is, we need to know which event happens first. If we can't get such a relationship, we say that the events happen concurrently.

Let's take amazon's dynamo as an example.

First, we execute put key1 value1 on server1. Before this update is synchronized to server2, we execute put key1 value2 on server2. After the above two operations, we need to achieve eventual consistency by synchronizing the value associated with key1. Since we don't have a causal relationship between the two update operations, we have no idea which value is the final value for key1.

You can think of this as space-like events in relativity theory.

The spacetime intervals is defined as:

$$
s^{2} = \Delta r^{2} - c^{2} \Delta t^{2}.
$$

where $c$ is speed of light.

Space-like events have a positive spacetime interval, that is


c^{2} \Delta t^{2} < \Delta r^{2} \\ s^{2} > 0

The above equation means, for space-like events, it's impossible to get a causal relationship by crossing the spatial distance at the speed of light.

For example, given a reference frame, Jack rolled a dice at coordinate $(x_1,x_2,x_3,t_1)$ while Sam rolled a dice at coordinate $(y_1,y_2,y_3,t_2)$. Then

\Delta t^{2} = (t_2-t_1)^2 \\
\Delta r^{2} = \sum_{i=1}^{3} (x_i - y_i) ^2

Jack and Sam agreed that when rolling the dice, they would also send a message to each other at the same time. If someone received the message before rolling the dice, he would know the other people rolled the dice first.

If $c \Delta t^2 < \Delta r^2 $, then even if Jack and Sam could communicate with each other at speed of light, they couldn't get a causal relationship for the events since both of them would receive the message after rolling the dice.