2.4 Abstracting Communication

link 抽象用于描述分布式系统中的网络组件，两个 process 之间是双向连接的，并且系统中所有 process 是全联通的。

在 link 上交换的 message 都是唯一的，每个消息的接收方可以确定知道这个消息的发送方。

如果两个 process 以 request-reply 的方式交换消息，那么需要知道某个 response 是响应哪个 request，这可以通过 sequence number、local clocks 或者 source of randomness 生成唯一标识解决。

2.4.1 Link Failures

在分布式系统中，通过网络传输消息是有可能丢失的。但是如果不是网络故障，process 总是有可能收到消息的。处理网络丟消息最简单的方法是持续重发。

下面将会介绍五个 link 抽象，其中三个基于 crash-stop process abstraction，一个基于 crash-recovery abstraction，一个基于 Byzantine process abstraction。这些全都是 point-to-point link 抽象，Broadcast communication abstraction 将在下一章介绍。

首先介绍 fair-loss links 抽象，数据会丢失，但是数据不丢的概率不是零；然后通过重传机制实现更可靠的抽象，也就是 stubborn 和 perfect links 抽象。这三个抽象假设 crash-stop process abstraction。

logged perfect links 抽象可以处理 crash-recovery faults；authenticated links 抽象可以处理 arbitrary faults。

定义与 link abstractions 交互的两种 events：a Send request event to send a message and a Deliver indication event that delivers a message。

When this event occurs on a process p for a message m, we say that p delivers m.

2.4.2 Fair-Loss Links

下述 Module 定义了 fair-loss links 抽象的接口：

fair-loss property 保证 link 不会系统性的丢掉每一条消息，如果发送方和接收方都正常，并且发送方继续重传消息，那么接收方最终会收到消息。

finite duplication property 保证网络不会重复执行更多次重传。

no creation property 保证网络不会创建或篡改消息。

2.4.3 Stubborn Links

这个抽象在 fair-loss 抽象的基础上隐藏了重传机制，使得消息最终会被接收方收到。

Algorithm: Retransmit Forever

这里假设了一个 timeout 服务，调用 starttimer 方法之后将会在给定延迟 Δ 之后收到一个 Timeout 事件。

Correctness. The fair-loss property of the underlying fair-loss links instance fll guarantees that, if the target process is correct, then every message that is sl-sent by every correct process will indeed be fll-delivered infinitely often by the target process. This is because the algorithm makes sure the sender process keeps fll-sending those messages infinitely often, unless the sender process itself crashes. The no creation property is simply preserved by the underlying links.

Performance. 这只是一个教学使用的算法，明显没有效率。有很多种方法可以使算法更实用：第一，无限这个词是上下文相关的，当算法不再使用这些 links 的时候，实际上就不需要重发了；第二，添加一个 acknowledgement mechanism 也是可以的。

2.4.4 Perfect Links

在 stubborn 抽象基础上添加去重机制。

Algorithm: Eliminate Duplicates.

Correctness. Consider the reliable delivery property of perfect links. Let m be any message pl-sent by some process p to some process q, and assume that these two processes are correct. According to the algorithm, process p sl-sends m to q using the underlying stubborn links abstraction sl. Because of the stubborn delivery property of that primitive, q eventually sl-delivers m, at least once, and hence pl-delivers m. The no duplication property follows from the test performed by the algorithm whenever a message is sl-delivered and before pl-delivering that message. The no creation property simply follows from the no creation property of the underlying stubborn links.