（笔记） 时钟和全局状态 分布式系统

时钟、事件和进程状态

在分布式系统中，时间是我们想要精确度量的量。我们有时需要观察分布式系统，确定事件的某些状态是否同时发生。但是没有一个绝对的全局时间，能力有限，无法准确记录不同结点上的事件的时间。

• 操作系统读取结点的硬件时钟值Hi(t)$H_i(t)$
• 软件时钟 Ci(t)=αHi(t)+β$C_i(t)=\alpha H_i(t)+\beta$
  -注：通常来说，时钟不是准确的。但是我们可以调整Ci(t)$C_i(t)$给pi$p_i$的事件打时间戳。连续事件对应不同的时间戳的条件是时钟分辨率比连续事件之间的时间间隔小。

时钟偏移和时钟漂移

• 时钟偏移：时钟的读数之间的瞬间不同
• 时钟漂移：以不同的时间给事件计数，时钟振荡器的频率不同

假定一个简单的分布式系统由N个模型组成pi(i=1,2,...,N)$p_i(i=1,2,...,N)$。每一个pi$p_i$进程的状态是si$s_i$。每一个进程执行过程中，会采取一系列的动作，按照关系→i$\to i$排序：history(pi)=hi=<e0i,e1i,e2i,⋯>$history(p_i)=h_i=<e_i^0,e_i^1,e_i^2,\cdots >$。

同步时钟

内部同步的时钟未必是外部同步的，但是如果一个系统P在范围D内是外部同步的，那么同一系统在范围2D内是内部同步的。

同步系统中的同步

一个进程在消息m中将本地时钟的时间t发送给另一个进程。原则上，接收进程可以将它的时钟设置成t+Ttrans$t+T_{trans}$，Ttrans$T_{trans}$是进程传输m所花费的时间。但是该值常常是变化和未知的，存在各自结点上竞争资源，其他消息与m竞争网络。对于一个同步系统，同步N个时钟时，可获得的时钟偏移最优范围是μ(1−1/N),μ=(max−min)$\mu (1-1/N),\mu =(max-min)$，时钟设置为t+(max+min)/N$t+(max+min)/N$
Ttrans=min+x$T_{trans}=min+x$

Cristian算法：存在的问题与所有单个服务器实现的服务相关，单个时间服务器可能出现故障。

Berkeley算法：选择一台协调者计算机作为主机，这个计算机定期轮询其他要同步时钟的计算机。如果主机出现故障，要能选举另一个主机接管。主机发送每个从属机的时钟所需要的调整量，在时钟中选择差值不多于一个指定量的子集，平均值仅根据这些时钟的读数计算。

Lamport时间戳的缺点：从L(e)<L(e′)$L(e)<L(e^{{}^{\prime }})$不能推出e→e′$e\to e^{{}^{\prime }}$
向量时间戳的缺点：占用的存储以及消息的有效负载与进程数N成正比。

全局状态

• 分布式无用单元收集
• 分布式死锁检测
• 分布式终止检测

一致的全局状态（consistent global sates）是指对应于一致割集的状态。

Chandy-Lamport 快照算法

进程pi的标记接受规则：

pi接受通道c上的标记消息:
     if (pi还没有记录它的状态):
         pi记录它的进程状态；
         将c的状态标记成为空集；
         开始记录从其他接入通道上到达的消息；
     else
         pi把c的状态记录成从保存其状态以来它在c上接收到的消息集合
     end if

进程pi的标记发送规则：

在pi记录了其状态之后，对每个外出通道c：
    （在pi从c上发送任何其他消息之前）pi在c上发送一个标记消息；

Reference：
《Distributed Systems Concepts and Design Fifth Edition 》 第十四章
《Distributed Computing Principles, Algorithms, and Systems》