Tempo e Estado Global
Tempo e estado global referem-se a como um sistema distribuído ordena eventos e raciocina sobre sua condição coletiva quando não há um relógio compartilhado e nenhuma visão global instantânea.
Definition
Em um sistema distribuído, os eventos ocorrem em processos separados sem um relógio compartilhado; o estudo do tempo e do estado global fornece as relações e algoritmos — relógios lógicos e vetoriais, instantâneos e entrega ordenada — que permitem ao sistema ordenar eventos causalmente e capturar estados globais consistentes.
Scope
Esta área abrange relógios lógicos e a relação 'aconteceu-antes', sincronização de relógios físicos, relógios vetoriais e a detecção de causalidade e concorrência, a determinação de instantâneos globais consistentes e as garantias de ordenação (FIFO, causal, total) necessárias para multicast confiável. Juntas, essas ferramentas permitem que sistemas distribuídos façam afirmações significativas sobre 'quando' e 'qual estado', apesar da ausência de um relógio global.
Sub-topics
Core questions
- Como eventos em diferentes processos podem ser ordenados sem um relógio físico compartilhado?
- Como um processo pode determinar se dois eventos estão causalmente relacionados ou são concorrentes?
- Como um instantâneo global consistente pode ser registrado enquanto a computação continua?
- Quais garantias de ordenação na entrega de mensagens são necessárias para preservar a causalidade?
Key theories
- Aconteceu-antes e relógios lógicos
- A relação 'aconteceu-antes' de Lamport define uma ordem causal parcial sobre eventos, e relógios lógicos (escalares) atribuem carimbos de tempo consistentes com ela, fornecendo uma noção de ordem independente de relógio suficiente para construir uma ordem total para muitos protocolos.
- Relógios vetoriais e causalidade
- Relógios vetoriais estendem os relógios lógicos para que a comparação de dois carimbos de tempo capture exatamente se um evento precede causalmente outro ou se os dois são concorrentes, permitindo o rastreamento preciso da causalidade.
- Instantâneos globais consistentes
- O algoritmo de instantâneo de Chandy-Lamport registra um estado global consistente — estados de processo mais mensagens em trânsito — sem interromper o sistema, propagando marcadores pelos canais.
Clinical relevance
Relógios lógicos e vetoriais sustentam a consistência causal, a detecção de conflitos em armazenamentos replicados e a depuração de execuções distribuídas; instantâneos consistentes sustentam o checkpointing distribuído, a detecção de deadlock e terminação, e a recuperação de falhas no processamento de fluxo.
History
O artigo de Lamport de 1978 introduziu o tempo lógico e a relação 'aconteceu-antes', um dos resultados mais citados na ciência da computação; Chandy e Lamport formalizaram instantâneos globais consistentes em 1985; e Fidge e Mattern desenvolveram independentemente relógios vetoriais no final da década de 1980, completando o conjunto de ferramentas fundamentais para raciocinar sobre tempo e estado.
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- Por que os sistemas distribuídos não podem simplesmente usar relógios físicos sincronizados?
- Relógios físicos sofrem desvio e não podem ser sincronizados perfeitamente em uma rede com atraso variável, de modo que a ordem em tempo real de dois eventos pode ser ambígua. Relógios lógicos e vetoriais, em vez disso, capturam a ordem causal que realmente importa para a correção.
- O que torna um instantâneo global 'consistente'?
- Um instantâneo é consistente se, sempre que incluir o recebimento de uma mensagem, também incluir o envio dessa mensagem. Tal estado poderia ter ocorrido durante a execução, embora nenhum instante único tenha sido observado globalmente.