Instantâneos Globais e Estado

Um instantâneo global captura uma visão consistente do estado de uma computação distribuída — o estado local de cada processo mais as mensagens em trânsito — sem congelar o sistema.

Definition

Um estado global consistente é uma coleção de estados de processos locais e conteúdos de canais correspondente a um corte consistente — um no qual, para cada recebimento de mensagem registrado, o envio correspondente também é registrado — de modo que o estado poderia ter surgido durante a computação, embora nenhum instante global tenha sido observado.

Scope

Este tópico abrange a noção de um estado global consistente e o corte que o define, o algoritmo de instantâneo baseado em marcadores de Chandy-Lamport e suas suposições (canais FIFO, entrega confiável), e a aplicação de instantâneos à detecção de propriedades estáveis, como detecção de terminação e deadlock, e ao checkpointing e recuperação distribuídos.

Core questions

• O que torna um estado global registrado consistente em vez de impossível?
• Como tal estado pode ser registrado enquanto a computação continua em execução?
• Como propriedades estáveis, como terminação e deadlock, são detectadas a partir de instantâneos?

Key theories

Cortes consistentes

Um estado global corresponde a um corte nas sequências de eventos dos processos; o corte é consistente exatamente quando é fechado sob a relação "aconteceu antes", garantindo que nenhuma mensagem seja recebida antes de ser enviada no estado registrado.

Algoritmo de instantâneo de Chandy-Lamport

Um iniciador registra seu estado e envia um marcador em cada canal de saída; cada processo, ao receber um marcador pela primeira vez, registra seu estado e então registra as mensagens de entrada em outros canais até que seus marcadores cheguem, capturando os conteúdos do canal.

Detecção de propriedades estáveis

Como os instantâneos capturam um estado em que o sistema poderia ter estado, qualquer propriedade estável (aquela que permanece verdadeira uma vez que se torna verdadeira, como terminação ou deadlock) detectada em um instantâneo é verdadeiramente válida, tornando os instantâneos uma ferramenta de detecção geral.

Clinical relevance

Algoritmos de instantâneo impulsionam o checkpoint/reinício distribuído para recuperação de falhas, incluindo o instantâneo assíncrono usado por motores modernos de processamento de fluxo para fornecer garantias de "exatamente uma vez", bem como a detecção de deadlock e terminação em computações de longa duração.

History

O algoritmo de Chandy e Lamport de 1985 forneceu o primeiro método prático para registrar um estado global consistente sem parar o sistema; Mattern e outros generalizaram a teoria de corte subjacente, e a técnica mais tarde tornou-se fundamental para o processamento de fluxo tolerante a falhas.

Key figures

• K. Mani Chandy
• Leslie Lamport
• Friedemann Mattern

Seminal works

• chandy1985
• mattern1989
• lynch1996

Frequently asked questions

A captura de um instantâneo exige a pausa do sistema?

Não. O algoritmo de Chandy-Lamport registra um estado global consistente enquanto a computação continua, propagando marcadores pelos canais; o estado registrado é um em que o sistema poderia ter estado, mesmo que nunca tenha sido globalmente interrompido.