G-Set: el conjunto que solo sabe crecer

Hay una estructura de datos que converge sin relojes, sin identificadores, sin vectores de versión y sin una sola línea de política de resolución, y cuya demostración de corrección cabe en tres igualdades. Es un conjunto al que solo se le pueden añadir elementos, y su función de mezcla es la unión. Suena a ejercicio de primera clase y la tentación es pasar de largo hacia las estructuras interesantes. Sería un error de lectura: el conjunto de solo crecimiento no es un caso degenerado del problema, es el problema entero resuelto por amputación. Todo lo que las cuatro lecciones siguientes van a construir —el borrado que resucita, los dos conjuntos que se condenan mutuamente, las etiquetas que devuelven la posibilidad de volver a añadir, las lápidas que ya nunca se marchan— aparece en el instante exacto en que le retiras a esta estructura la restricción que la hacía trivial. Para entender bien qué se rompe hay que entender antes, con precisión incómoda, qué era lo que funcionaba.

La estructura más simple que converge

El estado de un G-Set es un conjunto y nada más. La interfaz tiene dos operaciones de usuario, añadir y leer, y una operación de sistema, mezclar. Añadir inserta un elemento en el conjunto local. Leer devuelve el conjunto. Mezclar toma dos estados y devuelve su unión. No hay más. No hay marcas de tiempo, no hay identificadores de réplica, no hay resolución de empates porque no existen los empates.

// G-Set: el estado es un conjunto y la mezcla es la union
function crear(iterable = []) {
  return { elementos: new Set(iterable) };
}

function anadir(g, elemento) {
  g.elementos.add(elemento);
  return g;
}

function leer(g) {
  return new Set(g.elementos);
}

function mezclar(a, b) {
  return { elementos: new Set([...a.elementos, ...b.elementos]) };
}

Lo que convierte estas doce líneas en un CRDT no es su brevedad sino el hecho de que mezclar es idempotente, conmutativa y asociativa, las tres propiedades que el nivel 25 identificó como el núcleo de un semirretículo. Conviene ver qué compra cada una por separado, porque cada una neutraliza una patología distinta de la red y la neutraliza por completo, no estadísticamente. La idempotencia hace que recibir dos veces el mismo estado sea indistinguible de recibirlo una vez, de modo que la entrega al menos una vez deja de ser un problema y se puede reintentar cualquier envío sin llevar la cuenta. La conmutatividad hace que el orden de llegada sea irrelevante, y con él desaparece la necesidad de secuenciar mensajes. La asociatividad hace que agrupar las mezclas como convenga —por lotes, por réplica, por sesión— no cambie el resultado, que es lo que permite comprimir la sincronización sin razonar sobre ella.

const iguales = (a, b) =>
  a.elementos.size === b.elementos.size &&
  [...a.elementos].every((e) => b.elementos.has(e));

const x = crear(["a", "b"]);
const y = crear(["b", "c"]);
const z = crear(["c", "d"]);

iguales(mezclar(x, x), x);                                     // idempotente
iguales(mezclar(x, y), mezclar(y, x));                         // conmutativa
iguales(mezclar(mezclar(x, y), z), mezclar(x, mezclar(y, z))); // asociativa

La consecuencia práctica merece enunciarse sin adornos: en un G-Set no existe el concepto de conflicto. No es que los conflictos se resuelvan bien, es que la pregunta del nivel 23 —si el resultado depende de quién habló primero— tiene respuesta negativa por construcción para cualquier par de operaciones. Toda la maquinaria de detección causal que tanto costó montar sigue siendo útil para otras cosas, pero aquí no hace falta para converger.

La unión es el supremo, no una preferencia

Es fácil leer la unión como la mezcla sensata y quedarse ahí. La formulación correcta es más fuerte y más útil: dado el conjunto de todos los subconjuntos posibles ordenado por inclusión, la unión es el supremo, es decir, la menor cota superior de los dos estados. Y el supremo es la única función que puede hacer de mezcla, porque las dos exigencias que le pedimos la determinan sin margen. La primera es que el resultado domine a ambos operandos, ya que perder algo que una réplica sabía sería perder información que nadie autorizó a tirar. La segunda es que sea el menor de los que cumplen lo anterior, ya que cualquier cosa mayor estaría inventando elementos que nadie añadió.

Aquí conviene desmontar un malentendido frecuente, porque revela lo que las tres leyes no dicen. La intersección también es idempotente, conmutativa y asociativa. Si las tres leyes bastaran para elegir la mezcla, la intersección sería igual de válida, y evidentemente no lo es. Lo que la descarta no es el álgebra sino la dirección: con la intersección como mezcla, el orden asociado es la inclusión invertida, y en ese orden la operación de añadir hace descender el estado en lugar de elevarlo. La condición que falta, y que el nivel 25 llamó monotonía, es que toda operación local sea inflacionaria respecto del orden en el que la mezcla es supremo. Las tres leyes garantizan que la mezcla es determinista; la monotonía garantiza que el sistema progresa.

flowchart LR
A[replica A anade alfa y beta] --> U[union de los dos estados]
B[replica B anade beta y gamma] --> U
U --> R[alfa beta gamma en las dos replicas]
R --> L[el orden de llegada no cambia el resultado]
style A fill:#89b4fa,color:#11111b
style B fill:#89b4fa,color:#11111b
style R fill:#a6e3a1,color:#11111b

Ese orden parcial no es un adorno teórico: es computable y sirve para decidir si hace falta enviar algo. Si el estado remoto ya domina al local, no hay nada que mandar, y si el local domina al remoto, se puede mandar sin esperar respuesta. Cuando ninguno domina al otro, ambas réplicas tienen información que la otra ignora, que es exactamente el caso concurrente del nivel 22 reaparecido aquí sin causar ningún daño.

// El orden del semirreticulo: a precede a b si todo lo de a esta en b
function precede(a, b) {
  for (const e of a.elementos) if (!b.elementos.has(e)) return false;
  return true;
}

function relacion(a, b) {
  const ab = precede(a, b);
  const ba = precede(b, a);
  if (ab && ba) return "iguales";
  if (ab) return "b domina: no hay nada que enviar desde a";
  if (ba) return "a domina: enviar a sin esperar respuesta";
  return "concurrentes: cada una tiene algo que la otra no";
}

Dónde un conjunto que solo crece es la respuesta

Vale la pena resistir el impulso de tratar esta estructura como un peldaño pedagógico, porque una cantidad sorprendente de problemas reales encajan en ella tal cual, y encajan justamente en las zonas del sistema donde uno menos quiere depurar concurrencia.

Queda un coste que no es de corrección sino de transporte, y conviene verlo ahora porque reaparecerá agravado en el resto del nivel. Mezclar exige, en la formulación anterior, enviar el estado completo, cuyo tamaño crece de forma monótona con el uso. Sincronizar dos réplicas que difieren en un elemento cuesta lo mismo que sincronizar dos que no se hablan desde hace un año. La salida es la variante por deltas: como la mezcla es idempotente, un delta es simplemente otro estado más pequeño, y reenviarlo, duplicarlo o entregarlo desordenado no rompe nada.

// Delta: un estado pequeno que se mezcla igual que uno grande
function anadirConDelta(g, elemento) {
  const nuevo = !g.elementos.has(elemento);
  g.elementos.add(elemento);
  return nuevo ? { elementos: new Set([elemento]) } : null;
}

const local = crear(["a"]);
const delta = anadirConDelta(local, "b");
const remoto = crear(["a", "z"]);

const tras = mezclar(remoto, delta);         // solo viajo un elemento
iguales(tras, mezclar(remoto, local));       // mismo resultado que el estado entero
iguales(mezclar(tras, delta), tras);         // reenviarlo es inofensivo

El techo del que nace el resto del nivel

Falta nombrar lo que esta estructura no tiene, y no es un olvido de la interfaz: es una imposibilidad. No hay operación de quitar, y añadirla ingenuamente no produce un G-Set con una funcionalidad más, produce una estructura que ya no converge. Basta el trazado más corto posible para verlo, y merece la pena escribirlo entero porque es el germen de las cuatro lecciones restantes.

const A = crear(["x"]);
const B = crear(["x"]);

A.elementos.delete("x");              // A cree que x ya no esta
const fusion = mezclar(A, B);         // B nunca se entero del borrado
fusion.elementos.has("x");            // true: x ha vuelto

precede(B, A);                        // false: A ya no domina lo que sabia

La última línea es el diagnóstico exacto. Borrar hizo que el estado de A dejara de dominar a su propio pasado, y con eso rompió la monotonía de la que colgaba todo lo demás. La mezcla siguió calculando el supremo con absoluta corrección; lo que dejó de ser cierto es que el supremo represente lo que el usuario quería. Y fíjate en que la culpa no es de la unión: cualquier función que cumpla las tres leyes y respete el orden reconstruirá el elemento, porque B lo tiene y perderlo violaría la exigencia de no descartar información que una réplica poseía.