Lamport Clocks

Resumen

Leslie Lamport propuso en 1978 un mecanismo simple para ordenar eventos en sistemas distribuidos: cada nodo mantiene un contador que incrementa con cada evento local, y cuando recibe un mensaje, ajusta su contador al máximo entre su valor actual y el del mensaje recibido, más uno.

El resultado es una relación happened-before: si A ocurrió antes que B, el timestamp de A es menor. Pero la inversa no siempre es cierta: timestamps iguales no implican orden. Para orden total, se agrega el ID del nodo como desempate. Lamport clocks son la base conceptual de los vector clocks y de algoritmos de consenso como Paxos.

Alcance y supuestos

Cubre Lamport clocks como mecanismo de ordenamiento lógico y su diferencia con vector clocks. Asume familiaridad con sistemas distribuidos.

Modelo mental

Una fila en la panadería con números. Cuando entrás, tomás un número. Si estás hablando por teléfono con alguien que ya está en la fila, ajustás tu número al de esa persona + 1. Los números no te dicen la hora exacta, pero sí quién llegó antes que quién.

Uso práctico

• ✅ Ordenamiento de eventos en logs distribuidos, bases de datos, sistemas de archivos.
• ❌ Detección de conflictos —ahí se usan vector clocks—.

Ejemplo trabajado: ordenar mensajes en un sistema de archivos distribuido

Tres clientes escriben archivos. Con Lamport clocks, el sistema puede ordenar las escrituras aunque los relojes físicos difieran. Si A escribe file.txt a las 10:00:01 y B lo modifica a las 10:00:00 (reloj atrasado), el Lamport clock corrige: A=5, B recibe A y ajusta a 6.

Evidencia

• El paper "Time, Clocks, and the Ordering of Events in a Distributed System" (Lamport, 1978) es uno de los más citados en ciencias de la computación.