Skip to content

异步系统

Asynchronous distributed system

消息延迟和进程相对速度没有已知有限上界的系统模型。

形式陈述

异步分布式系统不假设存在已知常数同时上界进程执行速度、消息传输延迟或相邻步骤间隔。一次执行是满足组件局部转移规则及所选公平性、可靠性条件的事件序列;“异步”本身不等同于消息丢失或进程故障。

直觉

算法无法仅凭等待时间判断对方是崩溃还是只是极慢。模型刻意隐藏全局时钟与固定节拍,从而捕捉网络延迟和调度不可预测性。

例子与边界

可靠异步消息传递可保证每条发给正确接收者的消息最终送达,却允许延迟任意长。一个永远不调度某进程的执行是否允许,由公平性假设决定。把“无已知上界”写成“消息永不送达”会混淆时间模型与通信故障模型。

推论与应用

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。