El generador de historias concurrentes: un simulador mínimo

La propiedad de convergencia necesita un sujeto sobre el que hablar, y ese sujeto no es la función de fusión sino un sistema completo: varias réplicas con estado propio, una red que transporta mensajes con retrasos arbitrarios y un planificador que decide qué ocurre a continuación. Escribir ese simulador es el trabajo central del nivel y la parte que casi nadie hace, porque parece infraestructura y en realidad es especificación: el simulador es el documento donde queda escrito qué le concedes a la red y qué no. Si tu simulador no duplica mensajes, has decidido que tu transporte nunca los duplica, y esa decisión estará ahí aunque nadie la haya discutido. Lo que sigue es un simulador completo en unas ochenta líneas, con el tipo replicado como parámetro para que sirva igual a un conjunto, a un contador o a una secuencia, y con la red expresada como una función que puede negarse a entregar.

El modelo mínimo: réplicas, red y planificador

Un simulador útil descansa sobre una abstracción estrecha del tipo replicado. Un CRDT basado en estado se describe por completo con cuatro funciones puras: el estado inicial, la aplicación de una operación local, la fusión de dos estados y la lectura del valor observable. Nada más. Si el simulador solo depende de esas cuatro, servirá para todos los tipos que el track ha construido sin modificarlo.

const orSet = {
  vacio: () => ({ vivos: new Map(), muertos: new Set() }),
  aplicar(s, op) {
    const vivos = new Map(s.vivos), muertos = new Set(s.muertos);
    if (op.clase === 'anadir') vivos.set(op.etiqueta, op.valor);
    else for (const [et, v] of vivos) if (v === op.valor) { muertos.add(et); vivos.delete(et); }
    return { vivos, muertos };
  },
  unir(a, b) {
    const muertos = new Set([...a.muertos, ...b.muertos]);
    const vivos = new Map([...a.vivos, ...b.vivos]);
    for (const et of muertos) vivos.delete(et);
    return { vivos, muertos };
  },
  observar: (s) => [...new Set(s.vivos.values())].sort(),
};

La red se modela como una lista de mensajes en vuelo. Cada mensaje lleva su emisor y una copia del estado de ese emisor en el instante del envío, y permanece en la lista hasta que alguien lo entrega. Esa lista es la fuente de todo el desorden: entregar el mensaje que está en la posición cero es una red que preserva el orden, entregar uno cualquiera es una red que reordena, y entregar sin sacarlo de la lista es una red que duplica. El planificador, por su parte, es la historia misma: en lugar de decidir sobre la marcha con azar, el generador produce una lista de eventos y el simulador la ejecuta paso a paso. Esa separación no es estética, es lo que permite que un contraejemplo sea un dato serializable, reproducible y reducible, en vez de una traza que solo existió una vez.

El simulador entero

Tres clases de evento bastan para cubrir todo lo que el nivel necesita. Una operación local, que muta la réplica y encola el estado resultante como mensaje pendiente. Una entrega, que toma un mensaje de la red y lo fusiona en la réplica destino. Y el reposo final, que no es un evento del guion sino una fase que el simulador ejecuta siempre al terminar.

function ejecutar(tipo, n, historia, alcanzable = () => true) {
  const replicas = Array.from({ length: n }, () => tipo.vacio());
  const red = [];
  for (const ev of historia) {
    const r = ev.replica % n;
    if (ev.clase === 'local') {
      replicas[r] = tipo.aplicar(replicas[r], ev.op);
      red.push({ de: r, estado: replicas[r] });
    } else if (ev.clase === 'entrega' && red.length > 0) {
      const i = ev.indice % red.length, msg = red[i], destino = ev.destino % n;
      if (!ev.duplicado) red.splice(i, 1);
      if (destino !== msg.de && alcanzable(msg.de, destino, ev.reloj)) {
        replicas[destino] = tipo.unir(replicas[destino], msg.estado);
      }
    }
  }
  // Reposo: cada replica ve todo lo pendiente, pero en su propio orden.
  const pendientes = red.map((m) => m.estado).concat(replicas.slice());
  for (let d = 0; d < n; d += 1) {
    for (let k = 0; k < pendientes.length; k += 1) {
      replicas[d] = tipo.unir(replicas[d], pendientes[(d + k) % pendientes.length]);
    }
  }
  return replicas;
}

Merece la pena señalar tres decisiones del código porque cada una responde a un error frecuente. El operador de módulo sobre ev.indice y sobre ev.destino convierte cualquier número en un evento válido, lo que evita tener que filtrar guiones mal formados y, sobre todo, hace que el reductor pueda simplificar un número sin romper la historia. La comparación destino !== msg.de impide que una réplica se fusione con su propio pasado, que no es un error pero gasta casos sin ejercitar nada. Y el mensaje lleva el estado completo del emisor, no la operación: eso es lo que hace del simulador un modelo de CRDT basado en estado, y adaptarlo a uno basado en operaciones exige encolar la operación y garantizar entrega causal, que es un cambio pequeño y una discusión larga.

Particiones, duplicados y reordenación

El parámetro alcanzable es donde vive el modelo de fallos, y su firma toma emisor, destino y un reloj lógico que no es más que la posición del evento en el guion. Con esa firma se expresan todas las patologías interesantes sin tocar el simulador.

flowchart TB
E[evento de entrega] --> A{alcanzable de a en t}
A -->|no| P[mensaje descartado, la particion lo bloquea]
A -->|si| D[fusion en la replica destino]
P --> R[queda en la red y se entregara en el reposo]
D --> M{duplicado}
M -->|si| K[el mensaje sigue en la red]
M -->|no| Q[el mensaje se retira de la red]
style P fill:#f38ba8,color:#11111b
style D fill:#a6e3a1,color:#11111b

Una partición se escribe como un predicado que aísla un subconjunto de réplicas durante una ventana del guion. La versión más simple separa una réplica del resto entre dos instantes, y basta para provocar la situación que más fallos revela: una réplica que sigue operando a ciegas y reaparece con un lote grande de cambios antiguos.

// La replica 0 queda aislada entre los instantes 10 y 25 del guion.
const parte = (de, a, t) => !(t > 10 && t < 25 && (de === 0) !== (a === 0));

El generador de historias completa el cuadro. Su trabajo es producir guiones cuya forma se parezca a la de una sesión real y cuyos parámetros estén ajustados para que la concurrencia sea alta, no para que sea realista en volumen.

function generarHistoria(r, n = 3, largo = 40) {
  const h = [];
  for (let k = 0; k < largo; k += 1) {
    const replica = Math.floor(r() * n);
    if (r() < 0.5) {
      const clase = r() < 0.7 ? 'anadir' : 'borrar';
      const op = { clase, valor: Math.floor(r() * 5), etiqueta: `${replica}-${k}` };
      h.push({ clase: 'local', replica, op });
    } else {
      h.push({ clase: 'entrega', replica, destino: Math.floor(r() * n),
        indice: Math.floor(r() * 8), duplicado: r() < 0.15, reloj: k });
    }
  }
  return h;
}

El estado de reposo y la aserción final

La convergencia no afirma que las réplicas coincidan en todo momento, sino que coinciden cuando ya no queda nada por entregar. Definir ese momento es el punto donde el simulador puede engañarte, y el error es sutil y silencioso. La implementación ingenua del reposo recorre los mensajes pendientes y los fusiona en todas las réplicas en el mismo orden, y luego hace una ronda en la que cada réplica fusiona el estado de todas las demás, también en el mismo orden. El resultado es que todas ejecutan exactamente la misma secuencia de fusiones, de modo que terminan iguales aunque la fusión no sea conmutativa: el reposo mal implementado demuestra convergencia por construcción y anula la prueba entera. La versión de arriba evita la trampa rotando el orden en cada réplica, de forma que dos réplicas nunca ven la misma secuencia.

Reposo ingenuo   todas fusionan en el mismo orden
                 -> converge siempre, incluso con fusion no conmutativa
Reposo rotado    cada replica fusiona en un orden distinto
                 -> solo converge si la fusion es de verdad conmutativa

Con el reposo bien definido, la aserción es una línea: se lee el valor observable de cada réplica y se comprueba que todos son iguales entre sí, sin comparar contra ningún resultado esperado, porque no lo hay.

function convergen(tipo, n, historia, alcanzable) {
  const fin = ejecutar(tipo, n, historia, alcanzable);
  const ref = JSON.stringify(tipo.observar(fin[0]));
  return fin.every((e) => JSON.stringify(tipo.observar(e)) === ref);
}