Paso de Mensajes y Memoria Compartida

El paso de mensajes y la memoria compartida son las dos abstracciones fundamentales a través de las cuales interactúan los procesos concurrentes, y gran parte de la computación distribuida estudia cómo simular una con la otra.

Definition

En el modelo de paso de mensajes, los procesos se comunican únicamente enviando y recibiendo mensajes a través de canales; en el modelo de memoria compartida, se comunican leyendo y escribiendo objetos compartidos como registros. Cada uno es un modelo computacional preciso con sus propias condiciones de corrección.

Scope

Este tema cubre los modelos de paso de mensajes punto a punto y de difusión con sus semánticas de entrega y ordenamiento, los modelos de memoria compartida construidos a partir de registros de lectura/escritura y objetos de sincronización más potentes, y los resultados clásicos que muestran cómo la memoria compartida puede emularse sobre el paso de mensajes (y viceversa) bajo diversas suposiciones de fallos. También cubre la jerarquía de registros y la jerarquía de consenso que clasifican el poder de los objetos compartidos.

Core questions

• ¿Qué garantías de entrega y ordenamiento proporciona un canal y cómo afectan al diseño del algoritmo?
• ¿Se puede construir de forma fiable una abstracción de memoria compartida sobre una red de paso de mensajes poco fiable?
• ¿Cómo difieren los objetos de sincronización en su capacidad para resolver el consenso?

Key theories

Jerarquía de registros y consenso

Los objetos compartidos se clasifican por su número de consenso —el número máximo de procesos para los que pueden resolver el consenso sin esperas—, situando los registros simples de lectura/escritura en la parte inferior y los objetos universales como compare-and-swap en la parte superior.

Construcciones de registros

La jerarquía de Lamport de registros seguros, regulares y atómicos, y las construcciones que construyen registros más potentes a partir de otros más débiles, formalizan exactamente lo que significa que las lecturas y escrituras concurrentes se comporten correctamente.

Simulación de memoria compartida sobre paso de mensajes

Los registros atómicos de un solo escritor y de múltiples escritores pueden emularse sobre una red asíncrona de paso de mensajes tolerando una minoría de fallos por caída utilizando técnicas de quórum, unificando los dos modelos de comunicación.

Clinical relevance

La distinción entre paso de mensajes y memoria compartida se mapea directamente a plataformas reales: los clústeres y la nube son sistemas de paso de mensajes, los servidores multinúcleo exponen memoria compartida y los almacenes de clave-valor distribuidos presentan eficazmente una abstracción de registro compartido sobre una red de paso de mensajes.

History

Los artículos de Lamport de 1986 formalizaron los registros concurrentes; la jerarquía sin esperas de Herlihy en 1991 clasificó las primitivas de sincronización por número de consenso; y el texto de Attiya y Welch consolidó las simulaciones que relacionan el paso de mensajes y la memoria compartida, estableciendo la dualidad en el corazón del campo.

Key figures

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

Seminal works

• herlihy2008
• attiya2004
• lamport1986

Frequently asked questions

¿Son equivalentes el paso de mensajes y la memoria compartida?

Son equivalentes en poder computacional bajo suposiciones de fallos adecuadas —cada uno puede simular al otro—, pero difieren drásticamente en la conveniencia de programación y el rendimiento, razón por la cual los sistemas eligen uno como su modelo nativo.