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 síncrono. Afortunadamente, en muchas aplicaciones (como GNU distribuido ), si dos procesos nunca interactúan, la falta de sincronización es inobservable. Además, en estas aplicaciones, es suficiente que los procesos acuerden el orden de los eventos (es decir, el reloj lógico) en lugar de la hora del reloj de pared. [1] La primera implementación de reloj lógico, las marcas de tiempo de Lamport , fue propuesta por Leslie Lamport en 1978 ( Premio Turing en 2013).
Hora local vs global
En los sistemas de reloj lógico, cada proceso tiene dos estructuras de datos: hora local lógica y hora global lógica . El proceso utiliza la hora local lógica para marcar sus propios eventos, y la hora global lógica es la información local sobre la hora global. Se utiliza un protocolo especial para actualizar la hora local lógica después de cada evento local y la hora global lógica cuando los procesos intercambian datos. [2]
Aplicaciones
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.
Algoritmos
Algunos algoritmos de reloj lógico dignos de mención son:
- Marcas de tiempo de Lamport , que aumentan monótonamente los contadores de software.
- Relojes vectoriales , que permiten la ordenación parcial de eventos en un sistema distribuido.
- Vectores de versión , pedidos de réplicas, según actualizaciones, en un optimista sistema replicado .
- Relojes de matriz , una extensión de los relojes vectoriales que también contiene información sobre las vistas del sistema de otros procesos.
Referencias
- ^ "3ª edición de sistemas distribuidos (2017)" . DISTRIBUTED-SYSTEMS.NET . Consultado el 20 de marzo de 2021 .
- ^ Capítulo 3: Tiempo lógico // Ajay Kshemkalyani y Mukesh Singhal, Computación distribuida: principios, algoritmos y sistemas, Cambridge University Press, 2008
enlaces externos
- Tiempo Lógico del Sistema Distribuido // Roberto Baldoni, Silvia Bonomi. MIDLAB, Universidad Sapienza de Roma
- Capítulo 3: Tiempo lógico // Ajay Kshemkalyani y Mukesh Singhal, Computación distribuida: principios, algoritmos y sistemas, Cambridge University Press, 2008
- Sistemas distribuidos 06. Relojes lógicos // Paul Krzyzanowski, Universidad de Rutgers, otoño de 2014