Problemas Básicos em Computação Distribuída

Em um sistema sem memória compartilhada, cada processo só vê os próprios eventos e as mensagens que recebe. Não há relógio global: dois processos podem discordar sobre quem ocorreu primeiro.

Relógios lógicos e físicos, exclusão mútua, difusão e eleição deste tópico — e consistência, transações e tolerância a falhas nos tópicos seguintes — partem desses eventos e mensagens.

As páginas se agrupam em cinco blocos. O primeiro decide influência: a relação acontece-antes (→), o relógio escalar de Lamport e o vetorial que distingue concorrente de causal.

O segundo alinha horário de parede: a transformação T = a·Cᵢ + b corrige deriva e deslocamento nos contadores locais.

O terceiro garante no máximo um processo na seção crítica, por coordenador central, anel de ficha ou Ricart–Agrawala.

O quarto entrega a mesma mensagem a um conjunto — unicast, multicast ou broadcast — com ordem FIFO, causal ou total e, quando confiável, atomicidade todos-ou-nenhum.

O quinto elege um coordenador após falha: Bully em O(n²) ou anel em O(n).

Quem pode ter influenciado quem, e se dois eventos são concorrentes, está em Coordenação e Sincronização. Quanto tempo de parede separa dois fatos, ou se um prazo já venceu, está em Sincronização de Relógios Físicos.

Construir Cᵢ e o vetor de carimbos é Coordenação e Sincronização. Usar o par (T, id) só para desempatar pedidos da seção crítica é Exclusão Mútua.

A relação → entre envios está em Coordenação e Sincronização. A ordem em que a camada entrega a cópia à aplicação — FIFO, causal ou total — está em Difusão de Mensagens.

Garantir ≤ 1 processo na seção crítica é Exclusão Mútua. Restaurar exatamente um coordenador entre os que ainda respondem é Eleição de Líder.