第一章 引言

1.1 相关主题

分布式算法分类依据的属性包括：

• 进程间通信（IPC，Interprocess communication），访问共享存储器、发送点对点或广播的消息（广域网/局域网）以及执行RPC
• 时序模型，一种极端情况是处理器完全同步（通信和计算在锁同步中进行），另一种极端情况是它们完全异步（任意的速度和次序运行），还有一种是部分同步（基于事件时序的部分信息）
• 故障模型，算法需容忍一定限度的故障行为（处理器故障/Byzantine故障/通信故障）。通信故障包括消息丢失或消息重复

上述问题：系统资源分配、通信、分布式处理器之间的一致性、数据库并发控制、死锁检测、全局快照、同步以及各种对象类型的实现等。

算法不确定性和行为独立性包括：

• 处理器数目未知
• 网络拓扑结构未知
• 不同位置上的独立输入
• 几个程序立即运行，在不同时间开始，以不同速度运行
• 处理器的不确定性
• 不确定的消息传递次数
• 不确定的消息顺序
• 处理器和通信故障

1.2 时序模型

• 同步模型，运行依照同步向前进行。在大部分分布式系统中，实现同步模型几乎不可能或者无效。
• 异步模型，不同部分以任意的顺序、按任意速度执行每一步。此模型主要涉及活性的考虑，并可忽略时序的问题。实现起来有通用和可移植性。但是不同高效解决问题的能力，有时候甚至不能解决。
• 部分同步（基于时序）模型，它是假设对事件的相对时序作一些限制，不像同步模型的锁机制。此方式最实际，但是难编程，但一定需保证时序假设的正确性。