Chandy-Lamport algorithm 是一种分布式快照算法，其名称以两个作者（K. Mani Chandy & Leslie Lamport）的名字命名。Chandy-Lamport 算法可以在没有全局时钟的情况下，记录异步分布式系统的一致性全局状态。Chandy-Lamport 算法对于解决分布式系统的一些问题如：分布式系统的死锁检测，分布式系统的终止检测等具有重要意义，也可以用于分布式系统的 checkpointing。并且 Chandy-Lamport 算法的执行可以和分布式系统的计算同时进行，不会影响和更改底层的运算状态。

介绍

分布式系统中的进程通过发送和接收消息通信。一个进程可以记录它自己的状态和它所发送/接收的消息，也可以什么都不记录。一个进程 p 要确定全局系统状态，p 必须要与其他进程协作：其他进程都记录下其本地的状态并把记录下的本地状态都发送给 p。但由于没有一个全局的时钟，所有进程不可能精准的在同一时间同时记录下本地状态。因此我们必须找到一种算法，让进程都记录下它们各自的状态以及它们之间消息通道的状态，然后通过拼凑这些进程和消息通道的状态来组成一个大的全局的系统状态。

（在本论文之前）一些通过确定分布式系统的全局状态来解决死锁和终止问题的算法已经发布。不过 Gligor 和 Shattuck（参见原文参考文献 [5]）指出，许多已发表的算法都不正确且不切实际。不正确或不切实际的原因可能是不能很好地理解本地进程状态，全局系统状态和分布式计算中的点之间的关系。而本文的贡献之一就是定义这些关系。

模型

一个分布式系统由有限个进程和有限个消息通道组成，它可以由标记的有向图描述，其中顶点表示进程，边表示通道。比如图 1 的例子：

我们假定消息通道具有无限缓冲区，不会发生错误，并按发送的顺序传递消息。 （无限缓冲区假设是为了便于说明，如果是有界缓冲区则需要证明不存在进程会将消息添加至已满的缓冲区。）通道中消息可以有任意的延迟但延迟必须是有限的。沿着通道接收的消息序列是沿着通道发送的消息序列的初始子序列。消息通道的状态就是沿通道发送的消息序列，不包括沿通道已接收的消息。（也即：已发消息 - 已收消息 = 遗留消息 == 通道状态）

一个进程可以由一系列状态集合、一个初始状态（来自状态集合）和一系列事件定义。一个事件 e 是进程 p 中的一个原子操作，该操作可能改变进程 p 自己的状态和最多一个消息通道 c 的状态，消息通道 c 状态的改变可能是 p 沿着 c 发送了一个消息（如果 c 离开 p），也可能是 p 从 c 中接收了一个消息（c 指向 p）。一个事件 e 可以定义为一个 5 元组：(p, s, s’, M, c)。1、p 为事件发生的进程，2、s 为事件发生前 p 的状态，3、s‘ 为事件发生后 p 的状态，4、M 为消息，5、c 为发送消息的通道。如果没有消息发送/接收动作发生，M 和 c 为空（null）。

分布式系统的全局状态就是一系列进程状态和消息通道状态的集合：全局状态的初始状态就是各进程的初始状态及空的所有消息通道。一个事件的发生将会改变全局状态（事件驱动状态的转换）。设 e = (p, s, s’, M, c) 我们说当且仅当满足如下条件时，事件 e 才会在全局状态 S 中发生：1、进程 p 在全局状态 S 中的状态为 s；2、如果 c 是一个朝向 p 的消息通道，那么 c 的状态在全局状态 S 中是以消息 M 为队首的消息序列。我们定义一个 next 函数，next(S, e) 为事件 e 发生后紧跟 S 后的全局状态。next(S, e) 的值和 S 相比有如下几点差别：1、进程 p 的状态在 next(S, e) 中是 s’；2、如果 c 是一个朝向 p 的消息通道，则 c 在 next(S, e) 中的状态为 S 中 c 的状态删掉队首的消息 M（出队，此处论文打印有错：if e is a channal… -> if c is a channal…）；3、如果 c 是一个离开 p 的消息通道，则 c 在 next(S, e) 中的状态为 S 中 c 的状态在队尾加上的消息 M（入队）。

令 seq = (e_i: 0 ≤ i ≤ n) 是分布式系统进程的一个事件序列，我们说 seq 是一个“系统计算”当且仅当 ei 会发生在全局状态 Si (0 ≤ i ≤ n) 中时，其中 S0 是全局初始状态，并且 Si+1 = next(Si, ei) (0 ≤ i ≤ n) 。

例子 2-1：为清晰表述分布式系统的定义，我们来考虑一个简单的系统模型，包括两个进程：p 和 q，以及两个通道：c 和 c’，如图 2 所示：

这个系统还有一个 token 在进程之间传输，因此我们也称这个系统为“单-token 系统”。每个进程有两个状态：s0 和 s1，token 不在时是 s0，token 在时是 s1。p 的初始状态是 s1，q 的初始状态是 s0，每个进程有两个事件：1、随着发送 token 状态从 s1 到 s0；2、随着接收 token 状态从 s0 到 s1。进程的状态转换图如图 3 所示，全局状态及其转换过程图如图 4 所示：

“系统计算”对应于从初始全局状态开始的全局状态转换图（图 4）中的路径。比如是“系统计算”的例子：1、空的序列，2、p 发送 token，q 接收 token，p 接收 token。不是“系统计算”的例子：p 发送 token，q 发送 token。因为事件“q 发送 token”在 q 状态为 s0 时不可能发生。

为简单起见，按 token 转移的顺序（见图 4），我们将四个全局状态称为（1）in-p，（2）in-c，（3）in-q 和（4）in-c’ 用以表示 token 的位置。这个例子在后面中也会用于启发算法的产生。

例子 2-2：这个例子展示了不确定的计算，不确定性在分布式快照算法中起到了有趣的角色。

在 2-1 的例子中，在每个全局状态中只有一个可能的事件。现在考虑另外一个系统，其拓扑结构和 2-1 例子一致，但进程 p 和 q 的定义和状态转移如图 5 和 6 所示：

一个计算的例子如图 7 所示，可以观察到，这里的一个全局状态可以有多于一个的状态转移。比如：在初始全局状态里，可以发生“p 发送 M”，“q 发送 M‘”这样两个事件，并且这些事件的后续状态并不相同。

算法

算法逐步启发的过程

全局状态记录算法按如下流程工作：每个进程记录它自己的状态，和消息通道相关的两个进程（首尾两端）协助记录通道的状态。我们不能保证所有进程和消息通道的状态会被瞬间同时记录，因为没有全局的时钟，但我们要求记录的进程状态和消息通道状态可以拼装成一个“有意义”的全局系统状态。

全局状态记录算法叠映在底层计算之上，也就是，它必须和底层算法同时进行，但又不能改变底层的计算。全局状态记录算法可以发送消息并要求进程进行计算，但是，记录全局状态所需的消息和计算不得干扰底层计算。

现在我们通过一个例子来阐释算法启发的过程，在例子中我们假设可以瞬时记录下消息通道的状态，具体如何记录通道的状态我们后面再讨论。设 c 为 p 到 q 的通道。这个例子的目的是为了直观的理解记录 c 状态的瞬间和记录 p，q 状态瞬间之间的关系。

例子 3-1：考虑之前的“单-token 转换系统”，在全局状态 in-p 时记录 p 的状态，此时 p 的状态显示 token 在 p 当中。然后假设全局状态转移到了 in-c（p 发送了 token），此时记录通道 c，c’ 和进程 q 的状态，此时 c 的状态显示 token 在它里面，而 c‘ 和 q 不拥有 token。在这种情况下，组装全局的系统状态会显示系统中有两个 token，一个在 p 中，一个在 c 中。但在“单-token 系统”中，全局状态的这种情况是从初始状态开始不可达的！这个错误引发的原因是因为 p 的状态在 token 发送之前记录，而 c 的状态却在 token 发送之后记录。设 n 为记录 p 状态之前 p 沿 c 发送的消息数量，n’ 为记录 c 状态之前 p 沿 c 发送的消息数量。上面的例子显示了，如果 n < n’，则全局系统状态可能会存在不一致性。

现在考虑另一种情况。假设在全局状态 in-p 时记录 c 的状态，然后系统转换全局状态至 in-c，此时在记录 p，q，c‘ 的状态。在这种情况下全局系统状态显示没有 token。这个例子展示了，如果 c 在 p 沿着 c 发送消息之前记录状态，而 p 在 p 沿着 c 发放消息之后记录状态，也即 n > n’，全局系统状态也可能会存在不一致性。

因此从上述例子可知，（通常而言）一个一致性的全局系统状态要求：

（1）：n = n’

同理，设 m 为 q 的状态记录之前沿 c 接收到的消息数量，m‘ 为 c 的状态记录之前沿 c 接收到的消息数量，同样要求有：

（2）：m = m’

在任何一个状态，一个消息通道沿它接收到的消息数量不会超过沿它发送的消息数量，即：

（3）：n‘ ≥ m’

从上面的等式可得，

（4）：n ≥ m

消息通道 c 的状态必须是在发送者状态记录之前，沿它发送的消息序列，除去接收者状态记录之前，已被接收者接收的数据——也即，如果 n‘ = m’，则 c 的状态必须是空序列；如果 n’ > m’，则 c 的状态必须为从 (m’+1) … n’ 位置的 p 沿着 c 发送的消息序列（未接收部分）。以上的事实和等式（1）-（4）说明了一个简单算法：q 可以记录消息通道 c 的状态。在 p 沿着 c 发送完 n 个消息之后，p 必须发送一个特殊的消息，称为 marker。（但必须在 p 发送下一个消息之前。）marker 对下层计算不产生影响。c 的状态就是 q 在记录自己的状态之后沿着 c 接收到的在 marker 消息之前的消息序列。为了确保等式（4）成立，如果 q 在沿 c 接收到 marker 之前从未记录过自己的状态，q 必须在接收下一个消息前先记录下自己的状态。

全局状态检测算法的概述

Marker-Sending Rule for a Process p（进程 p 的 marker 发送规则）：对任何离向 p 的消息通道 c：p 在记录下自己的状态并欲往 c 发下一个消息之前，先发一个 marker。
p sends one marker along c after p records its state and before p sends further messages along c.

Marker-Receiving Rule for a Process q（进程 q 的 marker 接收规则）：一旦沿着消息通道 c 接收到了一个 marker：如果 q 从未记录过自己的状态，则 q 先记录自己的状态，q 再把 c 的状态记录为空序列；否则，q 将自己的状态记录之后，marker 接收之前的所有消息序列记录为 c 的状态。

if q has not recorded its state then
  begin q records its state;
        q records the state c as the empty sequence
  end
else q records the state of c as the sequence of messagesreceived along c 
     after q’s state was recorded and before q received the marker along c. 

算法的终止

Marker 的发送和接收规则确保了如果每个消息通道都能接收到 marker，那每个进程都会记录下它自身的状态及所有朝向它的管道状态。为了确保全局状态记录算法能在有限的时间内完成，每个进程必须保证：（L1）、marker 不会永远停留在收入通道中，及（L2）、进程记录自己的状态会在算法启动后的有限时间内完成。

全局状态记录算法可以由一个或多个进程发起，发起的进程在没有收到 marker 的情况下首先自发记录自身状态。如果 p 记录下了状态，并有个通道连到 q，则 q 会在有限时间内记录其状态，因为 p 会发送其一个 marker，并且 marker 会在有限时间内到达 q。推理可得，任何 p 有通道可达的进程都会在有限时间内完成状态的记录。

特别是，如果整个系统是一个强连通图，那只要一个进程发起状态记录，系统所有进程都会在有限时间内完成状态记录。

到目前为止算法描述了各进程记录自己的状态以及记录指向它的消息通道状态。这些记录的进程状态和通道状态必须收集到一起并组装成一个全局的状态。我们这边不再描述此类算法因为其他地方已有描述了（参见原文参考文献 [4, 10]）。一个简单的在强连通系统中收集信息的方法是每个进程都将自己记录的信息发往所有离向它的通道，每个进程在第一次接受到某个信息时记录下它并再转发到所有离向它的通道，这样所有的进程都能在有限时间内得到所有的记录信息，然后组装成全局状态。

算法的正确性

略

STABILITY DETECTION

略

参考资料
[1]. Distributed Snapshots: Determining Global States of Distributed Systems
[2]. Distributed Snapshots-Determining Global States of a Distributed System(译). http://duanple.com/?p=1066
[3]. Distributed snapshot. https://liumx10.github.io/2016/04/06/Distributed-snapshot/