Передача сообщений и разделяемая память

Передача сообщений и разделяемая память — это две фундаментальные абстракции, посредством которых взаимодействуют параллельные процессы, и большая часть исследований в области распределенных вычислений посвящена тому, как имитировать одну абстракцию с помощью другой.

Definition

В модели передачи сообщений процессы обмениваются данными только путем отправки и получения сообщений по каналам; в модели разделяемой памяти они обмениваются данными путем чтения и записи разделяемых объектов, таких как регистры. Каждая из них является точной вычислительной моделью со своими собственными условиями корректности.

Scope

Эта тема охватывает модели передачи сообщений «точка-точка» и широковещательной рассылки с их семантикой доставки и упорядочивания, модели разделяемой памяти, построенные на регистрах чтения/записи и более сильных объектах синхронизации, а также классические результаты, показывающие, как разделяемая память может быть эмулирована поверх передачи сообщений (и наоборот) при различных предположениях о сбоях. Она также охватывает иерархию регистров и иерархию консенсуса, которые ранжируют мощность разделяемых объектов.

Core questions

• Какие гарантии доставки и упорядочивания предоставляет канал, и как они влияют на проектирование алгоритмов?
• Может ли абстракция разделяемой памяти быть надежно построена поверх ненадежной сети передачи сообщений?
• Как объекты синхронизации различаются по своей способности решать проблему консенсуса?

Key theories

Иерархия регистров и консенсуса

Разделяемые объекты ранжируются по их числу консенсуса — максимальному количеству процессов, для которых они могут решить консенсус без ожидания, — помещая простые регистры чтения/записи в нижнюю часть и универсальные объекты, такие как compare-and-swap, в верхнюю.

Конструкции регистров

Иерархия безопасных, регулярных и атомарных регистров Лэмпорта, а также конструкции, которые строят более сильные регистры из более слабых, точно формализуют, что означает корректное поведение параллельных операций чтения и записи.

Имитация разделяемой памяти поверх передачи сообщений

Атомарные регистры с одним записывающим устройством и с несколькими записывающими устройствами могут быть эмулированы поверх асинхронной сети передачи сообщений, допускающей меньшинство сбоев по типу «отказ-остановка», с использованием кворумных методов, объединяя две модели связи.

Clinical relevance

Различие между передачей сообщений и разделяемой памятью напрямую проецируется на реальные платформы: кластеры и облако являются системами передачи сообщений, многоядерные серверы предоставляют разделяемую память, а распределенные хранилища типа «ключ-значение» фактически представляют абстракцию разделяемого регистра поверх сети передачи сообщений.

History

Работы Лэмпорта 1986 года формализовали параллельные регистры; иерархия Херлихи без ожидания 1991 года ранжировала примитивы синхронизации по числу консенсуса; а текст Аттии и Уэлча объединил симуляции, связывающие передачу сообщений и разделяемую память, установив дуальность, лежащую в основе этой области.

Key figures

• Leslie Lamport
• Maurice Herlihy
• Nir Shavit
• Hagit Attiya
• Jennifer Welch

Seminal works

• herlihy2008
• attiya2004
• lamport1986

Frequently asked questions

Эквивалентны ли передача сообщений и разделяемая память?

Они эквивалентны по вычислительной мощности при соответствующих предположениях о сбоях — каждая может имитировать другую — но они резко различаются по удобству программирования и производительности, поэтому системы выбирают одну из них в качестве своей нативной модели.