1. 时钟、事件和进程状态
1.1. 定义
设有一个分布式系统有n个进程pi(i=1,2,…,n)，该集合记为P
每个进程pi有各自的状态si
每个进程pi在不同的处理器上运行，处理器之间不共享内存
1.2. 事件顺序与历史
a) 事件顺序：
每个进程pi的事件序列可以用全序方式排列。假定事件e在事件e′前发送，则两事件有→i关系，即e→i e′
b) 事件历史：
一个进程pi的事件历史定义为：
history(pi)=hi=<e0i,e1i,…> （每个事件按照→i关系排序）
1.3. 时钟
每个机器都有自己独立的硬件时钟，假设当前实际时间为t，对于进程pi:
- 读取的硬件时钟值为：Hi(t)
- 产生的软件时钟值为：Ci(t)=αHi(t)+β （对硬件时钟放大，并添加偏移量以接近实际实际t，一般而言C(t)≠t）
时钟分辨率：物理时钟值的更新周期
1.4. 时钟偏移和时钟漂移
a) 时钟偏移
即在实际时间t下，两时钟读数不同，即Hi(t)≠Hj(t)
b) 时钟漂移
在某时间点，两时钟初始值一致，但过一段事件后，两时钟读值不同
时钟漂移率：由参考时间度量的每个单位时间内，时钟与名义上的参考时钟之间的偏移量（如11.6天有1秒的偏差）
1.5. 通用协调时间（UTC）
是国际计时的标准，基于原子时间
2. 同步物理时钟
外部同步：设有同步范围D>0，UTC时间源为S，当前实际时间为t，则满足|S(t)−Ci(t)|<D，其中i=1,2,…,n
内部同步：设有同步范围D>0，当前实际时间为t，则满足|Ci(t)−Cj(t)|<D，其中i,j=1,2,…,n
时钟正确性：一个物理时钟的漂移率在范围ρ>0之内，则是正确的
这表明硬件读数的间隔误差是有界的，即：
(1−ρ)(t′−t)≤H(t′)−H(t)≤(1+ρ)(t′−t)，这里t
单调性原则：保证t′>t⇒C(t′)>C(t)
故障：不满足时钟正确性条件的时钟就是故障的，分为2类
- 崩溃故障：时钟完全停止滴答
- 随机故障：其它的时钟故障
2.1. 同步系统中的同步
同步系统中，同步的消息message被标记为t, 传输时间有上界tmax
则不确定性为u=tmax−tmin，接收方可设置自己的时间为t+α（如α=u/2）
同步n个时钟，最优的时间偏移为u(1−1/n)。
2.2. 同步时钟的Cristian方法
使用一个时间服务器（连接到UTC设备），实现外部同步。客户请求时间服务器以获取时间。条件是：客户与服务器之间的往返时间与所要求的精度相比要足够短。
客户端向服务器发送req,然后服务器返回的resp中被标记为t并返回，整个往返时间为tround，单个传输的时间最短值为tmin, 则服务器的时钟时间位于范围[t+tmin,t+tround−tmin]，即精度为±(tround/2−tmin)
会出现假冒时间应答、无法处理时钟出错的问题。
2.3. Berkeley算法
一种内部同步的算法。
集群中选取一台协调者作为master，它定期轮询其它要同步时钟的机器（称为slave），slave返回时钟值给master。根据2.2.类似的方法，派出错误的读数，计算到一个容错平均值，最后返回给slave时钟的调整量（可正可负）。
若master故障，选举另一台机器接管master。
2.4. 网络时间协议（NTP）
目标：提供服务使互联网用户与UTC同步，服务可靠，提供保护以防止对时间服务的干扰
服务网结构：树形，层次结构。故障时同步子网可重配置。
- 主服务器：与UTC源同步（作为根）
- 二级服务器：与主服务器同步
同步方式（准确性由低到高）：
- 组播
- 过程调用模式：类似2.2.的Cristian算法操作
- 对称模式：一对服务器交换有时许信息的消息，以提高准确性
交换消息对：不使用不可靠的UDP传递
NTP计算偏移oi（即两时钟的偏移的估计）和延迟di（即消息对传输的整个时间）
设消息对的传输时间分别为t和t′, 第一个消息发送和接收的时间戳以及第二个消息发送和接收的时间戳分别为Ti−3,Ti−2,Ti−1,Ti, 则有：
- di=Ti−2−Ti−3+Ti−Ti−1=t+t′
-
实际偏移o=oi+(t′−t)/2, 其中oi=(Ti−2−Ti−3+Ti−Ti−1)/2
- oi−di/2≤o≤oi+di/2
然后，NTP根据连续的<oi,di>应用数据过滤算法，估计偏移量o以及估计的质量
3. 逻辑时间和逻辑时钟
3.1. Lamport的“发生在先”偏序关系（即因果序）
定义“发生在先”关系符号为：→
-
若存在进程pi, 有e→ie′, 则e→e′
-
任意消息m, 有send(m)→recv(m), 前者是发送事件，后者是接收事件
-
传递性，若e→e′,e′→e″, 则e→e″
在这个规则下，多进程下的事件排序可能不唯一。
3.2. 逻辑时钟
逻辑时钟只是一个单调增长的计数器，与物理时钟无关。
定义：
- 每个进程pi维护自己的逻辑时钟Li
- L(e)代表任意进程的事件e的时间戳
规则：
- 进程pi发出事件前，Li:=Li+1
- 进程pi发出消息m时，在m中附加t=Li
- 进程pj接收消息<m,t>时, Lj:=max(Lj,t), 然后给recv(m)事件打时间戳（之前需要应用规则1）
结论：
若e→e′, 则L(e)<L(e′) （反过来不成立）
3.3. 全序逻辑时钟
给时间戳打上进程标识，如[Ti,i],[Tj,j]（i,j为进程标识，且可比）。利用规则，当Ti≤Tj，或者i<j且Ti=Tj时[Ti,i]<[Tj,j]。
3.4. 向量时钟
改进Lamport时钟的缺点：L(e)<L(e′)不能推出e→e′
定义：
- n个进程的系统的向量时钟V是长度为n的向量
- 每个进程pi维护自己的向量时钟Vi
- 事件e的时间戳为V(e)
规则：
-
初始下，对任意的i,j，有 Vi[j]=0，这里i,j=1,2,…n
- 在pi中，给事件加时间戳前，令Vi[i]:=Vi[i]+1
- pi发送消息m时，给消息m附上t=Vi
- pi接收消息时，执行合并，即设置Vi[j]:=max(Vi[j],t[j]), 这里j=1,2,…,n，并给recv(m)事件打时间戳（打之前需应用规则2）
比较与结论
- V=V′⟺V[j]=V′[j](j=1,2,…,n)
- V≤V′⟺V[j]≤V′[j](j=1,2,…,n)
- V<V′⟺V≤V′∧V≠V′
- ¬(V(c)≤V(e))∧¬(V(e)≤V(c))→c‖e（并发）
可得到：e→e′⟺V(e)<V(e′)
4. 全局状态
4.1. 全局状态和一致割集
全局状态：进程集合的连续状态（难以观察，因为缺乏全局时间），即S=s1,s2,…,sn
全局历史：H=h0∪h1∪…∪hn−1
系统执行的割集：C=hc11∪hc22∪…∪hcnn
- 割集边界集合：ecii|i=1,2,…,n
- 全局状态S中si即为执行好ecii后的状态
- 一致割集：对于任意事件e∈C, 满足f→e⇒f∈C
- 一致的全局状态：对应于一致割集的状态
（顺序）走向：全局历史中所有事件的全序，且它保持了每个本地历史排序→i关系
- 线性走向：在走向的基础上，保持了全局历史H上的发生在先关系→（即只经历线性一致的全局状态）。若有一个经过S与S′的线性走向，则状态S′是从状态S可达的
- 线性走向中，并发事件（注：并发对应的是因果顺序上不可比）的顺序可以变换，得到的仍是线性走向
4.2. 全局状态谓词、稳定性、安全性、活性
全局状态谓词：系统P的全局状态映射到true,false的函数
- 对象无用、系统死锁、系统终止的状态的谓词是稳定的，即该系统将在所有的可从该状态可达的状态中一直保持true
- 监控和调试程序时，谓词是不稳定的
安全性：设有不希望有的性质（一个全局状态谓词）α，系统初始状态为S0，它的安全性是一个断言，即对所有可从S0可达的状态S，α值都为false
活性：设β为希望有的性质，它的活性是一个断言，即对所有可从S0开始的所有线性走向L，其可达的状态为SL，β值都为false
4.3. Chandy & Lamport 快照算法
该算法是为了记录进程集pi(i=1,2,…,n)的进程状态和通道状态集（即快照），其记录的全局状态是一致的。
前提假设：
- 通道与进程不会出现故障，通信可靠
- 通道是单向FIFO通道
- 任意两进程有一个通道连接
- 任意进程可在任意时间开始一个全局快照
- 拍快照时，进程可继续执行，发送、接收消息
概念：
- 接入通道：其它进程向本进程发送消息的通道
- 外出通道：本进程向其它进程发送消息的通道
通道的状态：若消息还在某通道中传输，则该消息就在该通道的状态中
- 标记消息：若接收者没保存自己的状态，则提示其保存该状态；也可以决定哪个消息包含在通道状态中
a) 算法
标记接收规则（当进程接收到标记消息后）：
procedure recvMarkMsg(p:Process, c:Channel, inChannels:Set)
if p.isRecordState == false
recordState(p)
c.state = Φ //c是接入通道
recvMsg(inputChannels)
else
c.state = recordState(c) // 从p记录状态开始到现在从c中收到消息的集合
标记发送规则：
procedure sendMarkMsg(p:Process, outChannels:Set)
foreach c in outChannels
send(markMsg, c) // 在发送任何其它消息之前发出标记消息
可以在假设中保证，一些进程记录它的初始状态之后的有限时间内，所有进程将记录它们的状态和接入通道的状态。
割集也与该算法记录的状态是一致的。
观察到的全局状态与初始和最后的全局状态之间是可达的。
对于稳定性谓词而言，快照获得的值是多少，最终值/最初值也是多少。
4.4. 分布式调试（Marzullo & Neiger算法）
对于谓词ϕ，全局历史H：
- 可能的ϕ：存在一个一致的全局状态S, H的一个线性走向经历了这个状态，且ϕ(S)为真
- 明确的ϕ：H的所有的线性走向Li都经历了一个状态Si，且ϕ(Si)为真
a) 收集状态
进程pi最初向监控器队列Qi发送初始状态，之后状态改变时发送消息
（可优化，如只发送部分状态，又如对于特定谓词ϕ状态改变后再发送）
b) 观察一致全局状态
监控器汇总收集的状态，判断其是否为一致的割集（即C中，所有事件e满足f→e⇒f∈C）
实现：
- 状态消息附上向量时钟值，队列Qi要根据向量时钟的第i项对消息排序
- 然后根据时间戳进行判断观察到的割集状态是否一致
- V(si)[i]≥V(sj)[i],∀i,j=1,2,…,n, 即CGS条件，满足则观察到的是历史状态是一致的（多次观察到的状态变化是线性走向）
- 很容易得到一个状态走向的网格，状态都是一致的，走向是线性的
c) 判断可能的ϕ
上述可知，可能的线性走向（线性走向可能有多个）构成网格，有层数的概念。
监控器可以发现L+1层中可从L层一个给定的一致状态可达的一致状态集合，只需遍历所有的队列Q即可。下层的S′从S可达，需满足：
- V(sj)[j]≥V(s′i)[j](j=1,2,…,n,i≠j)
只要判断到一个状态ϕ为真，这输出可能的ϕ
l := 0
states := {(s^0_1, s^0_2, ..., s^0_n)}
while (for all S in states, phi(S) = false) # 只要存在为真就输出
l := l + 1
reachableStates = {S_next | from all S in states, S_next is reachable from S, and level(S_next) = l}
states := reachableStates
end while
output "possible_phi"
d) 判断明确的ϕ
可能需要遍历整个网格。每条路径都要遍历，但某条路径出现ϕ为真时，后面就不需要判断了。
l := 0
if (phi(s^0_1, s^0_2, ..., s^0_n) = true)
states := {}
else
states := {(s^0_1, s^0_2, ..., s^0_n)}
while (states is not empty)
l := l + 1
reachableStates = {S_next | from all S in states, S_next is reachable from S, and level(S_next) = l}
states := {S in reachableStates, and phi(S) = false} # 遍历所有路径
end while
output "definite_phi"
开销：对于n个进程，一个进程事件最大个数为k, 则：
- 时间复杂度为O(kn)
- 空间复杂度为O(kn)
优化，对于队列Qi，若满足：
- V(slastj)[i]>V(si)[i],j=1,2,…,n∧j≠i
那么Qi可以删除包含状态si的消息
