Relógios Lógicos e Físicos

Relógios lógicos ordenam eventos por causalidade sem referência ao tempo real, enquanto a sincronização de relógios físicos mantém os relógios de tempo real de máquinas separadas próximos, apesar da deriva.

Definition

Um relógio lógico atribui a cada evento um carimbo de tempo inteiro que é monotônico ao longo de cada processo e aumenta através da comunicação, capturando a ordem causal; a sincronização de relógios físicos é o processo de ajustar os relógios de hardware das máquinas para que leiam aproximadamente o mesmo tempo real.

Scope

Este tópico aborda os relógios lógicos (escalares) de Lamport e a relação 'aconteceu-antes' que eles respeitam, a construção de uma ordem total a partir de carimbos de tempo lógicos e a sincronização de relógios físicos — limitando a deriva, trocando carimbos de tempo para estimar o desvio e os algoritmos (método de Cristian, algoritmo de Berkeley, NTP) usados na prática. Contrapõe quando o tempo lógico causal é suficiente e quando o tempo real é genuinamente necessário.

Core questions

• Como os carimbos de tempo podem ser atribuídos de modo a respeitar a relação causal 'aconteceu-antes'?
• Como uma ordem total consistente de eventos é construída a partir de relógios lógicos?
• Quão próximos os relógios físicos podem ser sincronizados, dada a variabilidade do atraso e da deriva da rede?

Key theories

Relógios lógicos de Lamport

Cada processo mantém um contador incrementado em cada evento e transportado em mensagens; os carimbos de tempo resultantes respeitam a relação 'aconteceu-antes', e os desempates por identificador de processo produzem uma ordem total consistente com a causalidade.

Sincronização probabilística e de ida e volta

O método de Cristian estima um relógio remoto medindo o tempo de ida e volta e assumindo atraso simétrico, fornecendo limites probabilísticos para o erro de sincronização alcançável em uma rede.

Network Time Protocol

O NTP organiza servidores de tempo em uma hierarquia estratificada e usa filtragem estatística de medições repetidas de desvio para disciplinar relógios em toda a internet com precisão de milissegundos.

Clinical relevance

Relógios lógicos ordenam operações em armazenamentos replicados e filas de mensagens sem confiar no tempo do relógio de parede, enquanto a sincronização física sustenta bancos de dados ordenados por carimbo de tempo, rastreamento distribuído e protocolos de segurança que dependem de erro de relógio limitado.

History

O artigo de Lamport de 1978 sobre relógios lógicos reformulou o tempo em sistemas distribuídos como uma noção causal, e não física; em paralelo, Cristian e outros desenvolveram a sincronização probabilística, e o NTP de Mills tornou-se o mecanismo padrão para manter os relógios da internet alinhados.

Debates

Tempo lógico versus físico para ordenação de operações

Relógios lógicos garantem correção causal sem confiar em relógios de hardware, mas não podem relacionar eventos ao tempo real; relógios físicos permitem o raciocínio em tempo real com o risco de ordenação incorreta quando a deriva excede o atraso da mensagem, motivando abordagens híbridas.

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

Se 'a' tem um carimbo de tempo de Lamport menor que 'b', 'a' aconteceu antes de 'b'?

Não necessariamente — um carimbo de tempo menor é consistente com 'aconteceu-antes', mas não o implica, porque eventos concorrentes podem receber carimbos de tempo ordenados. Para decidir a causalidade com precisão, são necessários relógios vetoriais, não relógios lógicos escalares.