Lamport时钟
机制：
1. 进程维护一个单调递增的计数器，充当逻辑时钟。
2. 用逻辑时钟为时间添加时间戳。
3. 按事件的时间戳大小为时间排序，任何两个时间不可能在同一时间发生，任何消息收到的时间都应该比发送的时间晚。
逻辑时钟的修改规则：
-进程Pi发出事件前，逻辑时钟Li: = Li+1
-进程Pi发送消息m时，在m中添加时间戳t=Li
-进程Pj在接收消息时，更新Li:=max(Lj , t) + 1, 给时间recv(m)加上时间戳后发送给应用程序。
具体过程：
在时刻6，消息A被发送到时刻16，这是正常的，因为它带的时间搓是6，进程2会认为它经过了10的滴答用于传输。而消息B同理。但是，消息c的时间戳是60，到达的进程2的时候却是56，所以进程b会调整自己的时钟到61，搞好比60晚1个滴答。这样来校正自己的时间。
由于不同的进程产生的消息可能具有相同的逻辑时钟
所以引入了全局逻辑时钟:
- 引入进程标示符创建时间的全局关系
- e e'分别为进程Pi Pj中发生的事件，则全局逻辑时间戳分别为（Ti , i ), ( Tj , j).
- e -> e' <=> Ti< Tj || Ti< j
- 系统中各个时间的Lamport时间错均不相同
基于Lamport时间戳的事件排序--总结
- 算法不依赖与事件发生的真实时间
- 与真实物理时间中事件的发生顺序可能不一致
Lamport时钟不具备的性质： 若 L(A) < L(B) 则A->B
没有捕获事件的因果关系
节点B发布一篇文章给A和C，节点A就此发表评论r，并传输给节点B和C，我们无法确定r的先后关系
即 C(a) < C(r) 不能推出 a -> r
全局状态：
用途：
1. 分布式无用单元的收集
检测系统中对象是否被引用的时候，需要检测对象是否真的没有被引用。即没有被本地进程，其他节点进程，或者是进程之间的通信的消息引用。
2. 检测死锁
3.分布式终止检测，即检测某一个分布式算法是否可以终止
假如p1和p2执行一个分布式算法，每个进程都会请求另外一个进程的值。我们可以确定在一个瞬间，进程的状态时主动的还是被动的。
考虑以下的状况：p2发送了一条消息给p1，当p1还没有接收到消息的时候，也就是说消息还在路上的时候。p1p2都变成了被动的状态，但是一旦当p1收到消息的时候，它又即将变成主动。因此算法还不能终止。
所以当我们考虑问题的时候，不仅仅要考虑进程的状态，还必须考虑信道的状态。
全局状态和一致性割集：
- 要准确测量系统的全局状态是非常困难的，根源是缺乏一致性的全局时间。
一些定义：
进程的历史： Hi =
其中每一个事件都是进程的内部动作，如收发消息。
全局历史：
H = h1 u h2 u ... u hN
进程状态：
Sik ： 进程pi 在第k个时间发生之前的状态
全局状态： 单个进程状态的集合
S = （S1 ， S2， …… SN）
割集系统全局历史的子集，是进程历史的并集。
C =
割集的一致性：
左边的割集是不一致的，因为他只包含了e20这个收到了消息的时间，却没有包含发送该消息的事件。
而右边的割集是一致的，因为发送e22的事件包含了，这个时候消息还没有到达p1，其割集恰好表示消息还在路上。
一致的全局状态 -- 对应于一致割集的状态
我们可以吧整个分布式系统的运行理解成系统在各个割集之间进行状态转换。
S0 -> S1 -> S2 ……
走向：
-全局历史中所有事件的全序
-与每一个本地历史的顺序一致，当然喽，本地历史发生的顺序，肯定在全局里面都囊括了的。
-不是所有的走向都经历全局的一致性状态
线性化走向：
-所有的线性化走向只经历一致性的全局状态
-如果存在一个经过S和S'的线性化走向，则状态S' 是从S可达的。
谓词：（这个我没看懂，详细参考书上的内容）
chandy和lamport的快照算法
目的：捕获一致的全局状态。
假设：
- 进程和通道不会出现故障
- 单向通道，提供FIFO顺序的消息传递
- 进程之间存在全联通的关系
- 任一进程可在任一时间开始全局拍照
- 拍照时，进程可以继续执行，并发送和接收消息。
算法基本思想：
- 接入通道 + 外出通道
- 进程状态 + 通道状态
- 标记消息
标记接收规则规则:强制进程在记录下自己的状态之后，但是在他们发送其他消息前，发送一条- - 标记。
标记接收规则:在接收标记前，强制没有记录状态的进程记录自己的状态。
标志的作用是为各个局部状态的同步提供一个截止的参照物.
由于每个进程都可以自主地发起快照算法，因此发起者必须对标记进行标识，以便区分,否则不同进程发起的快照算法将无法区分，造成混乱。
发起者进程通过记录自己的状态，并向所有要经过的信道(例如所有其他进程)发送特殊的控制消息，从而在执行任何事务或发送其他消息之前调用该算法。所有其他进程都要进行相同的处理工作。因此，每个进程有一个标记(类似于提交点)，这样在后面遇到某些并发问题时可以回到该标识处。
算法举例：
- 两个进程p1、p2进行交易， 每件$10
- 初始状态：p2已经收到5件商品的订单，它将马上分发给p1
过程：
1. p1在实际的全局状态S0中记录他自己的状态 P1: <$1000,0>。根据标记发送规则，p1在通过通道c2发送下一个应用层消息(订单10, $100)之前,在它的外出通道c2上发送一个标记消息。系统进入S1。
2.在p1接收到p2的消息之前，它通过c1发送一个应用消息（5个窗口部件）以响应p1之前的订单，产生新的实际全局状态s2.
3.现在，进程p1接受到p2的消息，p2接收到标记。根据标记接受规则，p2将它的状态记录成 <$50,1995>，将通道c2的状态记录成空序列。根据标记发送规则，它通过c1发送标记消息。
4.当进程p1接收到标记消息时，它将通道c1的状态记录成在第一次记录他的状态之后接收到的那个消息（5个窗口部件）。最后达到状态s4. |
