Passagem de Mensagens e Memória Compartilhada

A passagem de mensagens e a memória compartilhada são as duas abstrações fundamentais através das quais processos concorrentes interagem, e grande parte da computação distribuída estuda como simular uma com a outra.

Definition

No modelo de passagem de mensagens, os processos se comunicam apenas enviando e recebendo mensagens através de canais; no modelo de memória compartilhada, eles se comunicam lendo e escrevendo objetos compartilhados, como registradores. Cada um é um modelo computacional preciso com suas próprias condições de correção.

Scope

Este tópico abrange modelos de passagem de mensagens ponto a ponto e broadcast com suas semânticas de entrega e ordenação, modelos de memória compartilhada construídos a partir de registradores de leitura/escrita e objetos de sincronização mais robustos, e os resultados clássicos que mostram como a memória compartilhada pode ser emulada sobre a passagem de mensagens (e vice-versa) sob várias suposições de falha. Também aborda a hierarquia de registradores e a hierarquia de consenso que classificam o poder dos objetos compartilhados.

Core questions

• Que garantias de entrega e ordenação um canal oferece, e como elas afetam o projeto do algoritmo?
• Uma abstração de memória compartilhada pode ser construída de forma confiável sobre uma rede de passagem de mensagens não confiável?
• Como os objetos de sincronização diferem em seu poder para resolver o consenso?

Key theories

Hierarquia de registradores e consenso

Objetos compartilhados são classificados pelo seu número de consenso — o número máximo de processos para os quais eles podem resolver consenso sem espera — colocando registradores simples de leitura/escrita na base e objetos universais como compare-and-swap no topo.

Construções de registradores

A hierarquia de Lamport de registradores seguros, regulares e atômicos, e as construções que edificam registradores mais robustos a partir de outros mais fracos, formalizam exatamente o que significa para leituras e escritas concorrentes se comportarem corretamente.

Simulando memória compartilhada sobre passagem de mensagens

Registradores atômicos de escritor único e multi-escritor podem ser emulados sobre uma rede assíncrona de passagem de mensagens tolerando uma minoria de falhas por queda usando técnicas de quórum, unificando os dois modelos de comunicação.

Clinical relevance

A distinção entre passagem de mensagens e memória compartilhada se traduz diretamente em plataformas reais: clusters e a nuvem são sistemas de passagem de mensagens, servidores multi-core expõem memória compartilhada, e armazenamentos distribuídos de chave-valor efetivamente apresentam uma abstração de registrador compartilhado sobre uma rede de passagem de mensagens.

History

Os artigos de Lamport de 1986 formalizaram os registradores concorrentes; a hierarquia sem espera de Herlihy em 1991 classificou as primitivas de sincronização pelo número de consenso; e o texto de Attiya e Welch consolidou as simulações que relacionam a passagem de mensagens e a memória compartilhada, estabelecendo a dualidade no cerne do campo.

Key figures

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

Seminal works

• herlihy2008
• attiya2004
• lamport1986

Frequently asked questions

Passagem de mensagens e memória compartilhada são equivalentes?

Eles são equivalentes em poder computacional sob suposições de falha adequadas — cada um pode simular o outro — mas diferem acentuadamente em conveniência de programação e desempenho, razão pela qual os sistemas escolhem um como seu modelo nativo.