Un reloj lógico es un mecanismo para capturar relaciones cronológicas y causales en un sistema distribuido . A menudo, los sistemas distribuidos pueden no tener un reloj global físicamente sincrónico. En muchas aplicaciones (como GNU make distribuido ), si dos procesos nunca interactúan, la falta de sincronización es inobservable y en estas aplicaciones es suficiente que los procesos acuerden el orden de los eventos (es decir, el reloj lógico) en lugar del tiempo del reloj de pared. [1] La primera implementación del reloj lógico, las marcas de tiempo de Lamport , fue propuesta por Leslie Lamport en 1978 ( Premio Turing en 2013).
En los sistemas de reloj lógico, cada proceso tiene dos estructuras de datos: tiempo local lógico y tiempo global lógico . El tiempo local lógico es utilizado por el proceso para marcar sus propios eventos, y el tiempo global lógico es la información local sobre el tiempo global. Se utiliza un protocolo especial para actualizar el tiempo local lógico después de cada evento local y el tiempo global lógico cuando los procesos intercambian datos. [2]
Los relojes lógicos son útiles en el análisis computacional, el diseño de algoritmos distribuidos, el seguimiento de eventos individuales y la exploración del progreso computacional.
Algunos algoritmos de reloj lógico dignos de mención son: