IRSDP 读书笔记 - 2. Basic Abstractio

《Introduction to Reliable and Secure Distributed Programming》

2.5 Timing Assumptions

An important part in the characterization of a distributed system is the behavior of its processes and links with respect to the passage of time.

换句话说，是否可以假设网络延迟的时间范围，是否可以假设 process 的处理速度是每个 distributed-system model 最重要的部分。

本章将会介绍时间相关的模型，failure-detector 是抽象耗时假设特别有用的方式。

2.5.1 Asynchronous System

假设 asynchronous distributed system 不对 processes 和 links 做任何耗时假设。也就是，我们不假设 process 会访问物理时钟，我们也不假设任何处理和网络延迟的时间范围。

即使不访问物理时钟，我们也可以基于 the transmission and delivery of messages 来测量 the passage of time。这样测量的时间称为 logical time，这种时钟称为 logical clock。

下述算法可以用于测量 asynchronous distributed system 中的 logical time：

1. 每个 process p 维护一个整数，称为 logical clock l_p，初始值为 0。
2. process p 处理一个 event，logical clock l_p 自增一个单元。
3. 发送 message 时，process 通过 logical clock 获取时间戳附加在消息中，event e 的时间戳标记为 t(e)。
4. 当 process p 收到消息 m，其中时间戳为 t_m，那么 p 以这种方式更新 logical clock：l_p := max{l_p, t_m} + 1。

logical clock 表现了 cause–effect relations，我们称 e₁ 潜在地引发了 event e₂，标记为 e₁ → e₂，那么下述条件也满足：

1. e₁ 和 e₂ 发生在同一 process p 中，那么 e₁ 在 e₂ 之前发生；
2. 如果 e₁ 对应 p 发送消息 m，那么 e₂ 对应 q 接收消息 m；
3. 存在某些 event e'，使得 e₁ → e' 并且 e' → e₂。

这里定义的潜在的因果关系称为 happened-before relation，e₁ → e₂ ⇒ t(e₁) < t(e₂)，但是逆命题不为真。

即使没有物理时钟的假设，我们也可以使用逻辑时钟实现某些分布式编程抽象。但是也有一些抽象需要物理时钟假设。

即使只有一个 process 故障，也无法在 asynchronous system 中实现 consensus。

2.5.2 Synchronous System

synchronous system 假设了下述属性：

1. Synchronous computation. 明确知道 process 处理延迟的上限，也就是 process 每 step 的耗时小于这个限制。
2. Synchronous communication. 明确知道网络传输延迟的上限。
3. Synchronous physical clocks. 每个 process 持有本地物理时钟，本地时钟与 global real-time clock 之间的时间差具有明确的上限。

在同步系统中可以提供许多有用的服务：

• Timed failure detection. Every crash of a process may be detected within bounded
  time.
• Measure of transit delays. It is possible to get a good approximation of the delays of messages in the communication links and, from there, infer which nodes are more distant or connected by slower or overloaded links.
• Coordination based on time. One can implement a lease abstraction that provides the right to execute some action during a fixed time period. The right expires automatically at the end of the time period.
• Worst-case performance. By assuming a bound on the number of faults and on the load of the system, it is possible to derive worst-case response times for any given algorithm.
• Synchronized clocks. A synchronous system makes it possible to synchronize the clocks of the different processes in such a way that they are never apart by more than some known constant δ, called the clock synchronization precision.

同步系统模型的主要限制是模型的 coverage，也就是构建一个维持时间假设的系统很困难。

2.5.3 Partial Synchrony

通常来说，分布式系统都是同步的，也就说大部分操作都在有限的物理时间范围内。但是也存在大量的异常情况，比如说网络负载过高，消息缓冲溢出等，造成消息丢失，重传机制可以增加可靠性，但是耗时范围就无法预期了。现实中的系统是 partially synchronous 的。

假设系统是 eventually synchronous 的，系统并不总是同步的，也会存在时间无法预期的异步阶段，但是可以假设系统在一段时间内是同步的，而这段时间对于算法来说足够长。