Por qué los ejemplos no bastan: un punto en un espacio inmenso

Has implementado un conjunto replicado y una secuencia, y ambos funcionan: escribes una prueba con dos réplicas, aplicas tres operaciones a cada una, las fusionas en los dos sentidos y compruebas que el resultado coincide. La prueba pasa, el color es verde y la sensación de haber verificado algo es completa. Esa sensación es el error más caro de esta disciplina, porque lo que acabas de comprobar es que el sistema converge en un orden de entrega concreto, y el número de órdenes que la red puede producir con esas mismas seis operaciones es de veinte. Con tres réplicas y cinco operaciones cada una son setecientas cincuenta y seis mil setecientas cincuenta y seis. Con cuatro y diez, el número tiene veintidós dígitos. Un caso escrito a mano no es una muestra pequeña de ese espacio: es un punto, elegido además por la persona que escribió el algoritmo y que por tanto elige justo donde no sospecha nada. Esta lección hace la aritmética que casi nunca se hace, explica por qué la cobertura de líneas es aquí un indicador vacío y prepara el cambio de enunciado que ocupa el resto del nivel.

La aritmética que nadie hace

Fijemos el objeto de estudio con precisión, porque la palabra historia se usa con demasiada ligereza. Una historia es la secuencia de eventos que ocurren en un sistema replicado: operaciones locales en cada réplica y entregas de mensajes entre réplicas. Dos historias con las mismas operaciones pero distinto orden de entrega son historias distintas, y un algoritmo correcto debe converger en todas ellas. Ese es el universo que hay que cubrir.

Si hay n réplicas y cada una ejecuta m operaciones que deben acabar aplicándose en todas, el número de órdenes globales compatibles con el orden local de cada réplica es el coeficiente multinomial que reparte n por m posiciones en grupos de tamaño m. La restricción importa: dentro de una réplica el orden está fijado por la causalidad, así que no se cuentan todas las permutaciones sino solo las que respetan cada secuencia local.

function factorial(n) {
  let r = 1n;
  for (let i = 2n; i <= BigInt(n); i += 1n) r *= i;
  return r;
}

// Ordenes de entrega compatibles con el orden local de cada replica.
function entrelazados(replicas, opsPorReplica) {
  let r = factorial(replicas * opsPorReplica);
  for (let i = 0; i < replicas; i += 1) r /= factorial(opsPorReplica);
  return r;
}

for (const [n, m] of [[2, 2], [2, 3], [3, 5], [4, 10]]) {
  console.log(n, m, entrelazados(n, m).toString());
}
// 2 2  6
// 2 3  20
// 3 5  756756
// 4 10 4705360871073570227520

Conviene detenerse en la última fila, porque cuatro réplicas con diez operaciones cada una es una sesión de colaboración modesta: cuatro pestañas abiertas y diez pulsaciones por pestaña. Cuatro mil setecientos trillones de órdenes de entrega. Si tu suite ejecutase un millón de historias por segundo desde el Big Bang, habrías cubierto una fracción despreciable. No es que las pruebas manuales cubran poco: es que la noción de porcentaje cubierto deja de tener sentido operativo, y con ella deja de tenerlo la intuición de que probar más casos a mano acerca a algo.

Lo que un ejemplo sabe hacer y lo que no

De aquí no se sigue que las pruebas por ejemplo sobren, y conviene decirlo antes de criticarlas porque la conclusión perezosa sería tirarlas. Un ejemplo escrito a mano hace tres cosas que ninguna generación automática hace igual de bien, y las tres siguen siendo necesarias.

Lo que un ejemplo no puede hacer es responder a la pregunta de este nivel, que no es si el algoritmo funciona en el caso que se te ocurrió sino si funciona en todos. Y aquí aparece el indicador que más daño hace: la cobertura de código. Una suite de doce ejemplos puede ejecutar el cien por cien de las líneas de tu función de fusión, incluidas todas las ramas, y no haber tocado más que doce puntos de un espacio de veintidós dígitos. La cobertura mide el código visitado, no el espacio de estados explorado, y en un sistema replicado esas dos magnitudes no guardan ninguna relación. La función de fusión tiene pocas ramas; lo que es grande es el conjunto de secuencias de llamadas.

Que mide cada indicador y sobre que espacio

  cobertura de lineas .... lineas ejecutadas / lineas escritas
                           denominador pequeno, se satura enseguida
  cobertura de ramas ..... ramas tomadas / ramas del codigo
                           mejor, pero sigue hablando del codigo
  espacio de historias ... historias probadas / historias posibles
                           denominador astronomico, nunca se satura

La tercera fila es la única que habla del problema, y nótese que ninguna herramienta la calcula por ti. Hay que escribirla a mano y hay que aceptar que su valor será siempre indistinguible de cero. Que un indicador útil dé siempre cero resulta incómodo, y esa incomodidad explica en buena parte por qué la profesión prefiere los dos primeros: dan números que suben, que se pueden poner en un panel y que producen la sensación de progreso.

Hay además un sesgo que agrava lo anterior y que ninguna métrica detecta: los ejemplos los escribe quien escribió el algoritmo, poco después de escribirlo, con su modelo mental intacto. Se prueba lo que se ha pensado. Los fallos de convergencia viven exactamente en las interacciones que no se pensaron, es decir, en el complemento del conjunto que esa persona es capaz de enumerar. No es falta de rigor: es una imposibilidad estructural, y la única salida es que las historias las proponga algo que no comparta tu modelo mental.

Tres ejes que multiplican, no que suman

El espacio no crece por una sola causa, y separar las causas es lo que después permite diseñar el generador. Son tres ejes independientes, y su efecto es multiplicativo porque cualquier combinación de los tres es alcanzable.

flowchart TB
H[una historia concreta] --> A[eje 1 que operaciones y en que replica]
H --> B[eje 2 en que orden se entregan]
H --> C[eje 3 que hace la red con cada mensaje]
A --> A1[anadir borrar mover insertar]
B --> B1[todos los ordenes compatibles con la causalidad]
C --> C1[duplicar perder retrasar particionar]
A1 --> Z[espacio total igual al producto de los tres]
B1 --> Z
C1 --> Z
style Z fill:#f38ba8,color:#11111b
style B1 fill:#f9e2af,color:#11111b

El primer eje es el que todo el mundo prueba y el menos interesante, porque es el que el desarrollador controla y entiende. El segundo es el que produce casi todos los fallos reales de convergencia, porque es donde se manifiesta que la fusión no era conmutativa o no era asociativa. El tercero es el que separa un algoritmo que funciona en el laboratorio de uno que funciona en una red de verdad, y es también el que casi nadie modela porque exige escribir un simulador en lugar de llamar a la función de fusión.

Que patologia de red pone a prueba que ley algebraica

  reordenacion de entregas ....... conmutatividad de la fusion
  agrupacion distinta de mensajes  asociatividad de la fusion
  entrega duplicada .............. idempotencia de la fusion
  entrega tardia tras particion .. monotonia del estado
  arranque desde estado parcial .. clausura del conjunto de estados

Esa tabla es más que una curiosidad mnemotécnica: es el argumento de por qué las tres leyes del semirretículo que se demostraron en niveles anteriores son exactamente las que hay que comprobar, y no una lista arbitraria. Cada ley es la respuesta a una patología concreta que la red puede infligir. Si una implementación viola la idempotencia, no fallará hasta que un mensaje llegue dos veces; y un mensaje llegará dos veces, porque toda capa de transporte con reintentos los duplica tarde o temprano.

Del ejemplo al cuantificador

La salida no consiste en escribir más ejemplos sino en cambiar la forma del enunciado. Un ejemplo afirma que con esta entrada concreta el sistema produce esta salida concreta. Lo que hace falta afirmar es algo con un cuantificador universal delante: para toda historia de operaciones sobre estas réplicas, con cualquier orden de entrega y cualquier patología de red admisible, todas las réplicas terminan en el mismo estado.

El cambio parece cosmético y no lo es, porque obliga a resolver dos problemas nuevos que el ejemplo escondía. El primero es de dónde salen las historias, y su respuesta es un generador que sepa producir historias bien formadas y variadas. El segundo es cuál es el resultado esperado, y su respuesta ya no puede ser un valor escrito a mano, porque nadie sabe qué debe dar una historia aleatoria de cuarenta eventos.

Ese segundo problema tiene nombre propio en la literatura de pruebas y conviene usarlo, porque reaparecerá en todo el nivel: es el problema del oráculo, la cuestión de cómo decidir si una salida es correcta cuando no se dispone de la respuesta. Hay tres salidas conocidas y las tres se usan aquí. La primera es comparar contra una implementación de referencia más lenta pero obviamente correcta, que en este dominio suele ser un algoritmo cuadrático escrito para que se lea. La segunda es comprobar una relación metamórfica, es decir, que dos ejecuciones distintas relacionadas entre sí produzcan resultados relacionados de la manera prevista. Y la tercera, la que domina este nivel, es comprobar una invariante: una afirmación que debe ser cierta del resultado sin necesidad de conocerlo.

La convergencia es exactamente una invariante de ese tipo, y por eso resulta tan cómoda: la aserción es una relación entre réplicas y no un valor. No compruebas que el resultado sea el correcto, compruebas que todas las réplicas coinciden. Ese giro es el que hace posible probar lo improbable, y es también el que trae de vuelta la advertencia del nivel treinta y tres, porque coincidir no es lo mismo que estar bien: una implementación que borrase todo el contenido en cada fusión convergería siempre y pasaría la propiedad sin inmutarse. Guarda esa objeción, porque la quinta lección del nivel la responde entera.