消息传递与共享内存
消息传递和共享内存是并发进程交互的两种基本抽象，分布式计算的许多研究都集中在如何用其中一种模拟另一种。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
在消息传递模型中，进程仅通过在通道上发送和接收消息进行通信；在共享内存模型中，它们通过读写共享对象（如寄存器）进行通信。每种模型都是一个精确的计算模型，具有自己的正确性条件。
Scope
本主题涵盖点对点和广播消息传递模型及其传递和排序语义，由读/写寄存器和更强的同步对象构建的共享内存模型，以及在各种故障假设下共享内存如何通过消息传递（反之亦然）进行模拟的经典结果。它还涵盖了寄存器层次结构和共识层次结构，这些层次结构对共享对象的效能进行了排序。
Core questions
- 通道提供哪些传递和排序保证，它们如何影响算法设计？
- 共享内存抽象能否在不可靠的消息传递网络之上可靠地构建？
- 同步对象在解决共识方面的能力有何不同？
Key theories
- 寄存器和共识层次结构
- 共享对象根据其共识数进行排序——它们可以解决无等待共识的最大进程数——将简单的读/写寄存器置于底部，将比较并交换（compare-and-swap）等通用对象置于顶部。
- 寄存器构造
- Lamport 的安全、常规和原子寄存器层次结构，以及从较弱寄存器构建较强寄存器的构造，精确地形式化了并发读写正确行为的含义。
- 通过消息传递模拟共享内存
- 原子单写入器和多写入器寄存器可以通过异步消息传递网络进行模拟，该网络通过法定人数技术容忍少数崩溃故障，从而统一了两种通信模型。
Clinical relevance
消息传递/共享内存的区别直接映射到实际平台：集群和云是消息传递系统，多核服务器暴露共享内存，分布式键值存储有效地在消息传递网络上呈现共享寄存器抽象。
History
Lamport 在 1986 年的论文中形式化了并发寄存器；Herlihy 在 1991 年的无等待层次结构根据共识数对同步原语进行了排序；Attiya 和 Welch 的著作整合了消息传递和共享内存相关的模拟，确立了该领域核心的二元性。
Key figures
- Leslie Lamport
- Maurice Herlihy
- Nir Shavit
- Hagit Attiya
- Jennifer Welch
Related topics
Seminal works
- herlihy2008
- attiya2004
- lamport1986
Frequently asked questions
- 消息传递和共享内存是否等效？
- 在适当的故障假设下，它们在计算能力上是等效的——彼此可以相互模拟——但它们在编程便利性和性能方面存在显著差异，这就是为什么系统会选择其中一种作为其原生模型。