La prueba de convergencia: dos réplicas y una consola

Las tres lecciones anteriores han dejado sobre la mesa unas ciento veinte líneas de JavaScript. Ahora toca la única pregunta que importa: ¿converge? Y converger no significa que las dos réplicas muestren textos parecidos, ni que el resultado sea el que un humano habría esperado. Significa algo mucho más estricto y mucho más comprobable: que después de que ambas hayan visto exactamente el mismo conjunto de operaciones, sus arrays internos contengan los mismos nodos en el mismo orden, con independencia de la secuencia en que llegaron los mensajes. Esta lección monta el escenario, lo ejecuta, enseña la salida literal de la consola y después la somete a la única prueba que despeja las dudas: entregar las operaciones en todos los órdenes posibles, uno por uno, y verificar que el resultado no se mueve ni una vez.

El escenario: una base común y dos ediciones a la vez

El montaje tiene tres fases. En la primera, Ana escribe HOLA y difunde sus cuatro operaciones, de modo que las dos réplicas parten de un estado idéntico. En la segunda, cada una edita sin ver a la otra: Ana añade MUNDO al final y Beto añade CRUEL al final y además borra la H inicial. En la tercera intercambian todo, y aquí está lo importante: Ana recibe las operaciones de Beto en orden inverso al que se emitieron, para que el resultado no pueda depender del orden de llegada por casualidad.

const ana = crearReplica("ana");
const beto = crearReplica("beto");

// Fase 0: ana escribe y sincroniza. Las dos replicas parten del mismo estado.
const base = escribir(ana, 0, "HOLA");
for (const op of base) recibir(beto, op);
console.log("base comun          ana=%j  beto=%j", texto(ana), texto(beto));

// Fase 1: edicion concurrente. Ninguna ve todavia lo que hace la otra.
const deAna = escribir(ana, 4, " MUNDO");
const deBeto = escribir(beto, 4, " CRUEL");
deBeto.push(borrar(beto, idVisible(beto, 0)));
console.log("antes de sincronizar ana=%j  beto=%j", texto(ana), texto(beto));

// Fase 2: intercambio en ordenes distintos
for (const op of [...deBeto].reverse()) recibir(ana, op);   // inverso
for (const op of deAna) recibir(beto, op);                  // directo

console.log("despues de sincronizar ana=%j  beto=%j", texto(ana), texto(beto));
console.log("mismo texto: %s   misma secuencia interna: %s   pendientes: %d/%d",
  texto(ana) === texto(beto),
  ana.lista.map((n) => clave(n.id)).join() === beto.lista.map((n) => clave(n.id)).join(),
  ana.pendientes.length, beto.pendientes.length);

base comun          ana="HOLA"  beto="HOLA"
antes de sincronizar ana="HOLA MUNDO"  beto="OLA CRUEL"
despues de sincronizar ana="OLA CRUEL MUNDO"  beto="OLA CRUEL MUNDO"
mismo texto: true   misma secuencia interna: true   pendientes: 0/0

Leer la salida: nadie ve lo que escribió

La segunda línea es la interesante desde el punto de vista humano. Antes de sincronizar, Ana lee HOLA MUNDO y Beto lee OLA CRUEL. Después de sincronizar, ninguno de los dos ve lo que tenía: los dos leen OLA CRUEL MUNDO. El texto de Ana ha perdido su H porque el borrado de Beto era una operación legítima que ella no había visto, y el bloque de Beto se ha colado por delante del suyo porque el desempate por sello lo puso primero.

Conviene desmenuzar por qué el resultado es exactamente ese y no otro. Los dos espacios que abren cada ráfaga llevan el contador cinco, porque ambas réplicas habían visto los mismos cuatro caracteres; el empate lo rompe el nombre, y beto es posterior a ana en orden lexicográfico, así que su subárbol se coloca primero. Dentro de cada ráfaga no hay competencia alguna, porque cada carácter cuelga del anterior de su propia tanda, y por eso los seis caracteres de cada bloque salen juntos y en orden. El borrado, por su parte, no participa en la ordenación: solo apaga un nodo que sigue ahí.

Más allá del texto: la misma secuencia interna

La comprobación de la última línea es más fuerte que comparar los textos y merece una explicación, porque la diferencia no es cosmética. Dos réplicas podrían mostrar el mismo texto y tener estructuras internas distintas —por ejemplo, con las lápidas colocadas en sitios diferentes—, y esa divergencia oculta se manifestaría en la siguiente edición: una inserción hecha en la posición tres acabaría anclada a nodos distintos en cada réplica y a partir de ahí ya no habría vuelta atrás.

const huellaAna = ana.lista.map((n) => `${clave(n.id)}:${n.borrado ? 0 : 1}`).join("|");
const huellaBeto = beto.lista.map((n) => `${clave(n.id)}:${n.borrado ? 0 : 1}`).join("|");
console.log("huellas identicas:", huellaAna === huellaBeto);

flowchart TD
A[fase cero: base comun HOLA] --> B[ana escribe espacio MUNDO]
A --> C[beto escribe espacio CRUEL y borra la H]
B --> D[ana recibe lo de beto en orden inverso]
C --> E[beto recibe lo de ana en orden directo]
D --> F[OLA CRUEL MUNDO]
E --> F
F --> G[misma huella interna y cola vacia]
style B fill:#89b4fa,color:#11111b
style C fill:#a6e3a1,color:#11111b
style F fill:#f9e2af,color:#11111b
style G fill:#cba6f7,color:#11111b

Y las colas de pendientes vacías son la tercera parte del certificado. Si una operación se hubiera quedado atascada esperando un ancla, el texto podría coincidir por casualidad —al fin y al cabo, faltarían caracteres en un sitio que quizá no se nota— mientras la estructura ya habría divergido. Comprobar pendientes.length === 0 en las dos réplicas es lo que convierte parece igual en ha visto todo y ha integrado todo.

Todas las permutaciones, no una muestra

Un único orden de entrega no prueba nada; probaría, como mucho, que ese orden concreto funciona. La prueba honesta es exhaustiva: entregar a Ana las siete operaciones de Beto en cada una de las cinco mil cuarenta permutaciones posibles, y a Beto las seis de Ana en cada una de las setecientas veinte, y comprobar que el conjunto de resultados distintos tiene exactamente un elemento.

function* permutaciones(a) {
  if (a.length <= 1) { yield a; return; }
  for (let i = 0; i < a.length; i++)
    for (const resto of permutaciones([...a.slice(0, i), ...a.slice(i + 1)]))
      yield [a[i], ...resto];
}

const finales = new Set();
for (const orden of permutaciones([0, 1, 2, 3, 4, 5, 6])) {
  const { ana, deBeto } = escena();                 // escenario recien montado
  for (const i of orden) recibir(ana, deBeto[i]);
  finales.add(texto(ana) + "|" + ana.pendientes.length);
}
console.log("resultados distintos:", [...finales]);

permutaciones de las 7 operaciones de beto entregadas a ana: 5040
resultados distintos: "OLA CRUEL MUNDO|0"

permutaciones de las 6 operaciones de ana entregadas a beto: 720
resultados distintos: "OLA CRUEL MUNDO|0"

Cinco mil setecientos sesenta órdenes de entrega, un solo resultado y ninguna operación atascada. Fíjate en que la prueba incluye los órdenes que violan la causalidad de la forma más brutal posible: el borrado entregado antes que la inserción del nodo que borra, el último carácter de una ráfaga entregado antes que el primero, y todas las combinaciones intermedias. La cola de pendientes las absorbe y el bucle de reintento las resuelve en cuanto llega la pieza que faltaba.

Conviene notar qué parte del sistema está soportando esa hostilidad, porque no es el algoritmo de ordenación. La regla de desempate no sabe nada del orden de llegada y nunca lo ha sabido: recibe un nodo y un array y coloca. Lo que absorbe el desorden es la pareja formada por la comprobación del padre y la cola de reintento, y esa pareja es diminuta —cinco líneas entre las dos— comparada con la contabilidad de secuencias que necesitaría un sistema que dependiera del orden. Es un buen sitio para medir la diferencia de esfuerzo entre las dos filosofías: aquí, tolerar cualquier permutación de entrega no costó un protocolo, costó una cola.

Y hay un caso límite que la prueba también cubre sin que se note: la entrega repetida. Si en lugar de permutar entregas dos veces la misma operación, la comprobación de duplicado de aplicar devuelve verdadero sin tocar nada y el resultado es idéntico. Esa propiedad es la que permite que la capa de red sea deliberadamente tonta —reenviar todo lo que no se confirmó, reenviar el lote entero al reconectar, no llevar registro de qué vio cada par— sin poner en riesgo la corrección. Merece la pena añadirla explícitamente a tu conjunto de pruebas: barajar y además duplicar al azar una de cada tres operaciones.