《Introduction to Reliable and Secure Distributed Programming》
本章主要内容是对分布式系统进行抽象建模
2.1 分布式计算
2.1.1 Processes and Messages
我们将分布式系统中执行计算的单元称为 process。
举个例子，一个分布式系统包含 N 个 process，分别命名为 p、q、r、s 等，那么所有 process 的集合标记为 Π，在此定义函数 rank : Π → {1, . . . , N }，为每个 process 分配唯一的序号。
在算法描述中，我们用 self 表示当前执行代码的 process。
在分布式系统中，process 执行相同的本地算法，所有这些 process 的总和构成了分布式算法。
process 之间通过交换 message 进行通信，每个消息都是唯一的。通信单元抽象为 link，后面再详细讨论。
2.1.2 Automata and Steps
A distributed algorithm consists of a distributed collection of automata, one per process.
每个 process 抽象为自动机，对 message 做出响应。分布式算法的执行可以描述为 process 执行的一系列 step。
我们假设存在一个 global clock，process 的 step 依赖全局时钟的 tick 执行，即使两个 step 是同时执行的，我们也将其看做在全局时钟的两个 tick 下执行的。
所以也需要假设存在一个 global scheduler，为每个 process 分配执行的时间单元。
如上图所示，某个 process 的 step 包含：
- receiving (sometimes we also say delivering) a message from another process (global event)
- executing a local computation (local event)
- sending a message to some process (global event)
存在两个特殊的情况：
- 有时候没有 message 接收或者发送，也需要执行一些本地计算，对于这种情况只需要假定 message 为 nil 即可。
- 有时候也不需要执行本地计算，此时假定 local computation 为 nil 即可。
需要注意一点，process 内不同 module 之间的交互做为本地计算看待，而不是通信。
process 内部不同 module 之间交互消息，执行本地计算称为 computation step；不同 process 之间交互消息，执行计算称为 communication step。
不同 step 的耗时假设将会在后面章节讨论。
默认情况下，我们讨论的是 deterministic algorithm，另外也会讨论 randomized/probabilistic algorithm。
2.1.3 Safety and Liveness
分布式算法需要满足分布式编程抽象的属性，确保系统可以正常工作。
这些属性可以分为两类：
Safety
简而言之，safety 属性声明算法不应该做错的事情。
More precisely, a safety property is a property such that, whenever it is violated in some execution E of an algorithm, there is a partial execution E′ of E such that the property will be violated in any extension of E′. This means that safety properties prevent a set of unwanted execution prefixes from occurring.
Liveness
简而言之，liveness 属性确保最终会发生的正确事情。
More precisely, a liveness property is a property of a distributed system execution such that, for any time t, there is some hope that the property can be satisfied at some time t′ ≥ t.
同时保证 safety 和 liveness 是很有挑战性的。
网友评论