Qué significa maximal: hasta dónde se puede no intercalar
Maximal no quiere decir que nunca se intercale, sino que solo se intercala cuando la propia consistencia lo obliga, y un teorema de unicidad demuestra que ese límite no admite mejora.
La palabra que da nombre a la propiedad es la que más se malinterpreta. Maximal no significa mucho, ni significa suficiente, ni es una forma prudente de decir casi siempre. Significa algo mucho más fuerte y mucho más incómodo: que existe una frontera demostrable más allá de la cual no intercalar es lógicamente imposible, que la propiedad la alcanza exactamente y que ninguna definición más exigente puede satisfacerse. Para llegar ahí hay que hacer tres cosas seguidas. Primero, separar el problema en dos mitades —la escritura hacia delante y la escritura hacia atrás— porque son propiedades distintas y los algoritmos las incumplen por separado. Segundo, exhibir una ejecución concreta, de solo cuatro inserciones, en la que garantizar la primera mitad obliga a romper la segunda: no por limitación del algoritmo, sino por la interacción entre ambas y la exigencia de convergencia. Y tercero, escribir una definición que conceda esa excepción con precisión quirúrgica en lugar de renunciar a la mitad entera. El resultado es una propiedad que no solo se puede cumplir, sino que además fija el orden de la lista sin ninguna libertad restante.
- Definir origen izquierdo y origen derecho, y entender por qué son la unidad de análisis correcta.
- Enunciar la no intercalación hacia delante y ver qué implica sobre ráfagas completas de texto.
- Reconstruir la ejecución mínima en la que las dos direcciones son incompatibles entre sí.
- Leer la definición de no intercalación maximal y su teorema de unicidad como el enunciado de un límite.
Dos direcciones de escritura, dos propiedades distintas
Todo el análisis descansa sobre dos conceptos elementales que conviene fijar antes de nada. El origen izquierdo de un elemento es el elemento que estaba inmediatamente antes de su posición en el momento de insertarlo; si se insertó al principio de la lista, su origen izquierdo es un símbolo especial de inicio. El origen derecho es el simétrico: el elemento que estaba inmediatamente después en ese mismo instante, o un símbolo de fin. Un detalle técnico que parece menor y no lo es: el origen derecho se toma sobre la lista incluyendo las lápidas, es decir contando también los elementos ya borrados, y esa elección permite razonar sobre la intercalación ignorando por completo las eliminaciones.
Con esos dos conceptos se define el árbol de orígenes izquierdos, en el que el padre de cada elemento es su origen izquierdo, y que está enraizado en el símbolo de inicio; y su gemelo, el árbol de orígenes derechos, enraizado en el símbolo de fin. No son estructuras de datos del algoritmo: son objetos de análisis que existen en cualquier ejecución de cualquier algoritmo de listas replicadas, porque toda inserción ocurrió entre dos elementos concretos y esa relación queda registrada en la historia con independencia de cómo la almacene nadie. Este desdoblamiento es lo que permite hablar de las dos direcciones por separado.
La primera dirección es la habitual. Cuando alguien escribe pan, inserta p, luego a con origen izquierdo p, luego n con origen izquierdo a. La ráfaga forma una cadena descendente en el árbol de orígenes izquierdos, y la propiedad que se desea es que esa cadena salga entera y contigua. Formalmente, un algoritmo es no intercalante hacia delante si satisface la especificación fuerte de listas y, para cualesquiera elementos A y B, se cumple lo siguiente: si A es el origen izquierdo de B, y B aparece en la lista antes que cualquier otro elemento cuyo origen izquierdo sea A, entonces A y B son consecutivos.
El enunciado habla de dos elementos y de consecutividad, no de ráfagas ni de bloques, y a primera vista parece demasiado débil. El artículo demuestra en su lema 3 que no lo es: si un algoritmo cumple esa condición local, entonces también cumple la formulación global de 2019 restringida al caso hacia delante, es decir que si dos secuencias se insertan de izquierda a derecha concurrentemente en la misma posición de partida, todos los elementos de una quedan al mismo lado de todos los elementos de la otra. La demostración es un argumento de estado alcanzable: siempre es posible que alguna réplica se encuentre en un estado con el primer elemento de una secuencia y el segundo de la otra y nada más, y en ese estado la condición local fuerza el orden que después la especificación fuerte propaga al resultado final.
La segunda dirección es menos frecuente pero no marginal. Nadie teclea pan al revés, pero mucha gente antepone entradas al principio de una lista: una tarea nueva arriba del todo, una fila nueva en la cabecera de una hoja de cálculo, un artículo nuevo antes de los anteriores. El escenario del artículo es exactamente ese: dos personas sin conexión añaden productos al principio de una lista de la compra y luego rematan cada una con un encabezado de categoría, de modo que la fusión mal hecha acaba listando pan bajo la categoría fruta. La intercalación resultante es más gruesa que la de carácter a carácter, y por eso resulta menos escandalosa, pero sigue produciendo un documento que nadie escribió.
La ejecución donde las dos no caben
Lo natural sería definir la no intercalación hacia atrás como la dual exacta de la anterior —cambiando origen izquierdo por origen derecho— y llamar no intercalación a la conjunción de ambas. El artículo demuestra que esa conjunción es insatisfacible, y lo hace con una ejecución de una brevedad casi ofensiva: cuatro elementos, tres réplicas.
sequenceDiagram participant R1 as Replica 1 participant R2 as Replica 2 participant R3 as Replica 3 Note over R1,R3: lista vacia. las tres insertan a la vez Note over R1: inserta A Note over R2: inserta B Note over R3: inserta C R1->>R3: A R2->>R3: B Note over R3: recibe los tres y fija el orden A luego B luego C R3->>R1: C Note over R1: tiene A y C. inserta X en medio y obtiene A X C R2->>R1: recibe B Note over R1: debe colocar B sin romper el orden que fijo R3
El razonamiento que encierra a la réplica 1 tiene solo dos pasos y ninguno es evitable.
Hechos de la ejecucion:
X es el unico elemento cuyo origen izquierdo es A
X es el unico elemento cuyo origen derecho es C
la replica 3 llego al estado A B C antes de saber nada de X
Paso 1 la no intercalacion hacia delante exige que A y X
sean consecutivos, luego la lista contiene A X
Paso 2 la especificacion fuerte exige que el orden A B C
que fijo la replica 3 se respete en todas partes
Unico orden compatible con ambos: A X B C
Pero entonces X y C no son consecutivos, y X era el unico
elemento con origen derecho C. La dual exacta de la
no intercalacion hacia delante queda violada, y no habia
ninguna otra opcion disponible.La lección que hay que extraer es precisa: no es que sea difícil cumplir ambas mitades, es que son incompatibles. Cualquier algoritmo que satisfaga la especificación fuerte de listas y la no intercalación hacia delante violará la versión dual en esta ejecución. Un investigador con prisa concluiría que hay que quedarse con una de las dos, y probablemente elegiría la de delante por ser la que cubre el caso común. Ese es exactamente el punto donde el artículo hace lo que lo distingue: en lugar de renunciar a la mitad entera, delimita con exactitud las circunstancias en que la renuncia es forzosa y exige el cumplimiento en todas las demás.
La definición que sí se puede satisfacer
La no intercalación maximal se enuncia como tres condiciones sobre cualquier par de elementos A y B, en cualquier estado posible de la lista, además de la especificación fuerte de listas.
1 Hacia delante, sin excepciones
si A es el origen izquierdo de B, y B aparece en la lista
antes que cualquier otro elemento con origen izquierdo A,
entonces A y B son consecutivos.
2 Hacia atras, salvo cuando la condicion 1 lo impide
si B es el origen derecho de A, y A aparece en la lista
despues que cualquier otro elemento con origen derecho B,
entonces A y B son consecutivos, salvo en el caso excepcional
descrito abajo.
3 Desempate arbitrario
si A y B tienen el mismo origen izquierdo y el mismo origen
derecho, aparece antes el de identificador menor.
El caso excepcional de la condicion 2 se da cuando ambas cosas
son ciertas a la vez:
i A y B tienen origenes izquierdos distintos
ii existe un elemento C en el estado actual situado entre
el origen izquierdo de A y B, y C no es descendiente del
origen izquierdo de A en el arbol de origenes izquierdos.
En ese caso queda demostrado que C tiene que quedar entre A y B,
de modo que A y B no pueden ser consecutivos y la exigencia
de la condicion 2 se levanta.Tres observaciones sobre la forma de esta definición, porque cada una enseña algo distinto. La primera: la prioridad se le da a la dirección hacia delante, y el motivo que da el artículo es empírico y no matemático —escribir de izquierda a derecha es abrumadoramente más frecuente en un editor de texto que anteponer—. Cuando dos exigencias formales chocan, alguien tiene que decidir cuál cede, y esa decisión se toma mirando el dominio, no la teoría. La segunda: la excepción no está redactada como salvo cuando resulte imposible, que sería una tautología inútil, sino como una condición verificable sobre elementos concretos y sobre la posición relativa de un tercer elemento en el árbol de orígenes izquierdos. La tercera: la condición 3 es abiertamente arbitraria y el artículo lo admite, porque dos elementos insertados concurrentemente en exactamente el mismo hueco, con los mismos dos vecinos, no tienen ninguna razón intrínseca para ordenarse de una manera u otra.
Es tentador leer la condición 2 como una concesión y despacharla rápido. Es justo al revés: la excepción es la parte técnicamente más delicada de la definición y lo que la hace valiosa. Una excepción demasiado ancha vacía la propiedad, porque un algoritmo malo puede acogerse a ella siempre. Una excepción demasiado estrecha vuelve la propiedad insatisfacible otra vez. Acertar el ancho exacto exige haber demostrado antes qué se puede y qué no se puede evitar, y ese es el trabajo que separa una definición publicable de una intuición bien escrita.
El límite teórico: la propiedad fija el orden entero
Queda por responder la pregunta que da título a la lección: dónde está exactamente el límite y cómo se sabe que la definición lo alcanza. La respuesta es un teorema de unicidad, y es el resultado más fuerte del artículo. Dice que si un algoritmo de listas replicadas es maximalmente no intercalante, entonces es semánticamente equivalente a FugueMax: en cualquier ejecución produce el mismo orden total sobre los elementos. No parecido, no compatible: el mismo.
Cero libertad restante
Las condiciones 1 y 2 obligan a un recorrido concreto del árbol de orígenes izquierdos y del bosque de orígenes derechos. No queda nada que un diseñador pueda elegir.
Salvo el desempate
La única libertad que sobrevive es la condición 3, el orden entre dos elementos con ambos orígenes idénticos, y es arbitraria por construcción.
Ninguna exigencia adicional cabe
Cualquier condición extra no trivial ordenaría de otro modo a algún par, y ya está demostrado que ese otro modo viola alguna de las tres condiciones.
Un criterio para juzgar el futuro
La propiedad se convierte en un banco de pruebas: para saber si un algoritmo nuevo es maximalmente no intercalante basta con comparar su orden con el de FugueMax.
El teorema también ofrece una caracterización alternativa del orden que resulta muy útil para implementar y para verificar sin construir el árbol doble: primero se ordenan los elementos por un recorrido en profundidad y en preorden del árbol de orígenes izquierdos; después, los hermanos de ese árbol se ordenan por un recorrido en profundidad y en postorden de su bosque de orígenes derechos; a continuación, las raíces de ese bosque con orígenes derechos distintos se ordenan por el orden inverso de sus orígenes derechos; y por último, las raíces con el mismo origen derecho y el resto de hermanos se ordenan por identificador. El artículo señala expresamente que se podría construir un algoritmo directamente sobre esta caracterización, y que la presentación como árbol de dos lados se eligió por simplicidad, no por necesidad.
Hay un salto cualitativo escondido en el teorema de unicidad que conviene ver con nitidez, porque cambia el estatuto de todo lo que viene después. Mientras una propiedad de corrección admite varios objetos que la cumplen, el trabajo de quien construye sistemas es de diseño: hay un espacio de soluciones, hay compromisos entre rendimiento y simplicidad, hay gusto, y dos equipos competentes pueden elegir distinto y ambos tener razón. En el momento en que se demuestra que la propiedad determina el objeto de manera única, ese espacio colapsa a un punto y el trabajo pasa a ser de descubrimiento: ya no se elige el comportamiento, solo se elige cómo representarlo. Es la misma transición que ocurre en matemáticas cuando una lista de axiomas resulta ser categórica, y tiene tres consecuencias muy concretas para la ingeniería. La primera es que la competencia entre implementaciones deja de ser una competencia sobre semántica y se convierte enteramente en una competencia sobre representación, velocidad y memoria, lo que es una noticia excelente porque esas magnitudes se miden y las discusiones se cierran solas. La segunda es que la interoperabilidad deja de ser un problema de negociación: dos bibliotecas que satisfagan la propiedad producen el mismo documento aunque no se hayan visto nunca, y esa es la clase de garantía sobre la que se puede construir un formato de archivo con la esperanza de que siga abriéndose dentro de veinte años, que es literalmente uno de los ideales del software local-first. Y la tercera, la más contraintuitiva: el teorema de unicidad predice la convergencia independiente de los implementadores. Si dos personas persiguen la misma intuición sin conocerse y las dos aciertan, tienen que llegar al mismo algoritmo, porque solo hay uno. La lección quinta de este nivel documenta que eso fue exactamente lo que pasó —dos implementaciones no académicas llegaron por su cuenta a comportamientos que se conjeturan equivalentes a Fugue y a FugueMax— y a la luz de este teorema esa coincidencia deja de ser una anécdota curiosa para convertirse en una confirmación empírica de que la propiedad captura algo real y no una preferencia estética de sus autores.
- Implementa las funciones que calculan el origen izquierdo y el origen derecho de cada elemento a partir de un registro de operaciones, contando las lápidas en el segundo.
- Reproduce la ejecución de las tres réplicas y verifica que el orden
A X B Ces el único compatible con la condición 1 y con la especificación fuerte. - Escribe la condición 2 sin la excepción y comprueba con un generador aleatorio de ejecuciones con qué frecuencia aparece un contraejemplo.
- Codifica la excepción completa y vuelve a ejecutar el generador: no debería quedar ningún contraejemplo.
- Construye un verificador que, dado el registro de operaciones y el orden final, decida si las tres condiciones se cumplen, y pásaselo a cualquier CRDT de listas que tengas a mano.
- Explica en cinco líneas, sin usar la palabra maximal, qué le estás garantizando a un usuario que antepone tareas desde dos dispositivos sin conexión.