Causality and Happen-before relation

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

• \(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\) 之间不存在因果关系。

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\)。在分布式系统中，网络上的消息虽然不同于光束，但原理非常相似。