Lamport 原来是马萨诸塞的。

读文章的目标：搞清楚

  • 基本模型，基本假设：分布式系统的基本模型往往比较复杂。实际论文中的模型与课本中的模型
    比，要精细地多。大家需要按照课上讲的框架，把论文中模型的各个纬度都讨论清楚。
  • 基本问题：是否是经典问题。即使对于经典问题（e.g. consensus），也有很多的变体。把问题全
    面认识清楚，与解决问题一样重要。对于一些不经典的问题，可以参照课上的学习，将问题全面
    地认识清楚，解释清楚。
  • 主要贡献：对于论文贡献的深入解释，往往是一个具体的模型、算法、分析技术。技术的细节不
    是最重要的，简单copy原文更是大忌。课程看重的是，从课程中所学习的视角进行分析解读，进
    行原理性的提炼、阐述等。另外，虽然我们是偏理论的课程，但是对于实现、实验、系统的解读
    也是欢迎的，例如，系统设计、实现的背后，理论建模与分析是如何发挥指导性作用的，等等。

分布式系统中的时间，时钟，和事件的序关系

前言

构造一个“事件发生在另一事件前”的偏序关系。

提出分布式算法，用以同步一个逻辑时钟系统，实现事件的全序。

使用一个解决同步问题的方法来刻画全序的作用。

然后提出一个同步物理时钟的算法特例，给出了时钟偏离同步的上界。

分布式系统中，时间不同步导致事件之间的序关系不确定。

我们讨论偏序，然后给一个算法来把偏序扩展成所有事件的满足consistency 的全序。这个算法就对我们实现分布式系统很有帮助。

之后呢我们会解决一个简单的同步问题，来展示它的用法。

意外的是，当算法给出的序和用户观察到的不一致的时候，不正常的行为就会发生。我们可以通过引入真实的物理时钟来避免这个问题。我们描述了一个简单的方法来同步这些时钟，并且求出了偏差的上界。

不用物理时间定义偏序，因为可能不准。

系统定义：

假设系统由一堆进程组成。每一个都是事件的序列。一个子程序可以是事件，一条机器指令也可以是时间。假设他们形成一个序关系，

a occurs before b in this sequence if a happens before b

单线程，就是一组事件的全序。

假设收发消息是一个事件，那么我们可以定义“发生在前”关系（happens before），denoted by ->

Def. The relation “->”, on the set of events of a system is the smallest relation satisfying the following three conditions:

(1) If a and b are events in the same process, and a comes before b, then a->b.

(2) If a is the sending of a message by one precess and b is the receipt of the same message by another process, then a->b.

(3) If a->b and b->c then a->c.

简单来说：线程内有序；同一消息的收发有序；传递性。

Concurrent iff not a->b and not b->a.

For all a, not a->a. Irreflexive

我们可以画时空图来表明这种序关系。

我们只考虑已经发送的消息，而不考虑可能将会发送的消息。这是更实际的。

现在我们引入逻辑时钟。其实就是给每个事件赋一个时间戳。

对每个进程Pi定义时钟Ci，它可以给进程中的每个事件都发一个时间戳。整个时钟系统就表示为一个函数 C，为事件产生时间数 C.

C = Cj 如果 b 是 Pj 的一个事件。现在我们并不对这个时间与物理时间进行关系的假设。所以我们只认为这是逻辑时钟。有可能只是个计数器。

现在我们考虑，这个系统的“正确性”到底是什么意思。

Clock Condition. For any events a, b:

​ if a->b, then C < C

BUT Reverse not holds:

Suppose $C\langle a \rangle < C\langle b\rangle \implies a\rightarrow b$

Then $\neg a\to b \implies \neg C\langle a\rangle < C\langle b \rangle$

$Concurrence \iff \neg a\to b \and \neg b\to a$

$\iff \neg C\langle a\rangle < C\langle b\rangle\and \neg C\langle b\rangle < C\langle a\rangle$

$\iff C\langle a\rangle = C\langle b\rangle$

但是并发事件并不一定是同时进行。

时钟序成立，如果：

  • C1. If $a$ and $b$ are events in process $P_i$, and $a$ comes before $b$, then $C_i\langle a\rangle < C_i \langle b\rangle$.
  • C1. If $a$ is the sending of a message by process $P_i$ and $b$ is the receipt of that message by process $P_j$, then $C_i\langle a\rangle < C_j\langle b\rangle$

我们从时空图来考虑时钟。想象进程的时钟遍历每一个数字，每两个连续的事件之间都有（可能多次）“拨动”的操作。

然后对不同的线程，我们把它们相同的tick用虚线连起来。C1 就是说同线程中的两个事件之间必然有一条tick线。C2 则是说每一条消息线必须穿过一条 tick 线。

tick 线就是 笛卡尔 坐标系上的等时线（space-time）。我们把这玩意捋直了，这就表示了时间顺序了，还不用物理时钟。

这玩意你把它想象成三维的时空图也行。

假设线程是算法，事件代表其中的特定行为。

Pi 的时钟由一个寄存器 Ci 来代表，所以 Ci 就是事件 a 时寄存器的值。寄存器会在事件之间改变，所以这个改变并不构成事件。

为了保证系统满足 Clock Condition，我们要确保 C1, C2。C1 很简单。线程只要遵守这个实现规则：（Implementation Rule）

IR1. Each process $P_i$ increments $C_i$ between any two successive events.

C2，我们需要每个消息 m 包含一个时间戳 Tm，为消息发出的时间。然后在收到以 Tm 标识的消息时，进程时钟必须跳到 Tm 以后。更准确的说：

IR2. (a) If event $a$ is the sending of a message $m$ by process $P_i$, then the message $m$ contains a timestamp $T_m = C_i\langle a\rangle$.

(b) Upon receiving a message $m$, process $P_j$ sets $C_j$ greater than or equal to its present value and greater than $T_m$.

然后我们就可以排全序啦。

但是为了避免 ties，我们用一个任意的全序。我们定义关系 $\Rightarrow$:

if $a$ is an event in process $P_i$ and $b$ is an event in process $P_j$, then $a\Rightarrow b \iff (i) C_i\langle a\rangle < C_j\langle b\rangle \or (ii)C_i\langle a\rangle = C_j\langle b\rangle \and P_i \prec P_j$

什么意思呢？就是我们给线程随便指定一个优先级。然后遇到时间戳相同的事件，就按照他们的线程优先级来排事件的序。

我们用这玩意来构建一个满足

  • 互斥
  • 先到先服务
  • Liveness

的互斥资源请求算法。假设资源一开始已经分配给了一个进程。

这个并不简单。比如 P1 向 P0 请求后，向 P2 发一个消息。然后 P2 也向 P0 请求。第二个请求可能到的比一个早，这就 violation。

所以我们需要 IR1 + IR2 构造的一个时钟，来定义事件的全序。那么为了解决上述的问题，我们让每一个进程都了解到全局所有进程的操作。

简化问题，避免实现细节上的混乱，我们假设：

  • 固定两个进程之间单向的消息是按序到达的。
  • 消息一定会送到。

（我：现在TCP就很方便了。）

每个进程维护自己的请求队列，对其他进程不可见。一开始队列里存在一个 T0：P0 requests resourse ，即初始时的资源状态。T0比所有时钟都要小。

现提出5规则的算法，每条规则都包含于一个事件。

  1. 请求资源， $P_i$ 发送 $T_m : P_i$ requests resource 给所有的其他进程，并且把这个消息放到自己的请求队列里。

  2. $P_j$ 收到请求消息的时候，放到请求队列里，并返回一个带时间戳的 ACK （如果已经发了一个 > Tm 的消息，则不用再返回）

  3. 释放资源，则从请求队列里弹出，并向其他所有人发送。

  4. 收到释放，则也弹出。

  5. $P_i$ 在下列情况满足时获得资源

    • 在它自己的队列里，存在 $\Rightarrow$ 关系上的最小消息 $T_m : P_i$ requests resource. （消息的序就取决于其所在的事件的序）
    • $P_i$ 收到了所有人的比 $T_m$ 更晚的消息。

    上述两条都是 Thread Local 的条件

这些东西加起来，肯定就满足了互斥、FCFS 和 Liveness。

5-2 结合按序到达性质，就保证了 $P_i$ 知道了自己的请求之前的所有请求。（我自己弄了一个两线程的实示例。实际上意思就是，假如双向消息的交付不按物理时间序，是交错的，后发消息的线程在另一个线程取得资源之前，是不会收到全部的回复的。也就保证了互斥。）