Comprobar las tres propiedades con casos concretos

Las tres propiedades que hacen convergente a esta estructura suelen presentarse como una demostración de cuatro líneas que casi nadie lee y menos gente aún traduce a código. Aquí haremos lo contrario: escribirlas como pruebas concretas sobre estados concretos, ejecutarlas y mirar la salida, porque una propiedad comprobada empíricamente sobre el escenario adecuado protege más que una demostración correcta sobre una implementación que no es la que se ejecuta. El experimento tiene además un segundo resultado, menos esperado y bastante más útil que el primero: veremos que la mezcla defectuosa de la lección anterior pasa las tres propiedades con el escenario obvio y solo falla cuando el escenario incluye el caso que la rompe. Esa es la lección de método que conviene llevarse por delante de cualquier suite de pruebas de convergencia: la propiedad no se comprueba en el vacío, se comprueba sobre una historia, y una historia que no ejerce el caso difícil declara correcta a una implementación que pierde datos.

Qué protege cada propiedad

Antes de escribir las pruebas conviene saber contra qué fallo real defiende cada una, porque las tres se enuncian igual de rápido y protegen contra cosas muy distintas. La conmutatividad dice que mezclar en un orden o en el otro da lo mismo, y protege contra el hecho más básico de una red sin coordinación: dos réplicas se sincronizan a la vez y cada una recibe primero lo que la otra recibe después. La asociatividad dice que agrupar las mezclas de una manera o de otra da lo mismo, y protege contra las topologías: que un cambio llegue directo o pasando por un intermediario que ya lo había combinado con otros no puede cambiar el resultado. La idempotencia dice que volver a mezclar algo ya conocido no altera nada, y protege contra el reenvío, que en cualquier transporte real ocurre constantemente.

Hay una cuarta condición que no es una propiedad de la mezcla sino de las operaciones y que conviene nombrar porque se olvida: cada operación local tiene que ser monótona, es decir, no puede quitar información del estado. El alta añade una etiqueta y la baja añade una marca; ninguna de las dos borra nada. Si en algún momento se optimiza la clase eliminando etiquetas muertas del mapa de altas, esa monotonía se rompe y las tres propiedades dejan de bastar, porque la información destruida puede volver desde otra réplica y producir una resurrección.

El escenario y el comprobador

El escenario necesita tres réplicas con historias que se solapen de verdad. Una que añade dos cosas, otra que parte de lo que vio de la primera y luego añade y retira, y una tercera completamente independiente que añade uno de los mismos valores. Ese tercer detalle es el que hace útil al escenario y se justificará solo en la última sección.

const { ORSet, serializar } = require("./orset.js");

function escenario() {
  const A = new ORSet("A");
  A.add("pan"); A.add("cafe");
  const B = ORSet.merge(new ORSet("B"), A);   // B parte de lo que vio de A
  B.add("te"); B.remove("pan");
  const C = new ORSet("C");
  C.add("cafe"); C.add("sal");                // C anade cafe sin saber de A
  return { A, B, C };
}

let fallos = 0;
function comprobar(nombre, izq, der) {
  const ok = serializar(izq) === serializar(der);
  if (!ok) fallos += 1;
  console.log((ok ? "OK  " : "FALLA ") + nombre);
}

El comprobador compara la serialización estable de la lección anterior en lugar de los objetos, y esa decisión es la que hace que las pruebas signifiquen algo. Comparar por identidad daría siempre falso porque merge construye objetos nuevos; comparar recursivamente los campos incluiría replica y reloj, que son contabilidad local y difieren legítimamente entre réplicas convergentes. La serialización ordenada y sin campos locales es la definición operativa de estos dos estados son el mismo, y sin ella no hay prueba de convergencia posible.

const { A, B, C } = escenario();

comprobar("conmutativa  merge A B  ==  merge B A", ORSet.merge(A, B), ORSet.merge(B, A));
comprobar("conmutativa  merge A C  ==  merge C A", ORSet.merge(A, C), ORSet.merge(C, A));
comprobar("asociativa   A con BC   ==  AB con C ",
  ORSet.merge(A, ORSet.merge(B, C)), ORSet.merge(ORSet.merge(A, B), C));
comprobar("idempotente  merge A A  ==  A       ", ORSet.merge(A, A), A);
comprobar("idempotente  merge AB B ==  merge A B",
  ORSet.merge(ORSet.merge(A, B), B), ORSet.merge(A, B));

La salida y los seis órdenes de entrega

Las cinco comprobaciones anteriores son puntuales. La prueba que de verdad convence es la que enumera todos los órdenes de entrega posibles y verifica que producen un único estado, porque es la traducción literal de lo que promete la convergencia: da igual cómo se propague la información mientras se propague entera.

const ordenes = [[A,B,C],[A,C,B],[B,A,C],[B,C,A],[C,A,B],[C,B,A]];
const huellas = new Set(ordenes.map(
  ([x, y, z]) => serializar(ORSet.merge(ORSet.merge(x, y), z))
));
console.log("ordenes de entrega probados:", ordenes.length, "estados distintos:", huellas.size);
console.log("estado comun:", [...huellas][0]);
console.log(fallos === 0 ? "TODO CORRECTO" : fallos + " FALLOS");

OK  conmutativa  merge A B  ==  merge B A
OK  conmutativa  merge A C  ==  merge C A
OK  asociativa   A con BC   ==  AB con C 
OK  idempotente  merge A A  ==  A       
OK  idempotente  merge AB B ==  merge A B
ordenes de entrega probados: 6 estados distintos: 1
estado comun: {"altas":{"cafe":["A:2","C:1"],"pan":["A:1"],"sal":["C:2"],"te":["B:1"]},"bajas":["A:1"]}
TODO CORRECTO

Seis órdenes, un solo estado. Y el estado común dice bastante más que la palabra correcto. El elemento cafe conserva las dos etiquetas, la de A y la de C, porque fueron dos altas independientes del mismo valor y ninguna es la otra; el conjunto presenta un solo cafe al usuario pero recuerda que hubo dos aportaciones, y eso es exactamente lo que hará falta para que una retirada que solo vio una de ellas no elimine la otra. El elemento pan sigue en el mapa con su etiqueta A:1, que figura también entre las bajas: está muerto y su lápida permanece. Los valores presentes son cafe, sal y te.

flowchart TD
A[estado A] --> M1[mezcla en cualquier orden]
B[estado B] --> M1
C[estado C] --> M1
M1 --> U[un unico estado final]
U --> P1[conmutativa: el orden no importa]
U --> P2[asociativa: la agrupacion no importa]
U --> P3[idempotente: repetir no importa]
style U fill:#a6e3a1,color:#11111b

Una prueba solo vale lo que vale su escenario

Aquí llega el resultado que justifica la lección entera. Repitamos exactamente las mismas tres comprobaciones sobre la mezcla defectuosa de la lección anterior, la que reemplaza los conjuntos internos en lugar de unirlos, usando únicamente las réplicas A y B.

function mergeMalo(a, b) {
  const s = new ORSet(a.replica);
  s.altas = new Map([...a.altas, ...b.altas]);       // reemplaza en vez de unir
  s.bajas = new Set([...a.bajas, ...b.bajas]);
  return s;
}
const chk = (n, x, y) => console.log((serializar(x) === serializar(y) ? "OK    " : "FALLA ") + n);
chk("conmutativa", mergeMalo(A, B), mergeMalo(B, A));
chk("asociativa ", mergeMalo(A, mergeMalo(B, C)), mergeMalo(mergeMalo(A, B), C));
chk("idempotente", mergeMalo(A, A), A);
console.log("--- ahora con A y C, que anaden cafe de forma independiente ---");
chk("conmutativa", mergeMalo(A, C), mergeMalo(C, A));
console.log("A con C:", serializar(mergeMalo(A, C)));
console.log("C con A:", serializar(mergeMalo(C, A)));

OK    conmutativa
OK    asociativa 
OK    idempotente
--- ahora con A y C, que anaden cafe de forma independiente ---
FALLA conmutativa
A con C: {"altas":{"cafe":["C:1"],"pan":["A:1"],"sal":["C:2"]},"bajas":[]}
C con A: {"altas":{"cafe":["A:2"],"pan":["A:1"],"sal":["C:2"]},"bajas":[]}

Las tres propiedades pasaron con A y B, y fallaron en cuanto entró C. La razón es precisa: B heredó de A la etiqueta A:2 para cafe, de modo que reemplazar el conjunto o unirlo daba el mismo resultado porque el conjunto era idéntico. Solo cuando dos réplicas etiquetan el mismo valor de forma independiente hay dos conjuntos distintos bajo la misma clave, que es la única situación en la que reemplazar difiere de unir. El escenario obvio no la contenía y por eso certificó una implementación que destruye etiquetas.