消息排序和多播
组通信以指定的可靠性和排序保证向一组进程传递消息，范围从FIFO到因果再到全序。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
多播将单个消息传递给进程组的每个成员；排序保证限制了消息的相对传递顺序，其中FIFO保留了每个发送方的顺序，因果保留了“先发生”顺序，而全序则以相同的序列在每个成员处传递所有消息。
Scope
本主题涵盖可靠多播和传递排序的层次结构——FIFO、因果和全序（原子）——它们使用序列号、逻辑时钟和序列器或令牌方案的实现，以及将有序多播与一致的组成员变更集成的虚拟同步模型。全序（原子）广播被证明在能力上等同于共识。
Core questions
- 应用程序需要组通信提供哪些可靠性和排序保证？
- 如何有效地实现因果和全序传递？
- 为什么全序广播等同于共识？
Key theories
- 排序层次结构
- 传递排序形成一个层次结构——FIFO弱于因果，因果弱于全序——每个都通过额外的元数据（如每个发送方的序列号、向量时间戳或全局一致的序列）来强制执行。
- 虚拟同步
- 虚拟同步以一致的顺序向所有成员呈现组成员变更和多播消息，以便进程看到相同的事件序列和视图变更，从而简化了复制服务的构建。
- 原子广播等同于共识
- 全序（原子）广播和共识可以相互归约，因此任何一个问题的解决方案都可以产生另一个问题的解决方案，并且两者在异步和故障下的可解性限制相同。
Clinical relevance
有序、可靠的多播是状态机复制、发布-订阅系统和复制数据库的基础，在这些系统中，每个副本必须以相同的顺序应用相同的更新以保持一致性。
History
Birman和Joseph在20世纪80年代通过ISIS系统引入了虚拟同步和有序多播；原子广播和共识之间的关系在20世纪90年代得到阐明，Defago、Schiper和Urban在2004年的调查系统化了许多全序算法。
Key figures
- Kenneth Birman
- Thomas Joseph
- Andre Schiper
- Leslie Lamport
Related topics
Seminal works
- birman1987
- defago2004
- lamport1978
Frequently asked questions
- 因果排序和全序排序有什么区别？
- 因果排序只约束因果相关的消息，允许并发消息在不同进程以不同顺序传递。全序排序要求每个进程以相同的序列传递所有消息，这严格来说更强，并且与共识一样困难。