Passage de messages et mémoire partagée

Le passage de messages et la mémoire partagée sont les deux abstractions fondamentales par lesquelles les processus concurrents interagissent, et une grande partie de l'informatique distribuée étudie comment simuler l'une avec l'autre.

Definition

Dans le modèle de passage de messages, les processus communiquent uniquement en envoyant et en recevant des messages via des canaux ; dans le modèle de mémoire partagée, ils communiquent en lisant et en écrivant des objets partagés tels que des registres. Chacun est un modèle de calcul précis avec ses propres conditions de correction.

Scope

Ce sujet couvre les modèles de passage de messages point à point et de diffusion avec leurs sémantiques de livraison et d'ordonnancement, les modèles de mémoire partagée construits à partir de registres de lecture/écriture et d'objets de synchronisation plus robustes, ainsi que les résultats classiques montrant comment la mémoire partagée peut être émulée sur le passage de messages (et vice versa) sous diverses hypothèses de défaillance. Il aborde également la hiérarchie des registres et la hiérarchie du consensus qui classent la puissance des objets partagés.

Core questions

• Quelles garanties de livraison et d'ordonnancement un canal fournit-il, et comment affectent-elles la conception des algorithmes ?
• Une abstraction de mémoire partagée peut-elle être construite de manière fiable sur un réseau de passage de messages non fiable ?
• Comment les objets de synchronisation diffèrent-ils dans leur capacité à résoudre le consensus ?

Key theories

Hiérarchie des registres et du consensus

Les objets partagés sont classés par leur nombre de consensus — le nombre maximal de processus pour lesquels ils peuvent résoudre un consensus sans attente — plaçant les simples registres de lecture/écriture en bas et les objets universels tels que compare-and-swap en haut.

Constructions de registres

La hiérarchie de Lamport des registres sûrs, réguliers et atomiques, et les constructions qui bâtissent des registres plus robustes à partir de registres plus faibles, formalisent précisément ce que signifie pour des lectures et écritures concurrentes de se comporter correctement.

Simulation de la mémoire partagée sur le passage de messages

Les registres atomiques à écrivain unique et à écrivains multiples peuvent être émulés sur un réseau de passage de messages asynchrone tolérant une minorité de pannes par crash en utilisant des techniques de quorum, unifiant ainsi les deux modèles de communication.

Clinical relevance

La distinction passage de messages/mémoire partagée se transpose directement sur des plateformes réelles : les clusters et le cloud sont des systèmes à passage de messages, les serveurs multicœurs exposent de la mémoire partagée, et les bases de données clé-valeur distribuées présentent effectivement une abstraction de registre partagé sur un réseau à passage de messages.

History

Les articles de Lamport de 1986 ont formalisé les registres concurrents ; la hiérarchie sans attente de Herlihy en 1991 a classé les primitives de synchronisation par leur nombre de consensus ; et le texte d'Attiya et Welch a consolidé les simulations reliant le passage de messages et la mémoire partagée, établissant la dualité au cœur du domaine.

Key figures

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

Seminal works

• herlihy2008
• attiya2004
• lamport1986

Frequently asked questions

Le passage de messages et la mémoire partagée sont-ils équivalents ?

Ils sont équivalents en termes de puissance de calcul sous des hypothèses de défaillance appropriées — chacun peut simuler l'autre — mais ils diffèrent nettement en termes de commodité de programmation et de performance, c'est pourquoi les systèmes choisissent l'un comme modèle natif.