Por qué pasa: converger no obliga a ser sensato

La lección anterior dejó un cadáver sin asesino: un resultado inservible producido por un algoritmo al que no se le puede reprochar nada. La explicación no está escondida en ningún rincón oscuro de la implementación, sino a plena vista en el enunciado mismo de lo que estos sistemas prometen. Cuando se dice que un tipo de dato replicado es correcto, se está afirmando una cosa muy concreta y muy limitada: que dos réplicas que han recibido las mismas actualizaciones exhiben el mismo estado. Léelo otra vez y busca en esa frase a la persona que va a leer el resultado. No está. No aparece, no se la menciona, no se cuantifica sobre ella. La especificación relaciona réplicas con réplicas, y el mundo —incluido quien escribió lunes y esperaba volver a verlo— queda íntegramente fuera del alcance del cuantificador. Esta lección demuestra que ese hueco no es una lectura maliciosa del enunciado sino su contenido exacto, y lo hace construyendo algoritmos deliberadamente absurdos que aprobarían el examen con nota.

Qué promete exactamente la especificación

La consistencia eventual fuerte, que es la garantía que estos sistemas ofrecen, se enuncia con tres condiciones y conviene tenerlas delante para poder señalar el hueco con el dedo. La primera es de entrega: toda actualización aplicada en una réplica correcta acaba llegando a todas las demás. La segunda es de convergencia: dos réplicas que han recibido el mismo conjunto de actualizaciones tienen estados equivalentes. La tercera es de terminación: todos los métodos concluyen.

Léelas buscando activamente dónde se menciona el contenido del estado, porque el ejercicio es breve. La primera habla de mensajes que llegan. La segunda habla de dos estados que coinciden. La tercera habla de cómputos que acaban. Ninguna de las tres dice nada sobre qué debe contener el estado en cuestión, y esa ausencia no es un descuido de la redacción: es lo que hace que el enunciado sea universal y aplicable a cualquier tipo de dato, que era exactamente el objetivo de quienes lo formularon.

Nada de esto es una interpretación torcida ni una lectura de abogado. Es la formulación estándar, la que aparece en los textos de referencia y la que cualquier implementación cita al justificar su corrección. La crítica de este nivel no consiste en leerla mal, sino en leerla exactamente como está escrita.

Del lado algebraico, la maquinaria que garantiza la segunda condición es igual de precisa. El estado vive en un retículo con una operación de fusión que debe ser conmutativa, asociativa e idempotente. Conmutativa para que el orden de llegada de los mensajes no importe; asociativa para que el agrupamiento tampoco importe; idempotente para que recibir dos veces lo mismo no altere el resultado. Cualquier función que satisfaga esas tres leyes sobre un dominio bien ordenado produce convergencia, y el teorema no pide nada más.

Ahí está todo. Y ahora la pregunta que este nivel entero responde: ¿qué restringe esa colección de enunciados sobre qué valor concreto devuelve la fusión? La respuesta es que nada en absoluto. Las tres leyes son restricciones sobre la forma de la función, no sobre su imagen. Dicen cómo debe comportarse la fusión respecto de sí misma al reordenar, reagrupar y repetir sus argumentos, y son completamente mudas respecto de la relación entre el resultado y aquello que los usuarios pretendían.

El contraste con otras áreas de la informática ayuda a medir lo insólito de la situación. Cuando se especifica una función de ordenación, se exige que la salida sea una permutación de la entrada y que esté ordenada: hay una condición sobre el resultado. Cuando se especifica una transacción, se exige que el estado final satisfaga las invariantes declaradas: hay una condición sobre el resultado. Aquí no hay ninguna condición sobre el resultado, solo condiciones sobre la relación de la función consigo misma. Es una especificación puramente estructural, y por eso admite cualquier semántica.

flowchart TB
E[espacio de todas las funciones de fusion posibles] --> C[las que son conmutativas asociativas e idempotentes]
C --> V[convergen y por tanto son correctas]
V --> S[subconjunto que ademas produce resultados aceptables]
V --> N[subconjunto que produce resultados absurdos]
N --> X[la especificacion clasica no distingue estos dos subconjuntos]
style V fill:#89b4fa,color:#11111b
style S fill:#a6e3a1,color:#11111b
style N fill:#f38ba8,color:#11111b

Dos algoritmos absurdos que aprobarían el examen

La forma más rápida de comprobar que un hueco existe es meter el brazo por él, y en lógica eso se hace con contraejemplos. Tomemos el mismo caso de la lección anterior —base Nota: , Ana escribe lunes, Beto escribe martes— y diseñemos dos algoritmos de texto colaborativo que nadie querría usar y que, sin embargo, satisfacen punto por punto todo lo enunciado arriba.

El primero es el aniquilador. Su regla de fusión es: si las dos réplicas tienen estados distintos, el resultado es la cadena vacía. Compruébalo contra las tres leyes. Es conmutativa, porque no mira el orden de sus argumentos. Es asociativa, porque el vacío absorbe cualquier composición posterior. Es idempotente, porque fusionar un estado consigo mismo lo deja igual. Toda réplica que reciba el mismo conjunto de actualizaciones llegará al mismo estado, que será el vacío. Convergencia garantizada, teorema satisfecho, aplicación inservible.

Vale la pena notar que el aniquilador no es una curiosidad de pizarra: es la forma extrema de una política que existe en sistemas reales bajo el nombre de descartar y volver a empezar. Cada vez que un sistema resuelve una discrepancia tirando el estado local y recargando desde otro sitio está aplicando una versión atenuada de la misma idea, y lo hace porque converger es lo que se le pidió. Es la prueba de que la especificación no solo permite el absurdo en teoría, sino que también legitima sus parientes cercanos en la práctica.

Fíjate además en que el aniquilador tiene una virtud perversa: es el algoritmo más simple, más rápido y más fácil de verificar de todos los posibles. Si el único criterio fuese la convergencia, ganaría cualquier comparativa. Que a nadie se le ocurra proponerlo demuestra que todos los que trabajamos en esto llevamos en la cabeza un criterio adicional que jamás escribimos, y ese criterio tácito es precisamente el objeto de todo este nivel.

El segundo es más interesante porque anticipa una objeción evidente. Alguien dirá que el aniquilador es un truco barato porque destruye datos, y que basta con exigir además que no se pierda nada. Bien: el ordenador alfabético conserva absolutamente todos los caracteres escritos por todo el mundo. Su regla de fusión es la unión de los caracteres, y su renderizado es mostrarlos en orden alfabético. Es conmutativa, asociativa e idempotente por ser una unión de conjuntos, converge sin excepción y no descarta ni un solo dato.

Ana escribio        lunes
Beto escribio       martes

aniquilador         Nota:
ordenador alfabetico Nota: aeelmnrsstu
algoritmo real      Nota: mlaurnteess

Coloca las dos últimas líneas una junto a otra y sostén la mirada un momento. aeelmnrsstu es la salida de un algoritmo construido a propósito para ser ridículo, y mlaurnteess es la salida de un algoritmo publicado, implementado y desplegado en producción. Ambas contienen exactamente los mismos once caracteres, ambas son deterministas, ambas convergen y ninguna de las dos es legible. La diferencia entre el chiste y el estado del arte no es de naturaleza: es de grado, y en este caso concreto ni siquiera de mucho grado.

Cabe la objeción de que estos dos algoritmos son hombres de paja y que nadie los propondría en serio. La objeción es cierta y no viene al caso, porque su función no es competir con nada sino delimitar un espacio. Un contraejemplo no tiene que ser plausible: tiene que ser válido. Y lo que estos dos establecen, con la misma fuerza que un contraejemplo cualquiera en matemáticas, es que la especificación vigente no distingue entre el mejor algoritmo de edición colaborativa jamás escrito y un generador de ruido determinista. Si una definición no separa esos dos objetos, es que le falta algo, y ese algo no lo va a suplir el sentido común de quien implementa.

Conviene además notar que la distancia entre el chiste y la realidad se estrecha justo donde más duele. En un documento donde nadie edita concurrentemente, cualquier algoritmo funciona bien, incluidos los dos absurdos, porque nunca llegan a fusionar nada. La diferencia entre el buen algoritmo y el malo solo se manifiesta bajo concurrencia, que es exactamente la situación que estos sistemas existen para gestionar. Un criterio de corrección que no discrimina en el único escenario que motiva la construcción entera no es un criterio incompleto: es un criterio que mira hacia otro lado.

Dónde está el hueco: el retículo no conoce a nadie

Una vez visto que se puede meter el brazo, conviene entender por qué el agujero está ahí y por qué no se tapó antes. La razón es que la teoría se construyó para resolver un problema distinto, y lo resolvió muy bien.

Esta explicación es importante porque cierra el paso a la lectura fácil de todo el nivel, que sería concluir que la teoría de los datos replicados está mal. No lo está: está incompleta respecto de un uso que no era el que motivó su construcción, que es una situación distinta y mucho más común. Confundir ambas cosas lleva a descartar herramientas perfectamente buenas en lugar de a completarlas, y ese error tiene un coste tan alto como el original.

El problema que las réplicas convergentes vinieron a resolver es el de la disponibilidad bajo partición. Su enemigo declarado es la divergencia permanente: dos nodos que, tras reconectarse, siguen mostrando cosas distintas para siempre. Frente a ese enemigo, la convergencia es la victoria completa, y toda la elegancia del retículo está al servicio de demostrarla sin depender del orden de la red. Es un logro genuino y este track lo ha celebrado varias veces con razón.

Conviene además recordar de dónde venía la disciplina, porque explica por qué esa victoria absorbió toda la atención disponible. El punto de partida era un mundo en el que la única forma conocida de mantener réplicas coherentes pasaba por coordinarlas, con todo lo que la coordinación arrastra: latencia, indisponibilidad bajo partición y un punto de serialización que hay que sostener. Demostrar que existía una clase de estructuras capaces de prescindir de esa coordinación sin divergir fue un resultado liberador, y los resultados liberadores tienen la costumbre de fijar la agenda de las dos décadas siguientes. Nadie mira los límites de la puerta que acaba de abrirse.

Pero el enemigo estaba definido como una relación entre réplicas, y por eso la solución también lo es. Escribe la propiedad tal cual: para cualesquiera réplicas A y B que hayan entregado el mismo conjunto de actualizaciones, estado(A) equivale a estado(B). Los cuantificadores recorren réplicas y conjuntos de actualizaciones. No hay ninguna variable que recorra intenciones, ni documentos que alguien vaya a leer, ni frases que alguien quisiera escribir. Una propiedad no puede fallar por algo sobre lo que no habla, y por tanto tampoco puede protegerte de ello.

La consecuencia es que la convergencia es una propiedad relacional y no evaluativa. Relaciona dos objetos del mismo tipo y afirma que coinciden; no evalúa ninguno de los dos contra nada externo. Es exactamente el mismo tipo de enunciado que decir que dos relojes marcan la misma hora, afirmación perfectamente comprobable y perfectamente compatible con que ambos vayan cuatro horas atrasados. Sincronía y exactitud son propiedades independientes, y un sistema puede tener la primera en grado sumo sin tener ni un gramo de la segunda.

El nombre técnico de lo que falta es una especificación de la semántica de la fusión: un enunciado que, dado el estado inicial y las operaciones concurrentes, restrinja el conjunto de estados finales admisibles a un subconjunto propio de los estados convergentes. Sin ese enunciado, todos los resultados convergentes son igual de legítimos y el aniquilador es tan correcto como el mejor editor colaborativo que se haya escrito. Con él, la mayoría de los resultados convergentes quedan descartados y solo unos pocos sobreviven. Ese enunciado no existía.

Y no existía por una razón que conviene no despachar como pereza. Escribir esa especificación es un trabajo de naturaleza distinta al resto de la disciplina, porque no se puede hacer desde dentro del formalismo. Exige decidir, para un dominio concreto y unos usuarios concretos, qué resultados son tolerables, y esa decisión no se deriva de ningún axioma ni se comprueba con ningún demostrador. Es un juicio, y los juicios no se publican con la misma facilidad que los teoremas. La convergencia, en cambio, es universal: sirve para texto, para conjuntos, para contadores y para cualquier cosa, y se demuestra una vez. La asimetría de esfuerzo y de recompensa entre ambas tareas explica bastante bien por qué durante veinte años se hizo una y no la otra.

Converger a un estado que nadie escribió

Hay un último matiz que separa la intercalación de un simple resultado feo, y que explica por qué merece un nivel entero en lugar de un párrafo. Es además el matiz que hace que este caso sirva de criterio para auditar cualquier otro tipo de dato replicado, de modo que conviene formularlo con cuidado. Cuando un sistema elige el valor de Ana y descarta el de Beto, el estado final es al menos un estado que alguien produjo: existió en una réplica, alguien lo escribió y alguien lo vio. Es una elección desafortunada entre alternativas reales.

La intercalación no elige entre alternativas reales: fabrica una tercera que no existió nunca en ninguna parte. mlaurnteess no estuvo jamás en el portátil de Ana ni en el de Beto; no es la aportación de nadie, no representa la intención de nadie y no podría reconstruirse a partir de ninguna decisión humana. Es un estado sintetizado por el algoritmo de fusión y atribuido a dos personas que no lo escribieron. Ya vimos algo emparentado con esto al hablar del conflicto semántico entre campos ligados por una invariante, pero allí hacía falta una invariante de dominio para que apareciera el estado imposible; aquí basta con que dos personas escriban a la vez.

La distinción entre elegir y sintetizar merece quedarse como categoría estable, porque separa dos mundos con propiedades muy distintas. Un algoritmo que elige tiene su imagen contenida en el conjunto de los estados que alguna réplica produjo, y por tanto todo lo que devuelve es, en el peor de los casos, el trabajo de alguien. Un algoritmo que sintetiza tiene una imagen más grande que la unión de lo que las réplicas produjeron, y en ese excedente viven todos los estados que nadie quiso. Preguntar por cada fusión de tu sistema si elige o sintetiza es una de las pocas comprobaciones que se contestan rápido y que reordenan el mapa de riesgos entero.

Y hay una consecuencia práctica que suele descubrirse tarde: como el estado sintetizado es un estado válido del modelo de datos, se propaga sin fricción. Se guarda, se replica, se indexa, se exporta y se convierte en la base sobre la que se aplican las ediciones siguientes. Cuando alguien lo detecta, la corrupción ya está integrada en la historia causal del documento y deshacerla no es revertir una operación sino reescribir un pasado que todas las réplicas consideran legítimo.

Vale la pena ordenar los tres grados de daño que un sistema replicado puede infligir, porque la distinción vuelve a aparecer en cada tipo de dato del resto del track:

grado 1  se conserva un valor y se descarta otro
         alguien pierde su aportacion pero lo que queda es real

grado 2  se conservan ambos valores en paralelo
         nadie pierde nada y alguien tiene que decidir despues

grado 3  se sintetiza un valor que nadie escribio
         no hay nada que decidir porque no quedan alternativas

El primer grado es el que todo el mundo teme y del que todo el mundo habla, y es el menos grave de los tres. El segundo es el que los sistemas bien diseñados persiguen. El tercero apenas se menciona en la literatura de conflictos, es el que produce la intercalación, y es el único de los tres en el que la información original resulta irrecuperable incluso teniendo la traza completa delante.