Exclusão Mútua Distribuída e Eleição de Líder

Exclusão mútua e eleição de líder são problemas clássicos de coordenação: garantir que no máximo um processo acesse um recurso crítico e selecionar um único coordenador distinto entre pares.

Definition

A exclusão mútua distribuída garante que no máximo um processo por vez detenha um recurso compartilhado, assegurando o acesso eventual para todos os solicitantes; a eleição de líder seleciona deterministicamente exatamente um processo como coordenador, com todos os processos concordando com o resultado.

Scope

Este tópico abrange algoritmos de exclusão mútua baseados em permissão (algoritmo de carimbo de data/hora de Lamport, Ricart-Agrawala, abordagem de quorum de Maekawa) e algoritmos baseados em token, juntamente com sua complexidade de mensagem e propriedades de justiça; e algoritmos de eleição de líder para anéis (Chang-Roberts) e redes gerais (o algoritmo bully), incluindo suas suposições sobre identificadores e sincronia. Essas primitivas recorrem em serviços de coordenação e sistemas replicados.

Core questions

• Como os processos podem serializar o acesso a um recurso compartilhado usando apenas mensagens?
• Quais são as compensações de complexidade de mensagem e justiça entre esquemas baseados em permissão e baseados em token?
• Como um líder único é escolhido e como a eleição é reativada após a falha do líder?

Key theories

Exclusão mútua baseada em permissão

Algoritmos como Ricart-Agrawala ordenam as solicitações por carimbos de data/hora lógicos e concedem entrada assim que um solicitante recebe permissão de todos (ou de um quorum de) pares, alcançando justiça com custo de mensagem limitado por entrada de seção crítica.

Exclusão mútua baseada em token

Um token único circula ou é solicitado sob demanda, e apenas seu detentor pode entrar na seção crítica, reduzindo o tráfego de mensagens, mas exigindo mecanismos para regenerar um token perdido após falhas.

Eleição de líder

Algoritmos de eleição como Chang-Roberts para anéis e o algoritmo bully para redes gerais usam identificadores de processo para convergir em um único coordenador de mais alta prioridade que todos os processos corretos reconhecem.

Clinical relevance

A eleição de líder é invocada sempre que um sistema replicado deve escolher um primário ou coordenador, e o bloqueio distribuído generaliza a exclusão mútua; ambos são expostos como serviços centrais por sistemas de coordenação usados em toda a infraestrutura de nuvem.

History

O artigo de Lamport de 1978 sobre relógios lógicos introduziu um algoritmo de exclusão mútua baseado em carimbo de data/hora; Ricart e Agrawala o otimizaram em 1981, Maekawa introduziu quoruns logo depois, e o algoritmo bully de Garcia-Molina de 1982 formalizou a eleição de líder, dando ao campo seus algoritmos canônicos de coordenação.

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

Como a exclusão mútua distribuída difere de um bloqueio em uma única máquina?

Não há memória compartilhada ou gerenciador de bloqueio central para depender, então os processos devem coordenar puramente trocando mensagens e devem lidar explicitamente com atrasos e falhas de mensagens, o que um bloqueio de máquina única pode considerar garantido.