形式陈述
异步分布式系统不假设存在已知常数同时上界进程执行速度、消息传输延迟或相邻步骤间隔。一次执行是满足组件局部转移规则及所选公平性、可靠性条件的事件序列;“异步”本身不等同于消息丢失或进程故障。
直觉
算法无法仅凭等待时间判断对方是崩溃还是只是极慢。模型刻意隐藏全局时钟与固定节拍,从而捕捉网络延迟和调度不可预测性。
例子与边界
可靠异步消息传递可保证每条发给正确接收者的消息最终送达,却允许延迟任意长。一个永远不调度某进程的执行是否允许,由公平性假设决定。把“无已知上界”写成“消息永不送达”会混淆时间模型与通信故障模型。
推论与应用
FLP 不可能性、故障检测器和异步共识都依赖该模型。实际系统常通过超时、随机化或部分同步假设恢复可实现性,这些机制等于向纯异步模型加入额外信息。
参考资料
- Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996, Chapters 8 and 14。
- Hagit Attiya and Jennifer Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd ed., Wiley, 2004, Chapter 2。