La demostración informal: por qué esas propiedades bastan

Tenemos todas las piezas encima de la mesa: el enunciado, la estructura ordenada, las tres igualdades algebraicas y la condición de monotonía. Falta encajarlas, y encajarlas es sorprendentemente rápido. La demostración de que un semirretículo con actualizaciones inflacionarias garantiza consistencia fuerte eventual cabe en tres pasos que se pueden decir en voz alta sin escribir un símbolo, y esa brevedad no es un truco expositivo: es real, y es la razón de que este marco se pueda enseñar y auditar. Lo que sigue es el razonamiento completo en castellano, seguido de lo que conviene tener aún más claro que la demostración misma, que es su frontera: qué patologías de la red quedan neutralizadas, cuáles no lo están y qué sigue siendo responsabilidad tuya después de que el teorema haya hecho su parte.

Qué hay que probar y con qué materiales

La tesis, una vez más, sin abreviar: si dos réplicas han entregado el mismo conjunto de actualizaciones, sus estados son equivalentes. Los materiales disponibles son cuatro, y conviene tenerlos numerados porque la demostración va a usarlos uno por uno.

El primero es que los estados forman un semirretículo de unión y que la función de mezcla calcula la cota superior mínima, lo cual —según vimos— equivale a que esa función sea conmutativa, asociativa e idempotente. El segundo es que toda actualización local es inflacionaria: nunca baja en el orden. El tercero es cómo se construye el estado de una réplica: se parte del elemento mínimo, el estado inicial vacío, y se mezcla todo lo que se va entregando, sea una actualización propia o un estado recibido de otra réplica. El cuarto material no interviene en la parte de seguridad y solo aparece al final: la hipótesis de entrega eventual, que dice que todo lo enviado acaba llegando a todas partes.

Con esos materiales, el estado de una réplica en un instante dado es lo que en programación se llama un pliegue: mezclar, en el orden en que fueron llegando, todo lo entregado hasta ese momento, empezando por el mínimo. La demostración consiste enteramente en probar que ese pliegue no depende del orden ni de las repeticiones, y por tanto que es una función del conjunto entregado y de nada más.

// El estado de una replica es un pliegue sobre lo entregado, en el orden que sea
const estadoDe = (entregado) => entregado.reduce(join, MINIMO);

// La tesis, dicha en codigo: dos ordenaciones cualesquiera del mismo conjunto
// producen estados iguales, y repetir elementos tampoco cambia nada.

Fíjate en una consecuencia menor y muy cómoda de plantearlo así: una réplica recién instalada no es un caso especial que haya que tratar aparte. Su conjunto entregado es el vacío, su estado es el elemento mínimo, y a partir de ahí se comporta como cualquier otra. No hace falta un procedimiento de alta, ni un identificador asignado por nadie, ni un estado semilla que haya que pedirle a un servidor: basta con sincronizar con quien sea y el pliegue hace el resto. Esa propiedad es la que permite abrir la aplicación en un dispositivo nuevo sin conexión y empezar a trabajar antes de haber visto ningún dato ajeno.

El razonamiento en tres pasos

Paso uno: desaparecen las repeticiones. Una réplica puede haber entregado el mismo mensaje varias veces, porque el emisor reintentó, porque la topología de sincronización tiene ciclos o porque dos vecinos le contaron lo mismo. Lo que tiene, entonces, no es un conjunto sino un multiconjunto, con multiplicidades. La idempotencia dice que mezclar algo consigo mismo no cambia nada, y de ahí se sigue que mezclar un elemento que ya estaba incorporado tampoco lo cambia. Las repeticiones se colapsan y el multiconjunto queda reducido, a efectos del resultado, a su conjunto subyacente. Después de este paso podemos hablar del conjunto entregado sin mentir.

Paso dos: desaparecen el orden y el agrupamiento. La conmutatividad dice que dos elementos adyacentes en la secuencia se pueden intercambiar sin alterar el resultado, y cualquier permutación de una lista se obtiene encadenando intercambios de elementos adyacentes; por tanto ninguna ordenación de la misma colección da un resultado distinto. La asociatividad dice que los paréntesis no importan, de modo que da igual mezclar de uno en uno o mezclar primero por bloques y luego los bloques entre sí. Este segundo detalle es lo que permite que las propiedades, enunciadas sobre dos y tres elementos, se extiendan sin más a colecciones de cualquier tamaño: es el mismo argumento por el que una suma de mil números no depende de por dónde empieces. Después de este paso, el pliegue sobre el conjunto está bien definido: es un valor, no un valor por cada camino.

Paso tres: el supremo es único. Ese valor bien definido es exactamente el supremo del conjunto entregado, es decir, el estado más pequeño que contiene la información de todos sus elementos. Y en la segunda lección demostramos en tres líneas, apoyándonos solo en la antisimetría, que la cota superior mínima de un conjunto es única. Junta las dos cosas y ya está: dos réplicas con el mismo conjunto entregado calculan el supremo del mismo conjunto, el supremo es único, luego sus estados son iguales. El teorema está demostrado, y no ha hecho falta hablar de la red, ni de fallos, ni de tiempo.

flowchart TB
M[multiconjunto de lo entregado con repeticiones y en cualquier orden] --> I[paso uno idempotencia]
I --> C[conjunto sin repeticiones]
C --> O[paso dos conmutatividad y asociatividad]
O --> S[supremo del conjunto bien definido]
S --> U[paso tres antisimetria da unicidad]
U --> F[mismos conjuntos entregados implican mismo estado]
style M fill:#f9e2af,color:#11111b
style F fill:#a6e3a1,color:#11111b

Merece un comentario el detalle técnico del paso dos, porque es el único punto donde alguien podría sospechar que hemos ido deprisa. Las propiedades se enuncian sobre dos y tres elementos, y la afirmación que necesitamos es sobre colecciones de tamaño arbitrario. El puente es una inducción de las que se hacen en un primer curso de álgebra: cualquier reordenación de una lista se alcanza intercambiando elementos vecinos un número finito de veces, y cada intercambio está justificado por la conmutatividad aplicada a un par; cualquier reagrupamiento se alcanza moviendo paréntesis de tres en tres, y cada movimiento está justificado por la asociatividad. No hace falta más maquinaria, y por eso la demostración no crece con el tamaño del sistema.

Falta acoplar la monotonía, que en la lista de pasos no ha aparecido y sin embargo es imprescindible. Su papel es garantizar que el estado de una réplica sea de verdad el supremo de lo entregado y no otra cosa. Si una actualización local pudiera bajar en el orden, el estado dejaría de coincidir con ese supremo y el paso tres perdería su sujeto: habría un valor calculado por la réplica y un supremo del conjunto, y no serían el mismo. La monotonía es la hipótesis que mantiene ambos identificados a lo largo de toda la ejecución.

// La tesis, comprobada empiricamente sobre un conjunto de estados
const barajar = (xs) => [...xs].sort(() => Math.random() - 0.5);
const duplicar = (xs) => [...xs, ...xs.slice(0, 3)];

const base = [e1, e2, e3, e4, e5];
const referencia = estadoDe(base);

for (let i = 0; i < 1000; i++) {
  const variante = estadoDe(barajar(duplicar(base)));
  if (!iguales(variante, referencia)) throw new Error("no converge");
}

Por qué la red deja de importar, y qué sigue importando

Traduzcamos los tres pasos a la lista de cosas desagradables que hace una red real, que es donde se ve el rendimiento del argumento.

La cuarta tarjeta merece un comentario porque es la que más libertad operativa concede y la que menos se explicita. Como mezclar el estado de un vecino equivale a mezclar todo lo que ese vecino había entregado, no hay ninguna restricción sobre con quién sincroniza cada réplica ni con qué frecuencia: sirve una estrella alrededor de un servidor, sirve una cadena, sirve un intercambio directo por Bluetooth entre dos teléfonos en un tren y sirve una mezcla cambiante de todo lo anterior. El teorema no menciona la topología porque no la necesita, y de ahí sale la afirmación de que estos sistemas se sincronizan por cualquier medio, incluido copiar un archivo en una memoria USB.

La justificación de esa cuarta tarjeta cabe en una línea y conviene verla escrita porque se usa a todas horas: el estado de un vecino es el supremo del subconjunto que él ha entregado, y el supremo de una unión de conjuntos coincide con el supremo de los supremos de sus partes. Mezclar con un vecino es, por tanto, incorporar de golpe todo lo que ese vecino sabía, sin que importe por qué caminos lo supo ni cuántas veces me lo hayan contado ya. De ahí sale la corrección de los protocolos de antientropía, que consisten en elegir un compañero al azar cada cierto tiempo e intercambiar estados: no necesitan saber quién ha visto qué, porque el álgebra tolera la redundancia total.

Y ahora lo que no queda cubierto, que hay que saberse igual de bien. La pérdida definitiva: si un mensaje no llega nunca y nadie lo reintenta, los conjuntos entregados nunca coinciden y no hay álgebra que lo arregle; la convergencia real depende de la hipótesis de entrega, que es responsabilidad del transporte. El adversario: una réplica maliciosa puede enviar un elemento del semirretículo perfectamente legal cuyo contenido sea basura, y el sistema convergerá obedientemente a la basura; el teorema garantiza acuerdo, no veracidad, y defenderse de eso exige firmas, autorización y validación de las operaciones, que son otra capa. La familia basada en operaciones: allí el paso uno no lo da el álgebra sino el canal, que debe entregar cada operación una sola vez o hacerlas idempotentes por identificador, y además debe respetar el orden causal, porque la conmutatividad solo se exige entre operaciones concurrentes.

Lo que la demostración no dice

Un teorema bien entendido se usa por sus dos bordes, y el borde de abajo importa tanto como el de arriba. Aquí van las afirmaciones que no se han demostrado y que, sin embargo, se le atribuyen constantemente a este argumento.

No se ha demostrado que el estado al que se converge sea el correcto. La demostración cuantifica sobre la estructura algebraica y no toca el significado: si tu semirretículo hace ganar sistemáticamente al valor equivocado, todas las réplicas coincidirán en el valor equivocado y el teorema estará satisfecho. No se ha demostrado nada sobre el tamaño de los metadatos: las lápidas de la lección anterior son perfectamente compatibles con la demostración y siguen creciendo. No se ha demostrado nada sobre latencia: cuándo se entrega cada cosa es asunto del transporte. Y no se ha demostrado ninguna invariante que relacione varios datos entre sí, porque la mezcla trabaja sobre el estado y no sabe qué reglas de negocio querías conservar.

Sobre la familia basada en operaciones conviene ser todavía más explícito, porque su demostración se parece mucho a esta pero con las cargas repartidas de otra manera. Allí el paso uno no lo garantiza el álgebra sino el canal, que debe entregar cada operación una sola vez, o bien las operaciones deben llevar identificador y descartarse las repetidas, que es la misma idempotencia mudada de sitio. El paso dos se reduce a exigir conmutatividad únicamente entre operaciones concurrentes, lo cual es una hipótesis más débil y por eso permite operaciones que en la otra familia serían inadmisibles, pero a cambio obliga al canal a respetar el orden causal, que es maquinaria real: un búfer, unos metadatos causales y una política para lo que llega demasiado pronto. La cuenta final suele quedar equilibrada, y por eso ambas familias sobreviven en producción.

// La demostracion como prueba: red hostil y comprobacion final
function corrida(operaciones, replicas) {
  const cola = [];
  for (const op of operaciones) {
    const r = alAzar(replicas);
    r.estado = join(r.estado, aplicar(r.estado, op));
    cola.push({ desde: r, carga: r.estado });
    if (Math.random() < 0.3) cola.push(cola[cola.length - 1]); // duplicado
  }
  barajar(cola).forEach((m) => replicas.forEach((r) => {
    r.estado = join(r.estado, m.carga); // entrega desordenada y repetida
  }));
  return replicas.every((r) => iguales(ver(r.estado), ver(replicas[0].estado)));
}

Y una última precisión sobre el alcance, que es la que más disgustos ahorra en una reunión de producto: el teorema habla de estados, no de interfaces. Que dos réplicas tengan el mismo estado no significa que dos personas vean lo mismo en la pantalla, porque entre el estado y la pantalla hay filtros, ordenaciones, cachés, vistas materializadas y una posición de scroll. Buena parte de los informes de divergencia que llegan a los equipos que trabajan con estas estructuras no son divergencias del estado sino de la capa de presentación, y distinguir unas de otras en cinco minutos es una habilidad práctica que se adquiere volcando el estado convergente de ambos dispositivos y comparándolo antes de tocar nada.

Conviene además recordar la letra pequeña del enunciado: la igualdad final es equivalencia, no identidad de representación. Dos réplicas pueden llegar a estructuras internas distintas —órdenes distintos en un mapa, etiquetas internas diferentes— y ser el mismo estado a efectos del teorema si producen exactamente las mismas observaciones. Esa flexibilidad es la que hace implementables las estructuras con metadatos, y también la que obliga a que la función de igualdad que uses en las pruebas compare observaciones y no bytes.