Relojes lógicos y físicos

Los relojes lógicos ordenan los eventos por causalidad sin referencia al tiempo real, mientras que la sincronización de relojes físicos mantiene los relojes de tiempo real de máquinas separadas muy próximos a pesar de la deriva.

Definition

Un reloj lógico asigna a cada evento una marca de tiempo entera que es monótona a lo largo de cada proceso y aumenta a través de la comunicación, capturando el orden causal; la sincronización de relojes físicos es el proceso de ajustar los relojes de hardware de las máquinas para que marquen aproximadamente el mismo tiempo real.

Scope

Este tema abarca los relojes lógicos (escalares) de Lamport y la relación "sucedió antes" que respetan, la construcción de un orden total a partir de marcas de tiempo lógicas y la sincronización de relojes físicos: la limitación de la deriva, el intercambio de marcas de tiempo para estimar el desfase y los algoritmos (método de Cristian, algoritmo de Berkeley, NTP) utilizados en la práctica. Contrasta cuándo el tiempo lógico causal es suficiente y cuándo el tiempo real es realmente necesario.

Core questions

• ¿Cómo se pueden asignar marcas de tiempo para que respeten la relación causal "sucedió antes"?
• ¿Cómo se construye un orden total consistente de eventos a partir de relojes lógicos?
• ¿Qué tan cerca se pueden sincronizar los relojes físicos dada la variabilidad del retardo de red y la deriva?

Key theories

Relojes lógicos de Lamport

Cada proceso mantiene un contador que se incrementa en cada evento y se lleva en los mensajes; las marcas de tiempo resultantes respetan la relación "sucedió antes", y los empates resueltos por el identificador de proceso producen un orden total consistente con la causalidad.

Sincronización probabilística y de ida y vuelta

El método de Cristian estima un reloj remoto midiendo el tiempo de ida y vuelta y asumiendo un retardo simétrico, proporcionando límites probabilísticos sobre el error de sincronización alcanzable a través de una red.

Protocolo de tiempo de red

NTP organiza los servidores de tiempo en una jerarquía estratificada y utiliza el filtrado estadístico de mediciones de desfase repetidas para disciplinar los relojes en internet con una precisión de milisegundos.

Clinical relevance

Los relojes lógicos ordenan las operaciones en almacenes replicados y colas de mensajes sin depender del tiempo del reloj de pared, mientras que la sincronización física subyace a las bases de datos ordenadas por marca de tiempo, el rastreo distribuido y los protocolos de seguridad que dependen de un error de reloj limitado.

History

El artículo de Lamport de 1978 sobre relojes lógicos reformuló el tiempo en sistemas distribuidos como una noción causal en lugar de física; en paralelo, Cristian y otros desarrollaron la sincronización probabilística, y el NTP de Mills se convirtió en el mecanismo estándar para mantener alineados los relojes de internet.

Debates

Tiempo lógico versus tiempo físico para ordenar operaciones

Los relojes lógicos garantizan la corrección causal sin confiar en los relojes de hardware, pero no pueden relacionar eventos con el tiempo real; los relojes físicos permiten el razonamiento en tiempo real con el riesgo de un orden incorrecto cuando la deriva excede el retardo del mensaje, lo que motiva enfoques híbridos.

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

¿Si 'a' tiene una marca de tiempo de Lamport menor que 'b', 'a' ocurrió antes que 'b'?

No necesariamente; una marca de tiempo menor es consistente con la relación "sucedió antes", pero no la implica, porque los eventos concurrentes pueden recibir marcas de tiempo ordenadas. Para decidir la causalidad con precisión, se necesitan relojes vectoriales, no relojes lógicos escalares.