Relojes de Lamport: un contador que no mide el tiempo

La relación de precedencia es correcta pero inmanejable: para responder si un evento precede a otro hay que guardar el grafo entero de eventos y recorrerlo, lo cual es inviable en cualquier sistema real. Lo que Lamport propone en su artículo de 1978, Time, Clocks, and the Ordering of Events in a Distributed System, publicado en Communications of the ACM 21, número 7, páginas 558 a 565, es una condensación radical de esa información: un único número entero por réplica, con dos reglas de actualización que caben en tres líneas de código. La compresión es brutal y, como toda compresión con pérdida, tiene un coste exacto que hay que conocer al detalle. La garantía que ofrece el resultado es una implicación en un solo sentido, y la mitad de los errores que se cometen con relojes lógicos consisten en usarla en el sentido contrario.

Un contador por réplica y dos reglas

Cada réplica mantiene un entero, inicializado a cero, que no representa ningún instante ni ninguna duración. Solo cuenta eventos, propios y heredados. Las reglas son dos y en el artículo aparecen como reglas de implementación del reloj.

La primera dice que la réplica incrementa su contador entre dos eventos sucesivos cualesquiera, de modo que ningún par de eventos de la misma réplica comparte valor y la secuencia local es estrictamente creciente. La segunda tiene dos mitades: al enviar un mensaje, la réplica adjunta el valor de su contador como marca del mensaje; y al recibirlo, ajusta su contador a un valor que sea a la vez mayor o igual que el que tenía y estrictamente mayor que el que traía el mensaje. La formulación habitual, el máximo de ambos más uno, es una manera concreta de cumplir esa segunda regla.

class RelojLamport {
  constructor(inicial = 0) {
    this.t = inicial;
  }

  // Evento local o envio de mensaje
  tic() {
    this.t += 1;
    return this.t;
  }

  // Recepcion de un mensaje con marca tm
  recibir(tm) {
    this.t = Math.max(this.t, tm) + 1;
    return this.t;
  }
}

Nótese que la clase no distingue entre un evento local y el envío de un mensaje: ambos son simplemente eventos y ambos incrementan el contador. Esa uniformidad no es una simplificación del ejemplo, sino la formulación correcta, porque la primera regla habla de eventos sucesivos sin importar su naturaleza y el envío es un evento como cualquier otro.

Lo primero que conviene notar es lo que ese código no hace: no habla con nadie, no consulta ningún servicio, no espera nada. Una réplica puede sellar diez mil eventos sin conexión y sin coordinarse con ninguna otra. Ese es el motivo por el que un mecanismo tan modesto sostiene arquitecturas enteras: es información de orden generada localmente y a coste nulo.

Lo segundo es que la regla de recepción es donde ocurre todo lo interesante. Al hacer el máximo, la réplica que recibe adopta el conocimiento del emisor: se coloca por delante de cualquier evento que el emisor hubiera contado, incluidos los que el emisor a su vez heredó de terceros. El contador deja así de describir la actividad de una réplica y pasa a describir cuánto ha llegado a saber, contando en la misma unidad los eventos propios y los que le fueron transmitidos.

flowchart LR
A0[Replica A contador 0] --> A1[Evento local contador 1]
A1 --> A2[Envio de mensaje con marca 2]
B0[Replica B contador 0] --> B1[Evento local contador 1]
B1 --> B2[Recibe marca 2 y toma el maximo mas uno igual a 3]
A2 --> B2
B2 --> B3[Evento local contador 4]
style B2 fill:#89b4fa,color:#11111b
style B3 fill:#a6e3a1,color:#11111b

Conviene detenerse en por qué la segunda regla exige superar estrictamente la marca recibida y no simplemente igualarla. Si el receptor se limitara a copiar el valor del mensaje, el evento de recepción tendría la misma marca que el evento de envío, y como el envío precede causalmente a la recepción se estaría violando la condición que se quiere garantizar. El incremento adicional es lo que mantiene la desigualdad estricta a través de la arista de mensaje, exactamente igual que el incremento local la mantiene a lo largo de la ejecución de cada réplica. Ninguno de los dos incrementos es decorativo: cada uno cubre uno de los dos tipos de arista del grafo causal.

También merece una lectura el hecho de que el valor resultante no admita ninguna interpretación temporal. Una réplica muy activa y aislada puede tener un contador altísimo, y otra que apenas ha escrito pero que acaba de recibir noticias de un grupo grande puede saltar de golpe a un valor mayor todavía. El número no mide antigüedad ni actividad: mide profundidad causal, la longitud del camino más largo de eventos que desemboca en este. Nombrar el campo con esa idea en mente, y no como si guardara una hora, evita que alguien lo muestre en la interfaz o lo reste de otro creyendo que obtiene una duración.

En el diagrama, la réplica B llevaba su propio contador en uno, recibe un mensaje marcado con dos y salta a tres. Ese salto no significa que haya pasado tiempo: significa que ahora sabe algo que antes no sabía, y que cualquier evento que produzca a partir de este instante llevará un número mayor que el del envío que lo informó.

La garantía, con su enunciado exacto

La propiedad que estas reglas aseguran es lo que el artículo llama la condición de reloj, y se enuncia en un solo sentido: si un evento precede causalmente a otro, entonces la marca del primero es estrictamente menor que la del segundo. En notación breve, la precedencia implica Ca < Cb, donde Ca y Cb son los valores que el reloj asignó a cada evento.

La demostración es corta y merece hacerse mentalmente, porque explica de dónde sale cada regla. Si los dos eventos están en la misma réplica, la primera regla garantiza el incremento y por tanto la desigualdad. Si el primero es un envío y el segundo su recepción, la segunda regla obliga al receptor a superar estrictamente la marca del mensaje. Y si hay una cadena de eventos intermedios, la desigualdad se propaga por transitividad a lo largo de toda la cadena. Cada regla cubre exactamente uno de los tres casos de la definición de precedencia, lo cual no es casualidad: las reglas se diseñaron para eso.

Hay un detalle de esa demostración que conviene no pasar por alto, porque delimita el alcance del resultado: la garantía se apoya por completo en que todos los eventos relevantes pasen por las reglas. Una operación que se guarde sin incrementar el contador, un mensaje que se envíe sin adjuntar la marca o una recepción que se procese sin aplicar el máximo abren un agujero por el que la condición de reloj deja de valer, y no de forma parcial sino para todos los pares que atraviesen ese punto. Es una propiedad global sostenida por una disciplina local, y por eso el sellado no puede quedar a criterio de cada punto de llamada: tiene que estar centralizado en la única función por la que pasen todas las escrituras.

De la condición de reloj se sigue de inmediato su forma contrapuesta, que es la que de verdad se usa en el código: si la marca de un evento es mayor o igual que la de otro, entonces ese otro no puede preceder causalmente al primero. Es una afirmación negativa y por eso resulta sólida: descarta con certeza, aunque no confirme nada.

Ese descarte, por modesto que parezca, es lo que sostiene la corrección de todo lo que viene después: permite afirmar sin riesgo que una operación no pudo haber tenido en cuenta a otra.

Lo que no garantiza, y es lo que confunde a todo el mundo

La implicación recíproca es falsa, y esto hay que grabarlo a fuego: que la marca de un evento sea menor que la de otro no implica que lo preceda causalmente. Dos réplicas que jamás se han comunicado producen contadores que crecen en paralelo, y sus valores se comparan perfectamente entre sí sin que exista relación alguna entre los eventos. Comparar 3 con 5 siempre da un resultado; el problema es que ese resultado no significa lo que uno quisiera que significase.

El origen del malentendido es que la comparación de enteros es un orden total y siempre responde, mientras que la relación que se quería representar es un orden parcial y a veces debería no responder. El reloj de Lamport aplasta esa distinción: un par ordenado causalmente y un par concurrente producen exactamente la misma clase de comparación numérica, y desde el número no hay manera de distinguirlos. La información sobre concurrencia se destruyó al comprimir el grafo en un solo entero, y ningún tratamiento posterior del número la recupera.

Otro modo de ver la misma pérdida es contar grados de libertad. El grafo causal contiene, para cada par de eventos, una de tres respuestas posibles: precede, sucede o es incomparable. Un entero solo puede representar dos de ellas, porque la comparación entre dos números tiene únicamente los resultados menor, mayor o igual, y el resultado igual ya está reservado para un caso muy poco frecuente. La información no se ha perdido por descuido en la implementación: no cabe. Cualquier mecanismo que quiera responder la tercera pregunta necesitará más espacio que un número, y esa necesidad de espacio, con su coste y sus estrategias para podarlo, es lo que estructura el nivel siguiente.

Hay, sin embargo, una deducción positiva que sí es válida y que suele pasarse por alto. Si dos eventos distintos tienen la misma marca, entonces son necesariamente concurrentes, y la razón es inmediata: si uno precediera al otro, la condición de reloj exigiría desigualdad estricta, luego la igualdad excluye la precedencia en ambos sentidos. Es el único dato de concurrencia que un reloj de Lamport regala, y es una fracción diminuta del total, porque la inmensa mayoría de los pares concurrentes tienen marcas distintas. Sirve para poco por sí solo, pero es útil recordarlo cuando aparecen empates, que es justo el asunto de la lección siguiente.

Cuándo basta y qué hace falta cuidar

Antes de la lista de cautelas conviene situar el mecanismo en su sitio, porque su fama de insuficiente es en parte injusta. Un reloj de Lamport no es un intento fallido de vector de versiones: es la respuesta óptima a una pregunta más modesta. Con un solo entero, sin coordinación y sin crecer nunca con el número de réplicas, entrega la única propiedad que hace falta para que dos réplicas cualesquiera lleguen al mismo estado cuando han visto lo mismo. Ningún mecanismo con ese coste ofrece más, y muchas estructuras no necesitan más.

Un reloj de Lamport es suficiente cuando lo que necesitas es un orden coherente para procesar operaciones, no una detección de conflictos. Si tu estructura de datos hace conmutativas todas las operaciones, o si aplicas actualizaciones en un orden que respeta la causalidad y te da igual cómo queden los pares concurrentes entre sí, el contador basta y su coste constante lo hace inmejorable. Deja de bastar en el momento en que necesitas responder si dos escrituras fueron concurrentes para decidir si hay conflicto, y esa pregunta requiere una estructura con una entrada por réplica, que es el asunto del nivel siguiente.

Hay un segundo uso, más humilde y muy rentable, que suele pasar desapercibido: el contador es un excelente criterio de retención para una cola de operaciones pendientes. Como toda operación que dependa causalmente de otra lleva forzosamente una marca mayor, procesar las operaciones recibidas en orden creciente de marca nunca aplica una consecuencia antes que su causa dentro de lo que la réplica ya tiene. No es una entrega causal completa, porque no detecta que falte una operación intermedia que aún no ha llegado, pero elimina de golpe toda una familia de estados intermedios absurdos a cambio de una única comparación numérica.

Antes de eso, tres detalles de implementación que se descubren tarde y duelen. El primero es la persistencia: el contador tiene que sobrevivir al cierre de la aplicación, guardado en el mismo almacén y preferiblemente en la misma transacción que los datos que sella; una réplica que reinicia su contador a cero vuelve a emitir marcas ya usadas y rompe la condición de reloj. El segundo es el tamaño: en un entorno donde los números son de coma flotante de doble precisión, los enteros son exactos hasta Number.MAX_SAFE_INTEGER, un margen enorme pero no infinito, y conviene decidir si serializas el contador como número o como cadena antes de tener datos en producción. El tercero es la defensa ante marcas absurdas: una réplica maliciosa o averiada puede enviar una marca gigantesca y arrastrar a todas las demás hasta ese valor, un salto del que el sistema no vuelve; validar el rango de las marcas entrantes es barato y evita un daño irreversible.

async function aplicarRemoto(op, reloj, db) {
  if (!Number.isSafeInteger(op.t) || op.t < 0) return; // marca no confiable
  const t = reloj.recibir(op.t);
  // El contador y el dato se guardan juntos, en la misma transaccion
  await db.transaccion(["ops", "meta"], "readwrite", async (tx) => {
    await tx.ops.put({ ...op, tLocal: t });
    await tx.meta.put({ clave: "relojLamport", valor: reloj.t });
  });
}