IRSDP 读书笔记 - 1. Introduction

《Introduction to Reliable and Secure Distributed Programming》

1.1 动机

分布式系统是什么？

引用 Leslie Lamport 的名言：

A distributed system is one in which the failure of a computer you did not even know existed can render your own computer unusable.

多个进程协调成为一个整体，部分故障（partial failure）不影响整体。

The challenge in distributed computing is precisely to devise algorithms that provide the processes that remain operating with enough consistent information so that they can cooperate correctly and solve common tasks.

1.2 分布式编程抽象

为了更好的理解分布式系统，我们需要抽象。

system model

使用 process 和 link 描述物理系统，process 表示分布式系统中执行计算逻辑的实体，link 表示 process 之间通信的网络。

distributed agreement problem

• process 需要对身份、消息格式以及消息传递方式达成共识
• process 需要对消息的执行计划达成共识
• atomic commitment problem
• total-order broadcast problem

1.3 讨论

抽象很有用，但是实现很困难。

Distributed programming abstractions are useful but may sometimes be difficult or expensive to implement. In some cases, no simple algorithm is able to provide the desired abstraction and the algorithm that solves the problem can have a high complexity, e.g., in terms of the number of interprocess communication steps and messages. Therefore, depending on the system model, the network characteristics, and the required quality of service, the overhead of the abstraction can range from the negligible to the almost prohibitive.

1.4 软件组件

1.4.1 Composition Model

定义一种描述分布式算法的抽象模型。

一个例子

这是一个 asynchronous event-based composition model：

1. 每个 process 包含一组 software component，称为 module
2. 每个 component 有一个名字做为标识，以及一组属性
3. component 提供接收 event 和输出 event 的接口

每个 component 可以构建为一个 state-machine，根据接收到的 event 触发状态转移。

在本地 component 之间 event 以先进先出（FIFO）的顺序传递。

在下述例子中，component co₁ 包含两个 handler：

有时候也需要对内部条件做出响应：

有时候对外部事件做出响应时，也需要考虑本地条件：

1.4.2 编程接口

component 的 API 包含两类 event —— request 和 indication

以这个广播的抽象为例：

1. 收到来自上层的 request 事件，就会触发消息广播逻辑
2. 为了满足广播抽象的属性，该层通过向下一层发送 request 事件触发消息发送
3. 收到来自下层的 indication 事件，就表示收到了其他 process 的广播消息
4. 收到消息之后暂时存储下来，以满足可靠性的需求，满足条件之后通过向上层发送 indication 事件传递消息

1.4.3 Module

在此以一个简单的 job handler 抽象为例介绍 module 的描述方式。

接收 Submit 事件，返回 Confirm 确认事件。

算法 1.1 是同步实现，因为是在 job 处理完后才触发 Confirm。

算法 1.2 是异步实现。

为了展示 module 是如何组合的，在此增加 transformation handler

对于 transformation 失败的 job 返回 Error 事件。

1.5 算法的分类

可以通过故障假设对分布式算法分类：

1. fail-stop algorithms，process 发生故障并且停止，而且其它 process 可以可靠地检测到故障；
2. fail-silent algorithms，process 发生故障，但是不能被可靠地检测到；
3. fail-noisy algorithms，process 发生故障并且停止，其它 process 可以检测到，但是无法准确检测；
4. fail-recovery algorithms，process 发生故障停止，但是稍后会自动恢复；
5. fail-arbitrary algorithms，process 会产生恶意行为；
6. randomized algorithms，process 会产生随机性行为；

需要注意的是，某些抽象在某种故障假设中是可以实现的，并不意味着在其它故障假设中也可以实现。