La relación de precedencia causal

Si el reloj no puede decirte qué pasó antes, alguien tiene que definir qué significa antes sin recurrir a ningún reloj. Esa definición existe desde 1978, la dio Leslie Lamport en 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, y es una de esas construcciones que parecen triviales cuando las lees y reorganizan tu forma de pensar cuando las asimilas. La idea consiste en abandonar la pretensión de situar los eventos sobre una línea única y quedarse solo con lo que un sistema distribuido puede afirmar con honestidad: que ciertos eventos pudieron influir en otros, y que en muchísimos pares no hubo ninguna influencia posible en ninguna de las dos direcciones. Lo primero es una relación de precedencia; lo segundo se llama concurrencia; y el conjunto no es una línea, es una red.

Las tres reglas que definen el antes

Se parte de un modelo deliberadamente austero. Un sistema es un conjunto de réplicas o procesos, cada uno de los cuales ejecuta una secuencia de eventos, y las réplicas se comunican únicamente enviando y recibiendo mensajes. No hay memoria compartida, no hay reloj común, no hay observador externo. Sobre ese modelo se define una relación entre eventos, que suele escribirse con una flecha y se lee como precede causalmente a, mediante tres reglas.

Antes de enunciarlas conviene fijar qué cuenta como evento, porque la definición es tuya y no viene dada. En una aplicación real un evento suele ser una operación sobre los datos, el envío de un lote de cambios o la recepción de otro, y elegir un grano más fino de lo necesario multiplica el trabajo sin añadir información. La única exigencia es que la elección sea consistente: todo lo que quieras poder ordenar después tiene que haber pasado por la definición de evento desde el principio.

La primera es local: si dos eventos ocurren en la misma réplica, el que la réplica ejecutó primero precede al otro. Esto no requiere ninguna medida de tiempo, solo el orden de ejecución del propio proceso, que es un dato que la réplica conoce sin ambigüedad.

La segunda es la del mensaje: el envío de un mensaje precede a su recepción. También aquí basta con la estructura del sistema, sin reloj alguno, y es la única regla que cruza la frontera entre dos réplicas. Toda la información sobre orden que un sistema distribuido posee entra por esta puerta.

La tercera es la transitividad: si un evento precede a otro y ese otro precede a un tercero, el primero precede al tercero. Esta regla es la que convierte dos reglas locales en una relación global, porque encadena tramos de proceso con tramos de mensaje y permite conectar eventos que están a varias réplicas de distancia.

Conviene resistir dos lecturas erróneas de este trío de reglas. La primera es creer que hace falta que las réplicas se pongan de acuerdo en algo para aplicarlas; no hace falta nada: cada réplica conoce el orden de sus propios eventos y sabe qué mensajes envió y recibió, y con eso basta. La segunda es creer que la relación depende de la topología de la red o del protocolo de transporte. No depende: da igual que el mensaje viaje por un canal directo, rebote en un servidor intermedio o llegue dentro de un fichero copiado a mano en una memoria externa. Lo único que cuenta es que hubo transmisión de información de una réplica a otra, y por eso la construcción sobrevive intacta a cualquier arquitectura de sincronización que decidas usar después.

Y ahí se acaba la definición. Lo notable es lo que no aparece en ella: ninguna magnitud, ninguna unidad, ningún instrumento. La relación se construye enteramente con dos hechos que cada réplica observa por sí misma, y por eso es exactamente el tipo de información que un sistema sin autoridad central puede obtener sin coordinarse con nadie.

flowchart LR
a1[a1 escritura en la replica A] --> a2[a2 envio de mensaje desde A]
a2 --> b2[b2 recepcion del mensaje en B]
b1[b1 escritura en la replica B] --> b2
b2 --> b3[b3 escritura en la replica B]
c1[c1 escritura en la replica C] --> c2[c2 escritura en la replica C]
style a2 fill:#89b4fa,color:#11111b
style b2 fill:#89b4fa,color:#11111b
style c1 fill:#cba6f7,color:#11111b

En ese diagrama, a1 precede a b3 porque hay un camino dirigido que los une pasando por el mensaje. En cambio no hay ningún camino entre a1 y c1, ni en un sentido ni en el otro, y esa ausencia de camino es un hecho tan informativo como su presencia.

Todo lo demás de este nivel, y buena parte del siguiente, consiste en representar esa relación de forma compacta y en decidir qué hacer con los pares que deja sin ordenar.

Concurrente no significa simultáneo

Esta es probablemente la definición peor traducida de todo el campo, porque la palabra elegida arrastra en el lenguaje corriente un significado que aquí no tiene. Dos eventos distintos son concurrentes cuando ninguno precede causalmente al otro. Es una definición por negación, y conviene resistir la tentación de traducirla a otra cosa. En particular, la concurrencia no dice nada sobre la hora a la que ocurrieron los eventos: dos eventos concurrentes pueden estar separados por semanas de tiempo físico. Si una persona edita un documento en un portátil sin conexión un lunes y otra lo edita en su teléfono el jueves, y ninguna de las dos réplicas ha recibido nada de la otra en ese intervalo, los dos eventos son concurrentes en el sentido exacto de la definición, por mucho que en la línea temporal de la física uno esté tres días después del otro.

Que la traducción intuitiva falle no es un defecto de la definición sino su virtud, porque lo que se está capturando no es una coincidencia temporal sino una ausencia de información. Que dos eventos sean concurrentes significa que ninguna de las dos réplicas sabía nada de lo que la otra estaba haciendo, y por lo tanto que ninguna de las dos decisiones pudo tomar en cuenta la otra. Esa es precisamente la situación en la que un conflicto es posible, y es la razón por la que esta relación es el fundamento de todo lo que viene después: conflicto y concurrencia son el mismo fenómeno visto desde dos ángulos.

Vale la pena además observar una consecuencia contraintuitiva del modelo: la cantidad de concurrencia de un sistema no es una constante, sino una variable de diseño que tú controlas. Cada mensaje entregado añade aristas al grafo y convierte en comparables pares que antes no lo eran, así que sincronizar más a menudo reduce la concurrencia y sincronizar menos la aumenta. Un sistema que envía cambios en cuanto se producen y con la red disponible tiene poquísimos pares concurrentes; el mismo sistema con sincronización manual una vez al día los tiene a millares. Esto explica por qué el trabajo sin conexión no es solo una comodidad para el usuario, sino la decisión que determina cuánta maquinaria de resolución vas a necesitar.

Codificar la relación es directo si cada evento guarda la lista de sus dependencias inmediatas, es decir, el evento anterior de su propia réplica y, si es una recepción, el envío correspondiente.

// Cada evento guarda solo sus dependencias directas
const eventos = {
  a1: [],
  a2: ["a1"],
  b1: [],
  b2: ["b1", "a2"], // recepcion del mensaje enviado en a2
  b3: ["b2"],
  c1: [],
  c2: ["c1"],
};

function precede(x, y) {
  return eventos[y].some((p) => p === x || precede(x, p));
}

function concurrentes(x, y) {
  return x !== y && !precede(x, y) && !precede(y, x);
}

precede("a1", "b3");        // true, hay camino a traves del mensaje
concurrentes("a1", "c1");   // true, no hay camino en ningun sentido

Obsérvese que en la estructura de datos solo aparecen las dependencias directas de cada evento, nunca la lista completa de sus antecesores. Eso no es una economía casual: guardar únicamente las aristas inmediatas y dejar que la transitividad haga el resto es lo que mantiene el tamaño del registro proporcional al número de eventos y no a su cuadrado. La estructura resultante es la reducción transitiva del orden, el conjunto mínimo de aristas que genera exactamente la misma relación, y es la representación que emplean tanto los diagramas de este tipo como los formatos reales de intercambio entre réplicas.

Ese código es una definición ejecutable, no una implementación: recorre el grafo entero cada vez y no se usaría jamás en producción. Su valor está en dejar claro que la pregunta precede se responde con alcanzabilidad en un grafo dirigido, y la pregunta concurrentes se responde comprobando que no hay alcance en ninguna de las dos direcciones. Toda la maquinaria de relojes lógicos que verás a continuación no es más que un modo de responder esas dos preguntas sin guardar el grafo ni recorrerlo.

Hay un corolario que conviene tener a mano al diseñar la interfaz: si dos operaciones son concurrentes, ninguna de las dos personas implicadas pudo saber lo que hacía la otra, y por tanto ninguna de las dos actuó con mala información. Cualquier mensaje que culpe a una de las dos, o que sugiera que llegó tarde, describe mal lo ocurrido.

Por qué esto es un orden parcial

Conviene nombrar la estructura con precisión, porque el nombre trae consigo consecuencias que de otro modo hay que redescubrir a golpes. La relación es irreflexiva, pues ningún evento se precede a sí mismo; es transitiva por la tercera regla; y de ambas se sigue que es asimétrica, ya que un ciclo implicaría que un evento se precede a sí mismo. Una relación con esas propiedades es un orden parcial estricto, y el grafo que la representa es acíclico y dirigido.

La palabra que hace todo el trabajo es parcial. Un orden total exige que dos elementos cualesquiera sean comparables, y aquí eso falla por construcción: los pares concurrentes son incomparables, y no lo son por falta de esfuerzo ni por una limitación de la implementación, sino porque en el sistema no existe ninguna información que permita compararlos. Ningún algoritmo puede extraer un dato que nadie registró.

El propio Lamport señala en el artículo la analogía con la relatividad especial, donde tampoco existe un orden temporal único válido para todos los observadores y donde dos sucesos solo están ordenados si uno puede influir en el otro dentro del límite que impone la velocidad de la luz. La analogía es útil siempre que no se estire: en un sistema distribuido el papel del cono de luz lo desempeñan los mensajes, y la razón de que dos eventos sean incomparables no es un límite físico sino la simple ausencia de comunicación. Pero la enseñanza estructural es la misma y vale la pena interiorizarla, porque desactiva de raíz la sensación de que debe existir una secuencia verdadera que el sistema no consigue ver. No existe, y no por falta de instrumentos.

La consecuencia práctica es que sobre un orden parcial no puedes ordenar una colección con las funciones de ordenación habituales, porque todas ellas presuponen un orden total y producen resultados dependientes del orden de entrada cuando no lo tienen. Lo que sí puedes hacer es recorrer los eventos en un orden compatible con la precedencia, es decir, un orden topológico del grafo, en el que nunca procesas un evento antes que sus predecesores. Esa es exactamente la garantía que necesita un sistema de replicación para aplicar operaciones con sentido, y es también el motivo por el que hay muchos órdenes topológicos válidos y ninguno privilegiado.

Esa es, en el fondo, la razón de que toda la maquinaria de los niveles siguientes exista: no hay atajo hacia la línea única, y lo que queda es aprender a trabajar con la red.

Lo que la relación captura y lo que se le escapa

Falta una precisión que Lamport ya hace en el artículo original y que se pierde con frecuencia al divulgarlo. La relación no captura la causalidad real, sino la causalidad potencial: que un evento preceda a otro significa que el primero pudo haber influido en el segundo, no que lo hiciera. Puede haber un camino de mensajes entre dos eventos completamente ajenos entre sí, y la relación los declarará ordenados igualmente.

Que la relación sea generosa en esa dirección no es un defecto, sino una decisión de diseño deliberada y conservadora. Detectar la influencia real exigiría entender la semántica de cada operación, algo que ninguna capa de sincronización puede hacer, así que se toma la aproximación segura: si hubo un camino de mensajes, se declara ordenado. El coste de esa aproximación es que el sistema ordena de más y por tanto detecta menos conflictos de los que en teoría podrían señalarse; el beneficio es que nunca declara concurrentes dos eventos que el propio sistema conectó, que es el error que sí produciría estados incoherentes.

El error simétrico es más delicado. Dos eventos declarados concurrentes por la relación pueden estar relacionados de verdad si la influencia viajó por un canal que el sistema no observa. Dos personas que hablan por teléfono, una que ve la pantalla de la otra, un mensaje enviado por otra aplicación: en todos esos casos existe una dependencia real que el sistema no puede ver, porque no pasó por sus mensajes. El artículo de 1978 discute precisamente este fenómeno como un comportamiento anómalo desde el punto de vista de un observador externo, y es lo que motiva la segunda mitad del artículo, dedicada a los relojes físicos.

De todo ello sale una regla operativa que conviene tener presente al diseñar la interfaz: la relación es un buen fundamento para decidir qué datos se conservan y un mal fundamento para redactar mensajes tajantes al usuario. Afirmar en pantalla que dos personas editaron a la vez es correcto en el sentido técnico de la definición y puede ser falso en el sentido en que el usuario lo entenderá, si resulta que una avisó a la otra por teléfono. Describir la situación por lo que el sistema sabe, dos versiones que llegaron sin conocerse, es más largo y es cierto.