文章目录
1. 逻辑时钟的动机
1.1 基本概念
在分布式系统中物理时钟不能完美的同步
计算机时钟的主要作用 – 排序事件：
- 如果两个进程不需要交互，就没有需要同步时钟
- 这个观察导致“因果性”
1.2 因果性：
- 使用之后发生 \rightarrow 关系来排序事件：
- $a \rightarrow b$：$a$ 能够影响 $b$ 的结果
- $a || b$：
- $a$ 和 $b$ 出现在不同进程中，并不交换数据
- 其相对顺序并不重要
- happened-before 的定义
- 如果a和b位于同一进程，a 在 b 之后，则 a \rightarrow b
- 如果a和b出现在不同进程，a 是发送方，b 是对应（corresponding）的接收方，那么 a \rightarrow b
- 传递性（transitive）：如果 a \rightarrow b ,b \rightarrow c 则 a \rightarrow c
- 偏序 – 无序事件时并发的
2. 逻辑时钟
- 概念：逻辑时钟是单调（monotonically）增长的软件计数器；它不需要物理时钟；校正之只能使之增长，而不能减少
- 规则：如果 a \rightarrow b, clock(a)
3. 兰伯特（Lamport）算法，1978
3.1 算法：每个线程 P_i 有一个逻辑时钟 L_i，时钟同步算法：
- $L_i$ 被初始化为$0$；
- 更新 L_i:
- $LC1$：$L_i$ 当新的事件在$P_i$ 发生的时候增长1；
- $LC2$：当$P_i$ 发送一条消息$m$，将$t=L_i$附加到$m$上去；
- $LC3$：当$P_j$ 接收$(m,t)$时，它设置$L_j≔max{L_j,t}$，并且应用$LC1$的规则再次为事件$receive(m)$增加$L_j$；
iii.
3.2 问题：
- 相同的时间戳
- 描述：并发的事件可能有相同的时间戳
- 解决：在时钟值后追加线程ID（或者系统ID）
- 检测因果（causal）关系
- 算法：
- 如果a \rightarrow b，那么L(a)
- 如果 L(a)
- 如果a \rightarrow b，那么L(a)
- 解决：使用向量时钟法
- 算法：
4. 向量时间戳法
4.1 概念：
假设有一群人，每个都需要追踪发生于其他人的事件
解决：需要有向量时间戳
4.2 算法：每个进程 P_i 保持一个时钟 V_i ，向量有 N 维：
- 初始化：for 1 ≤ i ≤ N\ and\ 1 ≤ k ≤ N, V_i [k]≔0
- 更新 V_i:
- $VC1$：当其为 $P_i$ 进程的新事件时，设置 $V_i [i]≔V_i [i]+1$
- $VC2$：当 $P_i$ 发送消息 $m$，它将 $t=V_i$ 附加到 $m$ 上
- $VC3$：当 $P_j$ 接收到 $(m,t),for\ 1≤k≤N,it\ set\ V_j [k]≔max[{V_j [k], t[k]}]$，并运用$VC1$来增长$V_j [j]$
- 注意：V_i [j] 是一个时间戳，指示（indicating）P_i 知道发生在 P_j 至此的所有事件。
-
使用事件向量检测 → 或者 || 事件
- 规则：
- 只有每一维度都相等时，才相等，否则按照数值规则计算（此处不可能出现交叉）
- 对任何两个事件 a 或者 b：
- 当 V(a)
- 当没有 V(a)≤V(b) 也没有 V(a)≥V(b) 时，a || b
- 当 V(a)
- 规则：
- 一个时间戳向量的用法：因果排序多播
- 算法：每个组成员维持一个 N 维度时间戳向量，全都初始化为 0
- 当 P_i 多播一个消息 m，其增长 V_i [i] 并将之附加到 m 上
- 保留因果顺序
- 如果 m_1→m_2 ， m_1 会在 m_2 之前被所有接受者接收
- 如果 m_1 || m_2 ， m_1 和 m_2 可以被接受者随意的接收
- 全序组播：m_1 和 m_2 必须被所有的接受者以相同的顺序接收
- 算法：每个组成员维持一个 N 维度时间戳向量，全都初始化为 0