Desempatar: de orden parcial a orden total

Llegados aquí tienes un orden parcial correcto y un contador que lo respeta pero que empata con frecuencia. Y tienes también una necesidad muy concreta que no desaparece por muy elegante que sea la teoría: un campo de texto muestra un valor, no dos, y un registro tiene que quedarse con algo cuando dos réplicas escriben a la vez. Hay que elegir. El truco que resuelve esto aparece ya en el artículo de Lamport de 1978 y consiste en desempatar con un criterio que no dice nada sobre el mundo pero que todas las réplicas evalúan igual: el identificador de quien escribió. El resultado es un orden total, y conviene mirar de frente lo que se ha hecho, porque se ha fabricado información que el sistema no tenía. La pregunta que gobierna esta lección no es si eso es legítimo, que lo es, sino dónde colocar esa fabricación para que no destruya el trabajo de nadie.

De un orden parcial a un orden total

La construcción es de una sencillez desarmante. Se comparan primero los contadores lógicos; si difieren, ya está decidido. Si coinciden, se comparan los identificadores de réplica según cualquier orden total fijado de antemano sobre ellos, por ejemplo el orden lexicográfico de sus cadenas. Como los identificadores son únicos y el orden entre ellos es total, el empate se resuelve siempre y de una única manera.

// Un sello es el par contador logico mas identificador de replica
function comparar(a, b) {
  if (a.t !== b.t) return a.t - b.t;
  if (a.replica < b.replica) return -1;
  if (a.replica > b.replica) return 1;
  return 0; // mismo sello: es el mismo evento
}

const ganador = (x, y) => (comparar(x, y) >= 0 ? x : y);

Lo importante de esa comparación no es que sea corta, sino que satisface dos propiedades a la vez. La primera es que es un orden total: dos sellos cualesquiera son comparables y el resultado nunca es ambiguo. La segunda, mucho menos obvia, es que extiende al orden causal: si un evento precede causalmente a otro, la condición de reloj garantiza que su contador es estrictamente menor y por tanto el desempate ni siquiera llega a evaluarse. Es decir, el nuevo orden nunca contradice a la causalidad; solo rellena los huecos que la causalidad dejaba abiertos.

Conviene además fijarse en una propiedad de la construcción que resulta fácil de dar por supuesta y que es justamente la que la hace utilizable: el comparador solo necesita los dos sellos. No consulta el estado del documento, no necesita saber qué otras operaciones existen, no depende de cuántas réplicas hay ni de cuáles están conectadas. Es una función pura de dos argumentos que viajan pegados a los datos, y por eso puede evaluarse en un dispositivo desconectado, en un servidor de sincronización que no entiende el contenido o en una herramienta de reparación escrita tres años después.

En términos matemáticos, lo que se ha construido es una extensión lineal del orden parcial. Hay muchísimas extensiones lineales posibles para un mismo orden parcial, y este mecanismo elige una de ellas mediante una regla fija. La elección no descubre nada: inventa. Pero inventa solo donde no había nada que descubrir.

flowchart TB
P[Orden parcial causal con pares incomparables] --> C[Comparar contadores logicos]
C -->|contadores distintos| D[Decidido por causalidad potencial]
C -->|contadores iguales| I[Comparar identificadores de replica]
I --> E[Decidido por convencion arbitraria]
D --> T[Orden total identico en todas las replicas]
E --> T
style I fill:#f9e2af,color:#11111b
style E fill:#f9e2af,color:#11111b
style T fill:#a6e3a1,color:#11111b

Arbitrario pero determinista

Que el criterio de desempate sea arbitrario incomoda a mucha gente la primera vez, y la incomodidad suele expresarse como una búsqueda: tiene que haber un criterio mejor, uno que refleje algún mérito real. Se proponen entonces alternativas de aspecto razonable, como que gane el valor más largo, el más reciente según el reloj de pared, el de la réplica que más ha escrito o el del usuario con más permisos. Todas ellas comparten un defecto de fondo: ninguna se apoya en información que el sistema posea de manera fiable, y algunas reintroducen por la puerta de atrás exactamente el reloj de pared que la primera lección descartó.

El criterio del identificador no pretende tener mérito. Su única virtud, que resulta ser la que importa, es que es determinista: cualquier réplica que tenga los dos sellos calcula el mismo resultado, sin consultar a nadie, sin red y sin importar en qué orden le llegaron los datos. Esa propiedad es la que hace que dos réplicas que han visto el mismo conjunto de operaciones converjan al mismo estado, que es la única garantía que se puede ofrecer sin coordinación.

El contraste con un sistema centralizado ilumina el punto. Allí el criterio también es arbitrario, porque el ganador es simplemente quien llegó antes al servidor, y eso depende de la latencia de la red y no del mérito de nadie. La diferencia es que ese arbitrio queda oculto tras una explicación cómoda, la de que uno llegó primero, mientras que aquí queda a la vista en forma de un identificador aleatorio. La arbitrariedad no ha aumentado al distribuir el sistema; solo ha dejado de disimularse.

// Lo que NO puede entrar en un desempate
const criteriosProhibidos = [
  "la hora del reloj de pared, que difiere entre dispositivos",
  "el estado actual del documento, que difiere segun lo recibido",
  "cuantas escrituras lleva cada replica, que cambia con el tiempo",
  "el orden de llegada, que depende de la red de cada uno",
];
// Todos parecen razonables y todos producen resultados distintos
// en dos replicas que han visto exactamente lo mismo.

Conviene ver el determinismo como una exigencia con tres partes, porque un desempate que falle en cualquiera de ellas no sirve. Tiene que ser total, para que no queden pares sin decidir. Tiene que ser antisimétrico, para que la respuesta no dependa del orden en que se pasen los argumentos, cosa que ocurre exactamente cuando alguien devuelve cero para pares distintos. Y tiene que ser estable en el tiempo, para que la misma pareja de sellos dé el mismo resultado hoy y dentro de un año, lo cual excluye cualquier criterio basado en el estado actual de la réplica o en su historial.

Sobre el tamaño del identificador hay una decisión que se toma una sola vez y que no admite corrección posterior. Si dos réplicas generan por azar el mismo valor, sus sellos dejan de ser distinguibles y el orden total deja de estar bien definido, con la particularidad de que el fallo no se manifiesta hasta que ambas coinciden en un empate, quizá meses después y en datos de un usuario. Como no hay ninguna autoridad que reparta identificadores sin coordinación, la única defensa es hacer la colisión suficientemente improbable con un valor aleatorio de longitud generosa, que es el motivo por el que las implementaciones reales usan identificadores largos y aparentemente desproporcionados para lo que parece ser un simple desempate.

Merece la pena señalar que el propio artículo de 1978 advierte de que el orden total resultante es en cierto modo arbitrario y que puede producir comportamientos que un observador externo percibiría como anómalos, cuando dos usuarios se coordinan por un canal que el sistema no observa. Esa observación es la que motiva la segunda parte de aquel artículo, dedicada a los relojes físicos, y es también la que reaparecerá en este track bajo la forma de relojes lógicos híbridos.

Lo que el usuario ve cuando pierde

Todo lo anterior es impecable como mecanismo y puede ser desastroso como experiencia, y conviene no confundir los dos planos. Cuando un desempate por identificador decide un registro de tipo última escritura gana, alguien acaba de perder lo que escribió, y lo ha perdido por una razón que no existe: no llegó tarde, no se equivocó, no tenía menos derecho. Simplemente su identificador aleatorio era menor.

Merece la pena separar aquí dos cosas que se confunden con facilidad. El desempate por identificador es correcto en el sentido técnico exacto: produce convergencia, respeta la causalidad y no depende de ningún dato poco fiable. Y a la vez puede ser inaceptable en el sentido del producto, porque un usuario que pierde su trabajo no evalúa la corrección del algoritmo. Que ambas cosas sean verdad al mismo tiempo no es una contradicción, es el planteamiento del problema: la corrección es un requisito mínimo y no un objetivo, y una arquitectura que se detiene en cuanto alcanza la corrección deja el trabajo a medias.

Lo peor no es la pérdida, es su forma. No hay excepción, no hay conflicto marcado, no hay historial: el valor de una persona desaparece y en su lugar aparece el de otra, sin ningún rastro. Y hay un agravante estadístico que se pasa por alto: como el identificador es fijo, el sesgo es sistemático, no aleatorio. La misma réplica gana todos los empates contra la misma otra réplica, siempre, mientras ambos identificadores no cambien. Para un usuario concreto esto no se percibe como mala suerte ocasional sino como que la aplicación pierde sus cambios de forma reiterada, que es justamente el defecto que más rápido destruye la confianza en una herramienta.

Dónde poner la frontera

La conclusión práctica no es renunciar al desempate, que es imprescindible, sino contenerlo. Hay tres decisiones de diseño que reducen su daño de forma desproporcionada respecto a su coste.

Las tres se resumen en una idea que conviene enunciar antes de desarrollarlas: el desempate es una red de seguridad, no un mecanismo de trabajo. Un diseño saludable llega a él pocas veces, y cuando llega deja constancia.

La primera es la granularidad. Si el sello se aplica al documento entero, dos ediciones concurrentes en campos distintos entran en conflicto y una desaparece por completo. Si el sello se aplica a cada campo, esas dos ediciones sobreviven las dos y el desempate solo actúa cuando ambas tocan el mismo campo. Bajar la granularidad no cambia el algoritmo en absoluto: cambia cuántas veces llega a ejecutarse.

La segunda es conservar al perdedor. En lugar de descartar el valor derrotado, se guarda junto al ganador en un histórico corto, con su sello. El valor mostrado sigue siendo uno solo, el determinismo sigue intacto, y a cambio existe la posibilidad de que el usuario recupere lo suyo o de que el soporte técnico explique qué ocurrió. La diferencia entre una pérdida y una elección revisable cabe en un campo adicional.

Vale la pena además medir con qué frecuencia se llega de verdad al desempate, porque la intuición suele exagerarla en un sentido y minimizarla en otro. Entre réplicas que se sincronizan a menudo, los contadores rara vez coinciden y el desempate casi no actúa; entre réplicas que trabajan desconectadas durante días, los contadores avanzan por separado y el empate deja de ser una rareza. La conclusión es que la frecuencia del desempate no es una propiedad del algoritmo sino del patrón de uso de tu aplicación, y por tanto es algo que se instrumenta y se observa en datos reales, no algo que se estime en una pizarra.

La tercera es elegir la estructura según el dato. El desempate arbitrario es aceptable para un valor sin estructura interna donde la fusión no tiene sentido: un color, un estado, una casilla. Es inaceptable para texto que dos personas escriben a la vez, para conjuntos donde ambas aportaciones son válidas o para contadores donde las dos operaciones deben sumarse. Esas estructuras no necesitan árbitro porque sus operaciones conmutan, y sustituir un registro por la estructura adecuada elimina el problema en lugar de administrarlo.

// Registro por campo que conserva el valor descartado
function fusionarCampo(local, remoto) {
  const gana = comparar(remoto.sello, local.sello) > 0 ? remoto : local;
  const pierde = gana === remoto ? local : remoto;
  if (gana.valor === pierde.valor) return gana;
  return { ...gana, descartados: [...(gana.descartados ?? []), pierde] };
}

Las tres decisiones comparten una característica que las hace especialmente rentables: ninguna toca el comparador. El mecanismo de desempate sigue siendo el mismo par de líneas, con las mismas garantías y el mismo determinismo. Lo que cambia es sobre qué se aplica, con qué frecuencia y qué se hace con lo que queda fuera. Esa separación entre un núcleo mínimo e invariable y unas políticas ajustables alrededor es exactamente la forma que tienen los sistemas de este tipo cuando están bien construidos, y reconocerla ahora ahorra mucho tiempo cuando aparezcan estructuras más complicadas.