IRSDP 读书笔记 - 2. Basic Abstractio

《Introduction to Reliable and Secure Distributed Programming》

2.6 Abstracting Time

2.6.1 Failure Detection

使用 failure detector 提供 process 停止或者正常的信息，并且运行这个信息不精确。

使用 failure detector 封装 synchronous system 的耗时假设和 partially synchronous system 的耗时假设。通常来说耗时假设越强，failure detector 提供的信息越精确。

使用 failure-detector abstraction 有两个优势：

1. failure-detector abstraction 替代了扩展前面定义的 process and link abstractions，保持了这些抽象的简洁性。
2. 可以使用不包含显式物理时间引用的公理属性讨论 failure detector 的行为。

除了像 process control 这样的应用程序，耗时假设主要用于 detect process failure。

failure detector 可以周期性请求 remote process 执行某个操作来检测 process 是否 crash 了。需要假设 observer process 与 remote process 之间的通信没有故障，并且是同步的。如果只会发生 crash 这种故障，当 observer 发现 remote process 停止执行操作了，那么可以得出 remote process 已经发生故障的结论。a failure detector for crash faults provides an accurate failure signal about a remote process if and only if the process stops behaving properly in an algorithm.

在 arbitrary-fault process abstraction 下实现 failure detector 就比较困难了，所以本书不会讨论这种情况。

2.6.2 Perfect Failure Detection

对于 synchronous system 中 crash-stop process abstraction，可以通过 timeout 精确检测 crash。

For instance, assume that a process sends a message to another process and awaits a response. If the recipient process does not crash then the response is guaranteed to arrive within a time period equal to the worst-case processing delay plus two times the worst-case message transmission delay (ignoring the clock drifts).

sender process 可以使用本地时钟测量最差延迟，这个时间范围内获取不到相应，就可以判断 crash 了。在 synchronous system 中这种检测故障的方式称为 perfect failure-detector abstraction。

Algorithm: Exclude on Timeout.

检测故障的时间依赖 timeout 延迟。比较大的 timeout 更可能处理延迟扩大大情况。然而为了更快检测出故障，可能设置较短的 timeout。但是这样错误识别故障的概率将会变大。处理这样的权衡的一个方式是假设不完美的 failure detector。

2.6.3 Leader Election

有时候不需要检测哪个 process 故障了，只需要识别出一个没有故障的 process 即可。这个 process 可以做为 leader 协调算法的执行。

仅仅在 crash-stop process abstractions 中讨论 leader-election abstraction，而在 crash-recovery and arbitrary-fault process abstractions 中无法构造。

Algorithm:MonarchicalLeaderElection.

2.6.4 Eventually Perfect Failure Detection

在 partially synchronous system 中将 timing assumptions 封装为 eventually perfect failure detector abstraction。

Algorithm: Increasing Timeout.

2.6.5 Eventual Leader Election

使用 eventually perfect failure detector abstraction 无法实现 leader-election abstraction，但是可以实现一个较弱的 eventual leader election abstraction，只保存 the uniqueness of the leader only eventually。这个抽象可以在 crash-recovery 和 arbitrary-fault process abstractions 中实现。

Algorithm: Monarchical Eventual Leader Detection. crash-stop process abstraction 下的实现。

Algorithm: Elect Lower Epoch. crash-recovery process abstraction 下的实现。

epoch number 记录 process 故障后恢复的次数。本算法的目标是选择最小 epoch 的 process。

The test uses a deterministic function select (·) that picks one process from candidates according to the following rule: it considers the process/epoch pairs in candidates with the lowest epoch number, selects the corresponding processes, and returns the process with the highest rank among them.

2.6.6 Byzantine Leader Election

最后讨论 Byzantine processes abstraction 中的 eventual leader-detector abstraction。

Algorithm:RotatingByzantineLeaderDetection.

N 表示系统中 process 的个数，其中最多有 f 个异常 process，假设 N > 3f，第 r 轮的 leader 由上述公式确定。

每个正常的 process 最终收到 N−f > 2f 个 COMPLAINT 消息才能替代当前的 leader。