The Happens-before relation
An event is something happening at one node (sending or receiving a message, or a local execution step).
event \(a\) happens before event \(b\), written \(a \rightarrow b\).
那么在分布式，有三种情况，满足其中一条，则 \(a\) 是发生在 \(b\) 之前：
-
\(a\) 和 \(b\) 发生在相同节点，并且按照本地节点的执行顺序，\(a\) 发生在 \(b\) 之前。
-
事件 \(a\) 是发送消息 \(m\)，事件 \(b\) 是接收相同的消息 \(m\)（假定发送的消息都是唯一的）。
-
有这么一个时间 \(c\) 满足，\(a \rightarrow c\) 且 \(c \rightarrow b\)。
happens-before relation 是局部的顺序：有可能存在既不满足 \(a \rightarrow b\) 也不满足 \(b \rightarrow a\)，这样 \(a\) 和 \(b\) 就是并行的，写作 a || b。
Happen-before relation example
Figure 1: happens-before-example
- \(a \rightarrow b\), \(c \rightarrow d\), and \(e \rightarrow f\) due to process order
- \(b \rightarrow c\) and \(d \rightarrow f\) due to messages \(m_{1}\) and \(m_{2}\)
- \(a \rightarrow c\), \(a \rightarrow d\), \(a \rightarrow f\), \(b \rightarrow d\), \(b \rightarrow f\), and \(c \rightarrow f\) due to transitivity
- \(a || e\), \(b || e\), \(c || e\), and \(d || e\)
Causality
Happens-before relation 和 Causality 在分布式系统中联系非常紧密
- 当 \(a \rightarrow b\), 那么 \(a\) 可能是 \(b\) 的因。
- 当 \(a || b\), \(a\) 和 \(b\) 之间不存在因果关系。
Figure 2: causality
Let \(\prec\) be a strict total order on events.
如果 \((a \rightarrow b) \Rightarrow (a \prec b)\) 符号 \(\prec\) 就是所谓的因果顺序。
因果关系的概念是从物理学中借鉴的，信息的传播速度不可能超过光速。因此如果事件 \(a\) 和事件 \(b\) 在空间上相距很远，但是在时间上相距很近，那么从事件 \(a\) 发出的信号不可能在事件 \(b\) 之前到达 \(b\) 的位置，反之亦然。因此 \(a\) 和 \(b\) 是肯定没有因果关系的。
一个在空间上离 \(a\) 很近，时间上距离 \(a\) 很远的事件 \(c\)，将在 \(a\) 的光锥内，也就是说 \(a\) 的信号有可能到达 \(c\)，因此 \(a\) 可能影响 \(c\)。在分布式系统中，网络上的消息虽然不同于光束，但原理非常相似。