分布式高可用算法

11 结束语

10.5 实时操作系统的意义

10.4 时钟同步与网络同步的等价性

10.3.2 停止型失败算法

10.3.1 定义

10.3 基于网络同步的虚拟时钟

10.2.2 最终完美失败检测

10.2.1 完美失败检测

10.2 基于时钟同步的失败检测

10.1 包含时钟的时间假设

10 基于时钟的算法

9.7.3 停止型失败算法：基于可停止全序广播

9.7.2 定义

9.7.1 进程的加入和离开

9.7 可重配复制状态机

9.6.2 停止型失败算法：基于共识的可停止全序广播

9.6.1 定义

9.6 可停止全序广播

9.5.2 停止型失败算法：基于共识的组成员关系

9.5.1 定义

9.5 组成员关系

9.4.3 停止型失败算法：基于共识的非阻塞式原子提交

9.4.2 定义

9.4.1 介绍

9.4 原子提交

9.3.2 算法：基于全序广播的信号量

9.3.1 定义

9.3 信号量

9.2.2 算法：基于全序广播的状态复制

9.2.1 定义

9.2 复制状态机

9.1.2 算法：基于共识的全序广播

9.1.1 定义

9.1 全序广播

9 共识的应用

8.8.4 Multi-Paxos和Raft协议

8.8.3 噪音型失败算法

8.8.2 代次序列共识

8.8.1 概述

8.8 适用于噪音型失败模型的统一序列共识

8.7.3 基于单值共识的算法

8.7.2 定义

8.7.1 概述

8.7 统一序列共识

8.6.2 静音型失败算法

8.6.1 定义

8.6 统一快速共识

8.5.4 静音型失败算法：随机多值正则共识

8.5.3 静音型失败算法：随机二值正则共识

8.5.2 共币

8.5.1 定义

8.5 随机共识

8.4.4 恢复型失败算法

8.4.3 日志代次共识

8.4.2 日志代次变更

8.4.1 定义

8.4 日志统一共识

8.3.5 Paxos协议

8.3.4 噪音型失败算法

8.3.3 代次共识

8.3.2 代次变更

8.3.1 概述

8.3 适用于噪音型失败模型的统一共识

8.2.3 停止型失败算法：等级统一共识

8.2.2 停止型失败算法：泛洪统一共识

8.2.1 定义

8.2 统一共识

8.1.3 停止型失败算法：等级共识

8.1.2 停止型失败算法：泛洪共识

8.1.1 定义

8.1 正则共识

8 共识

7.8 CAP理论

7.7 因果注册器和先进先出注册器

7.6.4 静音型失败算法

7.6.3 叠加性

7.6.2 正则、顺序与原子注册器的比较

7.6.1 定义

7.6 （N-N）顺序注册器

7.5.3 恢复型失败算法

7.5.2 定义

7.5.1 操作顺序

7.5 （1-N）日志正则注册器

7.4.3 静音型失败算法

7.4.2 停止型失败算法

7.4.1 定义

7.4 （N-N）原子注册器

7.3.3 静音型失败算法

7.3.2 停止型失败算法

7.3.1 定义

7.3 （1-N）原子注册器

7.2.3 静音型失败算法

7.2.2 停止型失败算法

7.2.1 定义

7.2 （1-N）正则注册器

7.1.3 操作失败

7.1.2 操作顺序

7.1.1 前提假设

7.1 介绍

7 共享内存

6.7.4 静音型失败算法：基于向量时间

6.7.3 停止型失败算法

6.7.2 静音型失败算法

6.7.1 定义

6.7 因果可靠广播

6.6.2 静音型失败算法

6.6.1 定义

6.6 先进先出广播

6.5.3 随机化算法：推拉结合

6.5.2 随机化算法：尽力推送

6.5.1 定义

6.5 概率广播

6.4.2 恢复型失败算法

6.4.1 定义

6.4 顽固广播

6.3.3 静音型失败算法

6.3.2 停止型失败算法

6.3.1 定义

6.3 统一可靠广播

6.2.3 静音型失败算法

6.2.2 停止型失败算法

6.2.1 定义

6.2 正则可靠广播

6.1.2 静音型失败算法

6.1.1 定义

6.1 尽力广播

6 可靠广播

5.5.3 恢复失败型算法

5.5.2 噪音型失败算法

5.5.1 定义

5.5 最终选主

5.4.2 停止型失败算法

5.4.1 定义

5.4 选主

5.3.2 噪音型失败算法

5.3.1 定义

5.3 最终完美失败检测

5.2.2 停止型失败算法

5.2.1 定义

5.2 完美失败检测

5.1 失败检测

5 失败检测和选主

4.6 其他说明

4.5.2 恢复型失败算法

4.5.1 定义

4.5 日志可靠链路

4.4.2 静音型失败算法

4.4.1 定义

4.4 先进先出可靠链路

4.3.2 静音型失败算法

4.3.1 定义

4.3 可靠链路

4.2.2 静音型失败算法

4.2.1 定义

4.2 顽固链路

4.1.2 消息系统

4.1.1 定义

4.1 公平丢包链路

4 链路

3.10 性能度量

3.9 多数派

3.8 组合模型

3.7 安全性和活性

3.6.3 部分同步系统

3.6.2 同步系统

3.6.1 异步系统

3.6 时间假设

3.5.4 时钟偏移

3.5.3 逻辑时钟

3.5.2 因果顺序不变

3.5.1 本地时钟和全局时钟

3.5 时钟

3.4.5 各种失败的关系

3.4.4 拜占庭失败

3.4.3 恢复后崩溃失败

3.4.2 遗漏式失败

3.4.1 崩溃式失败

3.4 进程失败

3.3 进程启动

3.2 消息

3.1 进程

3 系统模型

2.2.3 抽象和实现

2.2.2 事件和事件处理器

2.2.1 调用关系

2.2 编程模型

2.1.5 小结

2.1.4 与业务逻辑的关系

2.1.3 隐藏操作

2.1.2 组合模型

2.1.1 基本模型

2.1 I/O自动机

2 算法模型

1.4.3 链路失败

1.4.2 进程失败

1.4.1 并发执行

1.4 设计分布式算法的主要挑战

1.3 “两将军”问题

1.2 分布式算法的意义

1.1 什么是分布式系统

1 初识分布式

前言

好评来袭

序三

序二

序一

其他

内容简介

作者简介

版权信息

封面

封面

版权信息

作者简介

内容简介

其他

序一

序二

序三

好评来袭

前言

1 初识分布式

1.1 什么是分布式系统

1.2 分布式算法的意义

1.3 “两将军”问题

1.4 设计分布式算法的主要挑战

1.4.1 并发执行

1.4.2 进程失败

1.4.3 链路失败

2 算法模型

2.1 I/O自动机

2.1.1 基本模型

2.1.2 组合模型

2.1.3 隐藏操作

2.1.4 与业务逻辑的关系

2.1.5 小结

2.2 编程模型

2.2.1 调用关系

2.2.2 事件和事件处理器

2.2.3 抽象和实现

3 系统模型

3.1 进程

3.2 消息

3.3 进程启动

3.4 进程失败

3.4.1 崩溃式失败

3.4.2 遗漏式失败

3.4.3 恢复后崩溃失败

3.4.4 拜占庭失败

3.4.5 各种失败的关系

3.5 时钟

3.5.1 本地时钟和全局时钟

3.5.2 因果顺序不变

3.5.3 逻辑时钟

3.5.4 时钟偏移

3.6 时间假设

3.6.1 异步系统

3.6.2 同步系统

3.6.3 部分同步系统

3.7 安全性和活性

3.8 组合模型

3.9 多数派

3.10 性能度量

4 链路

4.1 公平丢包链路

4.1.1 定义

4.1.2 消息系统

4.2 顽固链路

4.2.1 定义

4.2.2 静音型失败算法

4.3 可靠链路

4.3.1 定义

4.3.2 静音型失败算法

4.4 先进先出可靠链路

4.4.1 定义

4.4.2 静音型失败算法

4.5 日志可靠链路

4.5.1 定义

4.5.2 恢复型失败算法

4.6 其他说明

5 失败检测和选主

5.1 失败检测

5.2 完美失败检测

5.2.1 定义

5.2.2 停止型失败算法

5.3 最终完美失败检测

5.3.1 定义

5.3.2 噪音型失败算法

5.4 选主

5.4.1 定义

5.4.2 停止型失败算法

5.5 最终选主

5.5.1 定义

5.5.2 噪音型失败算法

5.5.3 恢复失败型算法

6 可靠广播

6.1 尽力广播

6.1.1 定义

6.1.2 静音型失败算法

6.2 正则可靠广播

6.2.1 定义

6.2.2 停止型失败算法

6.2.3 静音型失败算法

6.3 统一可靠广播

6.3.1 定义

6.3.2 停止型失败算法

6.3.3 静音型失败算法

6.4 顽固广播

6.4.1 定义

6.4.2 恢复型失败算法

6.5 概率广播

6.5.1 定义

6.5.2 随机化算法：尽力推送

6.5.3 随机化算法：推拉结合

6.6 先进先出广播

6.6.1 定义

6.6.2 静音型失败算法

6.7 因果可靠广播

6.7.1 定义

6.7.2 静音型失败算法

6.7.3 停止型失败算法

6.7.4 静音型失败算法：基于向量时间

7 共享内存

7.1 介绍

7.1.1 前提假设

7.1.2 操作顺序

7.1.3 操作失败

7.2 （1-N）正则注册器

7.2.1 定义

7.2.2 停止型失败算法

7.2.3 静音型失败算法

7.3 （1-N）原子注册器

7.3.1 定义

7.3.2 停止型失败算法

7.3.3 静音型失败算法

7.4 （N-N）原子注册器

7.4.1 定义

7.4.2 停止型失败算法

7.4.3 静音型失败算法

7.5 （1-N）日志正则注册器

7.5.1 操作顺序

7.5.2 定义

7.5.3 恢复型失败算法

7.6 （N-N）顺序注册器

7.6.1 定义

7.6.2 正则、顺序与原子注册器的比较

7.6.3 叠加性

7.6.4 静音型失败算法

7.7 因果注册器和先进先出注册器

7.8 CAP理论

8 共识

8.1 正则共识

8.1.1 定义

8.1.2 停止型失败算法：泛洪共识

8.1.3 停止型失败算法：等级共识

8.2 统一共识

8.2.1 定义

8.2.2 停止型失败算法：泛洪统一共识

8.2.3 停止型失败算法：等级统一共识

8.3 适用于噪音型失败模型的统一共识

8.3.1 概述

8.3.2 代次变更

8.3.3 代次共识

8.3.4 噪音型失败算法

8.3.5 Paxos协议

8.4 日志统一共识

8.4.1 定义

8.4.2 日志代次变更

8.4.3 日志代次共识

8.4.4 恢复型失败算法

8.5 随机共识

8.5.1 定义

8.5.2 共币

8.5.3 静音型失败算法：随机二值正则共识

8.5.4 静音型失败算法：随机多值正则共识

8.6 统一快速共识

8.6.1 定义

8.6.2 静音型失败算法

8.7 统一序列共识

8.7.1 概述

8.7.2 定义

8.7.3 基于单值共识的算法

8.8 适用于噪音型失败模型的统一序列共识

8.8.1 概述

8.8.2 代次序列共识

8.8.3 噪音型失败算法

8.8.4 Multi-Paxos和Raft协议

9 共识的应用

9.1 全序广播

9.1.1 定义

9.1.2 算法：基于共识的全序广播

9.2 复制状态机

9.2.1 定义

9.2.2 算法：基于全序广播的状态复制

9.3 信号量

9.3.1 定义

9.3.2 算法：基于全序广播的信号量

9.4 原子提交

9.4.1 介绍

9.4.2 定义

9.4.3 停止型失败算法：基于共识的非阻塞式原子提交

9.5 组成员关系

9.5.1 定义

9.5.2 停止型失败算法：基于共识的组成员关系

9.6 可停止全序广播

9.6.1 定义

9.6.2 停止型失败算法：基于共识的可停止全序广播

9.7 可重配复制状态机

9.7.1 进程的加入和离开

9.7.2 定义

9.7.3 停止型失败算法：基于可停止全序广播

10 基于时钟的算法

10.1 包含时钟的时间假设

10.2 基于时钟同步的失败检测

10.2.1 完美失败检测

10.2.2 最终完美失败检测

10.3 基于网络同步的虚拟时钟

10.3.1 定义

10.3.2 停止型失败算法

10.4 时钟同步与网络同步的等价性

10.5 实时操作系统的意义

11 结束语