Anotar el momento en el que pasa cada cosa dentro de un ordenador es relativamente fácil. Por un lado, todo ordenador incorpora un contador interno que calcula el paso de los segundos monitorizando la oscilación de cierto material (típicamente cristal de cuarzo). Por otro lado, y para resolver los pequeños desajustes del reloj interno, la hora local se sincroniza periódicamente con un servidor externo de referencia (mediante NTP).
No podemos siempre afirmar que la hora a la que se registra un evento es la real. Pongamos que un ordenador sincroniza la hora por NTP cada 3 segundos, y que su oscilador tiene un error de dos milisegundos por segundo. Un evento que ocurra 2 segundos más tarde de la sincronización podría estar anotado con un tiempo incorrecto por hasta 4 ms.
Esta circunstancia no es un problema si todo pasa en un único ordenador. Si todos los eventos toman como referencia el mismo reloj, podemos identificar fácilmente cuál ha pasado antes y cuál ha pasado después, aunque la hora exacta sea algo incorrecta. Sin embargo, todo se vuelve más complicado cuando utilizamos sistemas distribuidos.
Sin embardo, en sistemas distribuidos es inevitable que cada máquina tenga su propio reloj interno, con sus propios errores de oscilación e intervalos de sincronización. Por lo tanto, las horas a la que se registra cada evento dependerán del componente que los genera. En la práctica, un evento que ocurre immediatamente después de otro podría tener una anotación temporal menor, como ejemplifica el diagrama siguiente. A pesar de que el evento enviado por C es posterior al enviado por A, sus anotaciones temporales siguen el orden inverso.
Si queremos resolver conflictos en un sistema, volver hasta un estado anterior o sincronizar operaciones, es esencial saber qué evento ha ocurrido antes y cuál después. Los relojes de Lamport resuelven este problema en sistemas distribuidos, estableciendo un orden entre operaciones sobre máquinas con diferente hora interna.
Un reloj de Lamport no es ni una hora exacta ni un reloj compartido por todos los componentes. Es un contador numérico mantenido por cada componente independiente, que garantiza el orden global de los eventos desde la perspectiva local de cada propia máquina. El algoritmo para actualizar el contador sigue reglas sencillas:
- Un proceso incrementa su propio contador antes de cada evento.
- Cuando un proceso envía un mensaje, incluye el valor de su contador en el mensaje.
- Al recibir un mensaje, el proceso receptor actualiza su contador tomando el valor más alto entre su propio contador y el que incluye el propio mensaje.
De esta manera, cualquier evento B que ocurra más tarde que un evento A será anotado con una anotación temporal posterior (correcta o incorrecta, no nos importa para establecer un orden), sea cual sea la máquina que lo ejecuta. Al final resultará que Lamport también fabrica buenos relojes, aunque no claven la hora.
Leave a Reply