Qué algoritmos lo sufren y en qué grado

Decir que la intercalación afecta a los algoritmos de edición colaborativa es cierto y a la vez demasiado grueso para ser útil, porque no todos la sufren igual ni por los mismos motivos. Hay familias en las que el entrelazado es el comportamiento por defecto y aparece cada vez que dos personas escriben en el mismo hueco; hay otras en las que el caso corriente está protegido por una propiedad estructural del propio modelo y el fallo solo asoma cuando el patrón de edición se aparta de lo que esa estructura suponía. La diferencia importa mucho a la hora de elegir una biblioteca, y explica también por qué el problema tardó tanto en cristalizar: en la mitad de los sistemas era una rareza intermitente y no un defecto reproducible. Esta lección ordena el mapa por mecanismo y termina donde debe terminar, que es en la pregunta de por qué ninguna de nuestras pruebas automáticas lo vio venir.

Identificadores densos: entrelazar es el comportamiento normal

Antes de entrar en el detalle conviene fijar el criterio con el que se va a clasificar, porque no es la eficiencia ni la elegancia sino algo bastante más concreto: cuántas veces, al fusionar dos aportaciones concurrentes, el algoritmo toma una decisión de orden que puede romper la contigüidad de una de ellas. Cero decisiones significa que la contigüidad está garantizada por construcción; una decisión significa que solo se decide dónde va cada aportación entera; tantas decisiones como caracteres significa que la contigüidad depende de que todas ellas salgan alineadas, cosa que no ocurre.

Es la familia del ejemplo de la primera lección y la más gravemente afectada de todas. Su idea de partida es elegante: si a cada carácter se le asigna un identificador de un dominio densamente ordenado, entonces entre dos identificadores cualesquiera siempre cabe otro, el documento es un conjunto ordenado por esa clave y no hace falta ninguna estructura de árbol ni ninguna referencia entre elementos. Insertar es fabricar una clave en el hueco correcto.

El problema nace de la palabra fabricar. La clave del carácter nuevo debe caer estrictamente entre la de su vecino izquierdo y la de su vecino derecho, y hay infinitos valores que cumplen esa condición. Tomar siempre el punto medio haría que las claves creciesen en longitud con cada inserción en el mismo sitio, lo que en un documento real es inaceptable, así que las implementaciones eligen un valor con un componente arbitrario dentro del hueco disponible. Esa elección se hace localmente, sin conocer las claves que otra réplica está generando en ese mismo instante en ese mismo hueco.

De ahí se sigue el resultado con la fuerza de un teorema elemental. Dos réplicas concurrentes generan dos series de claves en el mismo intervalo, de forma independiente y sin coordinación posible; ordenar la unión de dos series independientes de valores del mismo rango produce, salvo por una casualidad estadísticamente irrelevante, una alternancia entre ambas. La intercalación no es aquí un caso límite del algoritmo: es su comportamiento esperado, y lo raro sería obtener las dos palabras enteras y seguidas.

Y no hay dentro del modelo ninguna palanca que permita evitarlo sin renunciar a otra cosa. Si las claves se generasen de forma no arbitraria, por ejemplo tomando siempre el punto medio, dejarían de entrelazarse tan a menudo pero crecerían en longitud con cada inserción sucesiva en el mismo lugar, que es justo el problema que la arbitrariedad venía a resolver. Si se coordinara la generación entre réplicas, se recuperaría la necesidad de comunicación que toda la arquitectura existe para eliminar. La familia está atrapada entre dos costes propios y elige el que no se ve.

Conviene subrayar la consecuencia de gravedad, porque es la que decide en una comparativa. En esta familia, la degradación es proporcional a la longitud de las aportaciones concurrentes. Dos palabras cortas dan un resultado ilegible; dos párrafos escritos a la vez en el mismo punto dan un resultado del que no se recupera ni una oración completa. No hay ningún mecanismo interno que limite el daño, porque no hay ninguna entidad en el modelo que represente el hecho de que esos caracteres iban juntos.

Referencia al predecesor: la secuencia aguanta, casi siempre

La otra gran familia parte de una idea distinta y bastante más afortunada para este asunto. En lugar de fabricar una clave absoluta, cada carácter guarda una referencia al elemento tras el cual se insertó. El documento deja de ser un conjunto ordenado por clave y pasa a ser un árbol de dependencias que se recorre para producir el texto: se emite un elemento, después todo lo que cuelga de él, después el siguiente hermano, y así sucesivamente, con un criterio determinista para ordenar los hermanos que compiten por el mismo anclaje.

Observa lo que ocurre con una palabra tecleada de izquierda a derecha, que es como teclea casi todo el mundo casi todo el tiempo. La primera letra se ancla al carácter que había antes; la segunda se ancla a la primera; la tercera a la segunda. La palabra entera forma una cadena, y una cadena es un solo subárbol. Cuando dos personas escriben concurrentemente en el mismo punto, el recorrido encuentra dos subárboles compitiendo por el mismo anclaje, resuelve el empate una única vez y a continuación emite un subárbol completo antes de pasar al otro. Las dos palabras salen enteras y seguidas.

La expresión clave del párrafo anterior es una única vez. Ahí está toda la diferencia con la familia anterior, y se puede resumir contando decisiones: en el esquema de identificadores densos se toman once decisiones de orden para once caracteres, y cada una puede ir en contra de la contigüidad; en el esquema de anclajes con la palabra formando cadena se toma una sola decisión, la del empate entre las dos cabezas, y el resto del orden se deduce de la estructura. Reducir el número de puntos donde se puede fallar de once a uno no es una mejora incremental: es un cambio de régimen.

anclaje  <- l <- u <- n <- e <- s          cadena de Ana
anclaje  <- m <- a <- r <- t <- e <- s     cadena de Beto

recorrido        Nota: marteslunes

Es un resultado muy superior al de la familia anterior y explica por qué esta rama del diseño acabó imponiéndose. Pero fíjate en de dónde viene exactamente la protección, porque no viene de ninguna regla que hable de palabras: viene de un accidente afortunado del patrón de escritura. Nada en el algoritmo dice que las letras de una palabra deban permanecer juntas. Lo que las mantiene juntas es que, al teclear hacia delante, cada letra queda anclada a la anterior y por tanto forma un subárbol. La propiedad deseable se obtiene como efecto colateral de una coincidencia entre el modelo de anclaje y una costumbre humana.

Y las costumbres humanas tienen excepciones. Cuando el patrón de edición no genera esa cadena, la protección desaparece por completo. El caso más claro es escribir hacia atrás: si alguien coloca el cursor y va insertando cada carácter antes del anterior, todas las letras acaban ancladas al mismo elemento de la izquierda en vez de encadenarse entre sí. Ya no hay un subárbol sino un puñado de hermanos que compiten por el mismo anclaje, y un puñado de hermanos concurrentes de dos réplicas distintas se ordena por el criterio de desempate elemento a elemento, que es exactamente la situación de la familia anterior. Lo mismo ocurre con otras maniobras que rompen la cadena, como volver sobre un hueco ya compartido o intercalar una edición en mitad de una secuencia propia.

flowchart TB
F1[identificadores densos] --> M1[cada caracter recibe una clave sorteada en el hueco]
M1 --> R1[entrelazado sistematico proporcional a la longitud]
F2[referencia al predecesor] --> M2[cada caracter se ancla al anterior de su propia secuencia]
M2 --> B[al teclear hacia delante la secuencia forma un subarbol]
B --> R2[las secuencias salen enteras en el caso corriente]
M2 --> D[si el patron rompe la cadena quedan hermanos sueltos]
D --> R3[entrelazado en ese patron concreto]
style R1 fill:#f38ba8,color:#11111b
style R2 fill:#a6e3a1,color:#11111b
style R3 fill:#fab387,color:#11111b

La conclusión que hay que llevarse de la comparación no es que una familia sea buena y otra mala, sino algo más incómodo: en la mejor de las dos, la ausencia de intercalación en el caso corriente es una consecuencia no buscada del diseño y no una garantía enunciada. Ningún artículo de la época afirmaba tenerla, ninguna implementación la probaba y por tanto nadie estaba obligado a conservarla al optimizar. Una propiedad que se tiene por casualidad se pierde por casualidad en la siguiente refactorización.

Merece la pena dejar el mapa en tres categorías, porque es lo que de verdad sirve al evaluar una biblioteca:

sistematico     identificadores densos
                entrelaza siempre que hay concurrencia en el mismo hueco
                el dano crece con la longitud de las aportaciones

condicional     referencia al predecesor
                el caso corriente de teclear hacia delante queda protegido
                el fallo aparece cuando el patron rompe la cadena de anclajes

especificado    algoritmos posteriores al enunciado del problema
                la ausencia de intercalacion figura como propiedad y se comprueba

La tercera categoría estaba vacía hasta que alguien escribió el enunciado, y esa es toda la diferencia entre las dos primeras y ella. No se trata de que los algoritmos de la tercera sean más ingeniosos, sino de que su corrección incluye una cláusula que las otras dos no tenían y que por tanto no podían ni cumplir ni incumplir.

Hay además un matiz sobre la segunda categoría que conviene no perder de vista al evaluar riesgos reales. Los patrones que rompen la cadena de anclajes no son maniobras de laboratorio: escribir hacia atrás ocurre cada vez que alguien corrige una palabra insertando letras delante del cursor, y volver sobre un hueco ya compartido ocurre cada vez que dos personas retoman la edición del mismo párrafo tras una sincronización. Que el fallo sea condicional no significa que sea improbable: significa que su frecuencia depende de hábitos de edición que varían por persona, por herramienta y por tipo de documento, lo cual es precisamente la peor propiedad que puede tener un fallo, porque hace que unos equipos lo vean a diario y otros nunca, y que ninguno de los dos crea al otro.

Por qué las pruebas no lo ven

Queda la parte que más duele para quien escribe software: este fallo atraviesa limpiamente las baterías de pruebas de un proyecto bien mantenido, y no por descuido sino por razones estructurales. Merece la pena enumerarlas, porque cada una es reutilizable en otros dominios.

La primera es la decisiva y conviene formularla como principio general: una prueba cuyo oráculo es otra réplica del mismo sistema solo puede detectar desacuerdos internos. Es una comprobación de coherencia, no de corrección, y confundir ambas cosas es lo que permite que un sistema apruebe miles de casos generados y produzca basura en el primer uso real. Para detectar corrupción hace falta un oráculo externo al sistema: una expectativa formulada en términos de lo que las personas hicieron, no en términos de lo que las réplicas contienen.

Aplica ese criterio a tu propia batería y verás que la proporción de pruebas circulares es más alta de lo que esperabas. Comprobar que serializar y deserializar devuelve el original, que dos rutas de cálculo dan el mismo número, que el estado tras un reinicio coincide con el previo: todas son valiosas y todas son internas. Ninguna de ellas puede detectar que el sistema entero esté haciendo consistentemente lo incorrecto, porque su punto de referencia es el propio sistema. Una batería sana necesita ambas clases, y la segunda es siempre la minoritaria porque es la única que obliga a escribir una expectativa.

Hay además un agravante propio de esta anomalía. Las pruebas basadas en propiedades, que son la herramienta ideal para explorar espacios de estados grandes, se configuran típicamente para minimizar el contraejemplo cuando encuentran un fallo. Como aquí no encuentran ninguno —la convergencia se cumple siempre— jamás llegan a esa fase, y el enorme espacio que exploran queda íntegramente desperdiciado sobre la propiedad equivocada. La potencia de la herramienta no sirve de nada si el predicado que se le da es el que no falla nunca.

Y hay un último obstáculo que es de método y no de herramienta. Aunque alguien imprimiera todos los resultados de esas pruebas, no habría manera automática de reconocer cuál es malo, porque la maldad de mlaurnteess no es una propiedad sintáctica evidente sino un juicio sobre legibilidad. La única forma de detectarlo sin un enunciado previo es que una persona mire la salida y se dé cuenta, y las personas no miran salidas de pruebas que pasan. El fallo estaba, literalmente, pasando por delante de los ojos de nadie durante veinte años de ejecuciones verdes.

La aserción que sí lo ve

La buena noticia es que, una vez enunciado el problema, la prueba que lo detecta es casi trivial de escribir. El predicado que hay que comprobar no habla de réplicas: habla del contenido. Dadas dos aportaciones concurrentes s1 y s2 sobre un mismo estado base, el texto fusionado debe contener tanto s1 como s2 como subcadenas contiguas. Nada más. No se exige un orden concreto entre ellas, porque elegir cuál va primero es una decisión legítima del algoritmo y ambas opciones son aceptables para una persona; se exige únicamente que ninguna de las dos aparezca troceada.

Con ese predicado, los tres desenlaces del nivel se separan solos y el informe deja de ser ambiguo:

resultado           contiene lunes   contiene martes   veredicto
Nota: lunesmartes        si               si            aceptable
Nota: marteslunes        si               si            aceptable
Nota: mlaurnteess        no               no            intercalacion

Fíjate en la economía del asunto. La aserción es una comprobación de subcadena, cuesta dos líneas y se ejecuta en microsegundos; la dificultad nunca estuvo en la técnica de prueba sino en saber qué había que afirmar. Durante veinte años, la comunidad tuvo generadores sofisticados, minimizadores de contraejemplos y demostradores asistidos por máquina, y no tuvo esta línea. Es la ilustración más limpia posible de que el cuello de botella de la verificación no es la potencia de las herramientas sino la calidad de los enunciados que les damos.

Para que la aserción sirva de algo hay que alimentarla con los casos correctos, y ahí sí hace falta un poco de cuidado. Un generador útil para este problema no sortea posiciones libremente: fabrica aportaciones, es decir, tuplas formadas por un estado base, un punto de anclaje compartido y dos secuencias de longitud al menos dos. Esa restricción, que parece una trampa para forzar el fallo, es en realidad lo contrario: es lo que hace que el espacio explorado se corresponda con el uso real del sistema, donde las personas escriben palabras en los mismos sitios y no caracteres sueltos en posiciones aleatorias.

Conviene añadir la variante que separa las dos familias del principio de la lección. Además de generar las dos aportaciones hacia delante, hay que generarlas también hacia atrás, insertando cada carácter delante del anterior. Con esas dos variantes y la aserción de contigüidad, una batería de pruebas de treinta líneas distingue los tres comportamientos posibles y deja constancia escrita de cuál tiene la biblioteca que estés usando. Es, con diferencia, la mejor relación entre esfuerzo invertido e información obtenida de todo este nivel.