Por qué una lista es el caso difícil: la posición es un dato

Los cuatro niveles anteriores han construido estructuras que convergen con una facilidad casi sospechosa: contadores que se suman, conjuntos que se unen, registros que comparan vectores, mapas que componen lo anterior clave a clave. Todas comparten un rasgo que no ha hecho falta nombrar hasta ahora: en ninguna de ellas el estado incluye la palabra dónde. Un elemento pertenece o no pertenece a un conjunto, y ahí se acaba la pregunta. La lista rompe esa comodidad de golpe, porque en una lista un elemento no solo está: está en un sitio, y ese sitio es tan parte del estado como el propio contenido. Esta lección explica por qué esa única palabra convierte el problema en otro problema, y por qué las secuencias han consumido más literatura de investigación que todas las estructuras anteriores juntas.

Un conjunto no tiene sitios; una lista sí

Recuerda por qué funcionaba el conjunto observado con lápidas. El estado era un par de conjuntos de identificadores, la fusión era la unión de ambos, y la unión es conmutativa, asociativa e idempotente sin que nadie tenga que hacer nada. Esa gratuidad no venía de la inteligencia del diseño sino de una propiedad del dominio: los elementos de un conjunto no guardan relación entre sí. Añadir manzana no dice nada sobre pera, y por eso dos réplicas que añaden cosas distintas no pueden discrepar: no hay ninguna afirmación conjunta sobre la que discrepar.

Una lista introduce exactamente esa afirmación conjunta. Decir que la lista es [a, b, c] no es decir tres cosas independientes; es decir además que a va antes que b y que b va antes que c. Esas relaciones binarias son estado, ocupan sitio y pueden entrar en contradicción: una réplica puede sostener que x va antes que y mientras la otra sostiene lo contrario, y la unión de ambas afirmaciones no es una lista sino un ciclo. La unión, que era la operación milagrosa del nivel anterior, deja de estar cerrada sobre el tipo.

flowchart TD
S[conjunto de elementos] --> SU[union de los dos conjuntos]
SU --> SOK[siempre es un conjunto valido]
L[lista con relaciones de orden] --> LU[union de las relaciones]
LU --> LNO[puede ser un ciclo y no una lista]
style SOK fill:#a6e3a1,color:#11111b
style LNO fill:#f38ba8,color:#11111b

Conviene medir el salto en términos de cuánta información hay que acordar. En un conjunto de n elementos, cada réplica afirma n hechos independientes de pertenencia. En una lista de n elementos hay del orden de n al cuadrado pares ordenados que el estado determina, y todos ellos han de coincidir en todas las réplicas para que las listas sean la misma lista. No es que la lista tenga un poco más de estado: es que tiene una clase de estado que las estructuras anteriores no tenían, y que además está fuertemente acoplado consigo mismo, porque el orden ha de ser transitivo y sin ciclos.

El experimento que lo hace tangible cabe en unas pocas líneas y conviene ejecutarlo antes de seguir leyendo. Toma dos réplicas que parten de la misma lista de dos elementos, deja que cada una inserte un elemento propio en el mismo hueco, y expresa el resultado como el conjunto de pares ordenados que cada una afirma. La unión de ambos conjuntos contiene afirmaciones que no se pueden satisfacer a la vez, y ninguna de las dos réplicas ha hecho nada indebido.

// Cada lista afirma un conjunto de pares ordenados; la union puede ser imposible
const paresDe = (lista) =>
  lista.flatMap((x, i) => lista.slice(i + 1).map((y) => `${x} antes de ${y}`));

paresDe(["a", "X", "b"]); // a antes de X, a antes de b, X antes de b
paresDe(["a", "Y", "b"]); // a antes de Y, a antes de b, Y antes de b

// La union no dice nada sobre X frente a Y: el orden queda sin determinar
// Y si cada replica lo completa a su manera, las dos listas son distintas

Ese vacío es el problema en su forma más desnuda. La unión de los dos estados no es contradictoria todavía, pero es incompleta: hay un par de elementos sobre el que nadie ha dicho nada y sobre el que hay que decir algo para poder mostrar una lista. Si cada réplica lo completa por su cuenta con un criterio distinto, divergen. Y si acuerdan un criterio, ese acuerdo tiene que salir de los propios datos, porque no hay nadie a quien preguntar.

Qué le pedimos a una lista replicada, además de converger

Convergencia sola es un listón bajísimo y conviene decirlo sin rodeos: una implementación que vacíe la lista en cuanto detecte cualquier concurrencia converge perfectamente, porque todas las réplicas acaban en el mismo estado vacío. Que ese estado sea inservible no lo detecta ninguna prueba de convergencia. Por eso el problema de las secuencias se especifica con una lista de propiedades que hay que enunciar antes de discutir cualquier algoritmo.

Conviene notar que estas cuatro propiedades no son independientes entre sí ni igual de fáciles de comprobar. La convergencia se puede verificar mecánicamente con pruebas generadas, y por eso es la única que casi todas las implementaciones garantizan de verdad. Las otras tres hablan de qué esperaba el usuario, y eso no se deduce del estado: hay que declararlo primero como especificación y después comprobarlo contra ella. Esa asimetría explica por qué el campo tardó décadas en formular la cuarta, y por qué conviene desconfiar de cualquier biblioteca que presuma solo de converger.

Las dos primeras propiedades son las clásicas y se citan siempre juntas. La tercera se da por supuesta hasta que un algoritmo la incumple y el cursor del usuario salta de párrafo mientras escribe. La cuarta es la más joven de las cuatro: quedó formulada con precisión en 2019 y destapó que casi todos los algoritmos publicados hasta entonces fallaban en casos concretos que nadie había mirado. La discutiremos en su propio nivel, pero conviene tenerla presente desde ahora, porque explica por qué un algoritmo de secuencias no se declara correcto solo con demostrar que converge.

Hay además dos requisitos de coste que no son teóricos pero deciden qué se puede usar en producción. El primero es que la inserción y el borrado no pueden costar proporcionalmente al tamaño del documento, porque un texto largo recibe una operación por pulsación de tecla. El segundo es que los metadatos que la estructura arrastra tienen que ser proporcionados al contenido: guardar cien bytes de contabilidad por cada carácter es matemáticamente correcto y prácticamente inaceptable.

Los tres intentos ingenuos y dónde revientan

El primer intento es tratar la lista como un valor cualquiera y aplicarle un registro de último escritor. Converge, es trivial de implementar y destruye el trabajo entero de una de las dos réplicas en cada fusión: quien escribió con la marca menor pierde su inserción completa. Es el equivalente para listas de lo que ya descartamos para valores sueltos, y falla por la misma razón, agravada porque en una lista el estado en juego suele ser todo el documento.

El segundo intento es más sofisticado y se ve en muchísimas bases de datos: dar a cada elemento un campo numérico de orden y ordenar por él. El problema aparece al reordenar, porque mover un elemento obliga a reescribir el campo de otros, y esas reescrituras son asignaciones absolutas concurrentes que colisionan entre sí. Dos réplicas que reordenan a la vez producen numeraciones incompatibles, y la fusión campo a campo genera empates, huecos o directamente órdenes que ninguna de las dos quería.

// Clave de orden numerica: dos reordenaciones concurrentes se destrozan
const inicial = [
  { id: "a", orden: 1 },
  { id: "b", orden: 2 },
  { id: "c", orden: 3 },
];

// La replica 1 sube c al principio y reescribe los tres campos
const r1 = [{ id: "c", orden: 1 }, { id: "a", orden: 2 }, { id: "b", orden: 3 }];
// La replica 2 sube b al principio y reescribe los tres campos
const r2 = [{ id: "b", orden: 1 }, { id: "c", orden: 2 }, { id: "a", orden: 3 }];

// Fusion por ultimo escritor campo a campo: ordenes 1, 1 y 2, con empate
// El resultado no es ninguna de las dos reordenaciones que alguien pidio

El tercer intento consiste en ordenar por marca de tiempo de creación, y es el que más lejos llega antes de fallar, porque en un registro que solo crece por el final funciona de maravilla. Se rompe en cuanto alguien inserta en medio, que es la operación que define una lista frente a un registro cronológico: no existe ninguna marca de tiempo que exprese quiero ir entre estos dos elementos que ya existen, porque el tiempo de creación es una propiedad del acto de escribir y no del sitio elegido.

Merece la pena detenerse en este tercer intento porque delimita con precisión la frontera del problema. Si tu lista solo crece por un extremo, no tienes un problema de secuencias: tienes un conjunto con una clave de ordenación derivada del contenido, y el nivel de los conjuntos ya te lo resolvió. Un registro de eventos, una bitácora, un hilo de mensajes que solo se anexan por el final son exactamente ese caso, y aplicarles la maquinaria de las cinco lecciones siguientes es sobreingeniería pura. La dificultad nace únicamente de la inserción en medio, y su presencia o ausencia en tu producto es la primera pregunta que hay que hacerse.

La posición hay que representarla, no deducirla

Los tres fracasos anteriores comparten una raíz y merece la pena nombrarla, porque es la bisagra de todo el nivel. En los tres casos la posición no está representada: se deduce del recorrido de un array, de la comparación de un número reutilizable o del instante de creación. Y lo que no está representado no se puede fusionar, porque la fusión solo sabe operar sobre lo que el estado contiene explícitamente.

De ahí sale la reformulación que abre el camino y que las cuatro lecciones siguientes desarrollan. Si el problema es que la posición no es un dato, hagámosla un dato: que cada elemento lleve consigo un identificador que diga dónde está, asignado en el momento de la inserción y jamás modificado después. La lista deja entonces de ser una estructura ordenada y pasa a ser un conjunto de pares, que es precisamente la estructura que ya sabemos fusionar, con el orden recuperado al leer mediante una comparación de identificadores.

// La lista como conjunto de pares: fusionar vuelve a ser unir
const replicaA = new Map([["0.25", "hola"], ["0.75", "mundo"]]);
const replicaB = new Map([["0.25", "hola"], ["0.50", "cruel"]]);

const fusion = new Map([...replicaA, ...replicaB]); // union, sin decidir nada
const texto = [...fusion.entries()]
  .sort((x, y) => (x[0] < y[0] ? -1 : 1))
  .map(([, valor]) => valor); // ["hola", "cruel", "mundo"]

Ese fragmento tiene una trampa deliberada que la lección cuarta desmontará: usa cadenas decimales como si fueran números reales, y los identificadores de una implementación seria no pueden serlo. Pero la forma del argumento ya está completa y es la que conviene retener: unión para fusionar, comparación para leer, e inmutabilidad del identificador como condición que hace válidas a las dos anteriores.

Observa también qué le ha pasado a la dificultad, porque no ha desaparecido sino que se ha mudado. La fusión, que era el punto donde todo se rompía, ha quedado reducida a una unión de mapas que cualquiera escribe sin pensar. La lectura es una ordenación corriente. Lo único que queda difícil es de dónde salen esos identificadores, y esa concentración es la mejor noticia posible: un problema repartido por toda la estructura se ha convertido en un problema localizado en una función que recibe dos identificadores y devuelve uno intermedio. Las lecciones restantes del nivel se dedican íntegramente a esa función.