La reducción de casos: de doscientas operaciones a las tres culpables

El generador acaba de encontrar una divergencia en una historia de doscientos eventos repartidos entre cuatro réplicas, con dos particiones y once entregas duplicadas. Enhorabuena: acabas de recibir la información menos accionable posible. Un contraejemplo de ese tamaño demuestra que existe un error y no ayuda en absoluto a encontrarlo, porque el trabajo de diagnóstico consiste en distinguir los tres eventos que provocan el fallo de los ciento noventa y siete que solo estaban de paso, y ese trabajo es exponencial si se hace a mano. La reducción automática es la pieza que convierte esta técnica de una curiosidad académica en una herramienta de ingeniería, y su idea cabe en una frase: probar sistemáticamente casos más pequeños y quedarse con los que siguen fallando, hasta que ningún recorte adicional falle. Lo interesante no es el algoritmo, que es trivial, sino todo lo que hay que garantizar para que funcione sobre historias concurrentes en lugar de sobre listas de números.

Por qué un contraejemplo grande no vale casi nada

El coste de depurar un fallo de convergencia no crece con la dificultad conceptual del error sino con el tamaño de la traza que hay que leer. Ante doscientos eventos, la pregunta que hay que responder es cuál de los subconjuntos posibles es el responsable, y el número de subconjuntos de doscientos elementos tiene sesenta y un dígitos. Nadie hace eso a ojo, así que lo que ocurre en la práctica es que alguien empieza a borrar eventos al azar durante media hora, se cansa y clasifica el fallo como intermitente.

Ante tres eventos, en cambio, el diagnóstico es inmediato y de una clase distinta: se lee la historia entera de un vistazo, se identifica la interacción y muy a menudo se reconoce una clase de error en lugar de una instancia. Dos añadidos concurrentes del mismo valor en réplicas distintas; una operación local y una entrega en el orden inverso al esperado; un borrado que precede a su propio añadido. Estos patrones tienen nombre en la literatura y la persona que los ve reducidos los reconoce, mientras que la misma persona no los reconocería enterrados en doscientos eventos.

El algoritmo: quitar, simplificar, repetir

El reductor recibe un candidato que falla y una función que decide si un candidato sigue fallando, y devuelve un candidato mínimo. Su estructura es un descenso voraz: mientras algún recorte siga fallando, se adopta y se vuelve a empezar.

function reducir(historia, falla) {
  let actual = historia;
  let mejoro = true;
  while (mejoro) {
    mejoro = false;
    for (const candidato of candidatos(actual)) {
      if (falla(candidato)) { actual = candidato; mejoro = true; break; }
    }
  }
  return actual;
}

Toda la inteligencia está en candidatos, que enumera los recortes en el orden que más reduce por intento. La primera fase borra bloques contiguos empezando por los grandes y bajando por mitades, que es la idea del depurado por deltas: si medio guion se puede tirar de una vez, tirarlo cuesta un intento en lugar de cien. La segunda fase, cuando ya no se puede borrar nada, simplifica los campos numéricos de cada evento acercándolos a cero, lo que convierte índices y destinos arbitrarios en los más pequeños que aún reproducen el fallo.

function* candidatos(h) {
  // Fase 1: borrar bloques contiguos, de grandes a pequenos.
  for (let n = h.length; n >= 1; n = Math.floor(n / 2)) {
    for (let i = 0; i + n <= h.length; i += 1) {
      yield [...h.slice(0, i), ...h.slice(i + n)];
    }
    if (n === 1) break;
  }
  // Fase 2: acercar cada campo numerico a cero.
  for (let i = 0; i < h.length; i += 1) {
    const ev = h[i];
    for (const campo of ['indice', 'destino', 'replica']) {
      if (typeof ev[campo] === 'number' && ev[campo] > 0) {
        const copia = h.slice();
        copia[i] = { ...ev, [campo]: ev[campo] - 1 };
        yield copia;
      }
    }
    if (ev.op && ev.op.valor > 0) {
      const copia = h.slice();
      copia[i] = { ...ev, op: { ...ev.op, valor: ev.op.valor - 1 } };
      yield copia;
    }
  }
}

El orden de las dos fases importa y no es intercambiable. Borrar primero es lo que hace barato el proceso, porque cada borrado exitoso elimina de golpe todos los campos que habría habido que simplificar. Simplificar primero gastaría miles de intentos puliendo eventos que después van a desaparecer. La regla general es reducir siempre por la dimensión que más recorta el espacio restante, y en una historia esa dimensión es la longitud.

Reducir historias es más difícil que reducir listas

Sobre una lista de enteros, cualquier sublista es un candidato válido. Sobre una historia concurrente, no: quitar un evento puede producir un guion que el sistema no podría haber generado nunca, y entonces el reductor deja de estar buscando el mismo fallo. Los tres requisitos que la reducción impone al resto del sistema son la parte que se descubre tarde y duele.

El primero es el determinismo. La función que decide si un candidato falla debe dar siempre la misma respuesta para el mismo candidato. Si el simulador consulta el reloj, si la fusión ordena por un identificador aleatorio no sembrado o si el generador se invoca dentro del bucle de ejecución, el descenso voraz se convierte en un paseo aleatorio: adopta candidatos que no fallaban y descarta los que sí, y termina en cualquier sitio. Este es el motivo real por el que la lección anterior insistía en separar el guion de la ejecución.

El segundo es la validez. Un candidato debe seguir siendo una historia bien formada. Hay dos maneras de conseguirlo y conviene elegir a conciencia. La reparadora normaliza el candidato después de recortarlo, ajustando índices que ahora apuntan fuera de rango y descartando entregas sin mensaje disponible; es la vía del simulador de la lección anterior, que aplica el módulo a cada índice y así hace válido cualquier guion. La estructural genera candidatos que son válidos por construcción, lo que exige que el reductor entienda la semántica de la historia y es bastante más código.

flowchart TB
A[contraejemplo de 40 eventos] --> B[borrar bloque grande]
B --> C{sigue fallando}
C -->|si| D[adoptar y reiniciar]
C -->|no| E[probar bloque menor]
E --> C
D --> F{queda algun recorte que falle}
F -->|si| B
F -->|no| G[minimo local de 2 eventos]
style G fill:#a6e3a1,color:#11111b
style C fill:#89b4fa,color:#11111b

El tercero es la monotonía del criterio de parada, que evita que el reductor entre en un ciclo. Cada candidato adoptado debe ser estrictamente menor que el anterior según una medida bien fundada, típicamente el par formado por la longitud del guion y la suma de sus campos numéricos. Sin esa garantía, una simplificación que aumente un campo o un recorte que reordene eventos puede devolver al reductor a un estado ya visitado y dejarlo girando para siempre.

De cuarenta eventos a dos

Un ejemplo concreto cierra el argumento. Tomemos un registro de última escritura mal implementado: guarda una marca lógica y un valor, y al fusionar se queda con el estado cuya marca es mayor o igual. Es un error clásico, porque cuando dos réplicas producen la misma marca con valores distintos, la fusión deja de ser conmutativa y el desempate por identificador de réplica, que es lo que faltaba, no existe.

const lww = {
  vacio: () => ({ t: 0, valor: null }),
  aplicar: (s, op) => ({ t: s.t + 1, valor: op.valor }),
  unir: (a, b) => (b.t >= a.t ? b : a),   // falta el desempate por replica
  iguales: (a, b) => a.t === b.t && a.valor === b.valor,
};

let encontrado = null;
for (let s = 0; s < 200 && !encontrado; s += 1) {
  const h = generar(motor(0xabc ^ s));
  if (!converge(h)) encontrado = h;
}

const minimo = reducir(encontrado, (h) => !converge(h));
console.log(encontrado.length, minimo.length);   // 40 2
console.log(JSON.stringify(minimo));
// [{"clase":"local","replica":0,"op":{"valor":0}},
//  {"clase":"local","replica":1,"op":{"valor":1}}]

El contraejemplo mínimo tiene dos eventos y no necesita comentario: dos réplicas ejecutan una operación local cada una, sin ninguna comunicación previa, y por tanto ambas llegan a la marca uno con valores distintos. En el reposo, cada réplica fusiona en su propio orden y la que fusiona en último lugar gana. La ausencia del desempate salta a la vista. Compárese con la utilidad de los cuarenta eventos originales, donde la misma situación estaba oculta entre dieciocho entregas y tres duplicados.

Conviene ser honesto sobre el límite del método. El resultado es un mínimo local: ningún candidato del enumerador falla, pero podría existir otro contraejemplo más pequeño estructuralmente distinto que el descenso voraz no alcanza. En el caso anterior el mínimo local coincide con el global porque dos eventos es lo mínimo imaginable, pero eso no es la norma. Un reductor que se detiene en seis eventos no está diciendo que no exista uno de tres: está diciendo que ninguno de los recortes que sabe proponer sigue fallando, y ampliar el enumerador con recortes nuevos es lo que empuja ese límite.