El semirretículo de unión: la forma exacta que debe tener el estado

La lección anterior dejó el problema reducido a una sola pieza: como no puedes coordinar, ni arbitrar, ni retroceder, lo único ajustable es la forma de la función que mezcla dos estados. Aquí construimos esa forma, y el resultado tiene un nombre que asusta más de lo que merece. Un semirretículo de unión es un conjunto de estados ordenados por cuánta información contienen, en el que cualquier par de estados tiene una cota superior mínima: un estado que incluye a los dos y que no incluye nada más. Esa frase, entendida despacio, contiene las cuatro exigencias que la replicación sin árbitro impone a la mezcla, una por cada pieza de la definición. No es que los semirretículos resulten ser convenientes para esto: es que la lista de exigencias, escrita sin pensar en matemáticas, define un semirretículo palabra por palabra.

Un orden parcial es una manera de no obligar a comparar

Empecemos por lo único que hace falta postular: una relación entre estados que se escribe x <= y y que se lee «y sabe al menos todo lo que sabe x». No es una comparación de valores ni de fechas; es una comparación de información. Un carrito con dos artículos es menor o igual que el mismo carrito con esos dos y un tercero, porque el segundo contiene lo que el primero sabía.

Para que esa relación merezca el nombre de orden parcial hace falta que cumpla tres condiciones, y ninguna es caprichosa. Reflexividad: todo estado se compara consigo mismo, x <= x, que dicho en castellano es que un estado sabe lo que sabe. Antisimetría: si x <= y y también y <= x, entonces x e y son el mismo estado; es decir, si dos estados se contienen mutuamente, no había dos estados. Transitividad: si x <= y e y <= z, entonces x <= z; la información se acumula sin sorpresas al encadenar.

Falta una cuarta condición que deliberadamente no exigimos, y su ausencia es el corazón de todo el asunto. Un orden total añade la totalidad: dos elementos cualesquiera son comparables, uno de los dos siempre es menor. Los números con su orden habitual son totales, y por eso comparar marcas de tiempo produce siempre un ganador. Un orden parcial se llama parcial precisamente porque renuncia a eso: hay pares de estados de los que no se puede decir que uno sepa más que el otro, porque cada uno sabe algo que el otro ignora. Ese par se llama incomparable, y es, con otro nombre, la concurrencia causal que definimos hace dos niveles. La estructura que estamos construyendo no es una manera de esquivar la incomparabilidad: es una manera de convivir con ella.

Una precisión técnica que evita discusiones más adelante. La antisimetría se enuncia a menudo módulo equivalencia: dos representaciones internas distintas pueden considerarse el mismo estado si producen exactamente las mismas observaciones. Un conjunto con etiquetas internas diferentes pero los mismos elementos visibles es, a efectos del teorema, un solo estado. Esa flexibilidad no debilita nada y será útil cuando implementemos estructuras con metadatos, donde la igualdad literal de bytes es demasiado exigente.

flowchart BT
V[estado vacio] --> A[solo el elemento a]
V --> B[solo el elemento b]
A --> AB[a y b juntos]
B --> AB
AB --> T[nota a y b son incomparables entre si]
style V fill:#a6e3a1,color:#11111b
style AB fill:#89b4fa,color:#11111b
style T fill:#f9e2af,color:#11111b

La cota superior mínima y por qué es única

Sobre ese orden se levantan dos definiciones encadenadas. Un estado z es cota superior de x y de y cuando x <= z y también y <= z: un estado que sabe al menos lo que sabían los dos. Casi siempre hay muchas cotas superiores de un par, porque cualquier estado que contenga a las dos y además otras cosas también lo es.

Entre todas ellas interesa una en concreto. Una cota superior m es mínima cuando es menor o igual que cualquier otra cota superior: para todo z que sea cota superior de x e y, se cumple m <= z. La cota superior mínima es, dicho llanamente, el estado más pequeño que contiene a los dos. Se la llama también unión o supremo del par, y a la operación que la calcula la escribiremos join, que es la función de mezcla que llevamos dos lecciones buscando.

La unicidad no hay que postularla, sale gratis de la antisimetría, y merece la pena verlo porque es el argumento más corto de todo el nivel. Supón que m y n son ambas cotas superiores mínimas del mismo par. Como m es mínima y n es cota superior, m <= n. Como n es mínima y m es cota superior, n <= m. Por antisimetría, m y n son el mismo estado. Fin. Esa unicidad es la que garantiza que la mezcla sea determinista y no una elección, y por tanto es lo que satisface la prohibición de arbitraje: nadie decide nada, la estructura decide sola.

Un conjunto ordenado en el que todo par tiene cota superior mínima se llama semirretículo de unión. Se llama semi porque no exige lo simétrico, la cota inferior máxima, que aquí no nos hace falta. Y de la existencia para pares se sigue por inducción la existencia para cualquier conjunto finito y no vacío: mezclas los dos primeros, el resultado con el tercero, y así. Es útil además, aunque no imprescindible, que exista un elemento mínimo de todos —el estado inicial, el conjunto vacío, el cero— porque entonces la mezcla de la colección vacía queda definida y el arranque de una réplica nueva no es un caso especial.

Merece la pena señalar lo que la definición no exige, porque a menudo se sobreentiende de más. No se pide que exista supremo de colecciones infinitas, solo de pares, y de ahí se deduce el caso finito; los semirretículos completos son otra cosa y aquí no hacen falta. Tampoco se pide que el orden tenga altura finita, es decir, que las cadenas ascendentes acaben: un conjunto que puede crecer indefinidamente es un semirretículo perfectamente legítimo, y de hecho es el caso normal. Esa observación tiene una consecuencia práctica incómoda que la cuarta lección desarrollará: nada en la estructura impide que el estado crezca sin techo, porque la garantía es sobre la forma de la mezcla y no sobre su tamaño.

// El orden se puede leer desde la mezcla: x <= y equivale a mezclar y obtener y
const esMenorOIgual = (x, y) => sonIguales(join(x, y), y);

// Semirreticulo de conjuntos: la union es la cota superior minima
const join = (a, b) => new Set([...a, ...b]);

const x = new Set(["a"]);
const y = new Set(["b"]);
join(x, y);              // Set { "a", "b" }: contiene a los dos
esMenorOIgual(x, y);     // false: x sabe algo que y ignora
esMenorOIgual(y, x);     // false: y sabe algo que x ignora, son incomparables

Por qué esa estructura es exactamente la que hace falta

Lo interesante no es la definición sino su necesidad. Escribe la lista de exigencias que impone replicar sin árbitro, sin mirar ninguna matemática, y verás aparecer la definición entera.

La tercera tarjeta es la que más gente pasa por alto y la que más protege. Si te quedaras solo con «existe» y «no pierde», la función que devuelve siempre el elemento máximo del orden —el estado que lo contiene todo— cumpliría ambas y sería inservible. La minimalidad es el filtro que descarta esa trampa, y es la versión estructural de la queja que hicimos en la lección anterior contra el sistema que converge borrándolo todo: aquel violaba la conservación, este violaría la minimalidad, y el semirretículo prohíbe los dos a la vez.

Hay además una segunda lectura de la estructura que resulta muy práctica al implementar. Puedes recorrer el camino en sentido inverso: en lugar de definir el orden y derivar la mezcla, defines la mezcla y derivas el orden con la regla que aparece en el código de arriba, «x <= y si y solo si mezclar x con y devuelve y». Que esa relación derivada sea de verdad un orden parcial y que la mezcla sea de verdad su cota superior mínima no es automático: depende de tres propiedades algebraicas de la función, que son el asunto exacto de la lección siguiente. Las dos rutas —geométrica y algebraica— describen el mismo objeto, y en la práctica se usa la segunda porque es la que se puede comprobar con pruebas.

Ejemplos que ya usabas sin llamarlos así

La estructura es tan común que probablemente lleves años programando con ella. Los conjuntos con la unión forman un semirretículo cuyo mínimo es el conjunto vacío. Los números naturales con el máximo forman otro, con el cero abajo: por eso un contador que solo guarda «el valor más alto visto» converge sin esfuerzo. Los booleanos con el or forman el más pequeño interesante, con false abajo, y modelan la bandera que una vez encendida ya no se apaga.

De ahí salen los compuestos, que son los que se usan de verdad, y salen por dos construcciones que conviene tener a mano. El producto: si cada componente de una tupla vive en un semirretículo, la tupla forma un semirretículo mezclando componente a componente. Los vectores de versiones del nivel veintidós son exactamente eso, el producto de tantos semirretículos de máximo como réplicas haya, y esa es la razón profunda de que comparar vectores dé tres desenlaces en vez de dos: el producto de órdenes totales es un orden parcial. Y el mapa: si los valores viven en un semirretículo, los diccionarios forman otro tomando la unión de las claves y la mezcla de los valores en las claves compartidas.

// Producto: el vector de versiones es un semirreticulo de maximos
const joinVector = (a, b) => {
  const claves = new Set([...Object.keys(a), ...Object.keys(b)]);
  const r = {};
  for (const k of claves) r[k] = Math.max(a[k] ?? 0, b[k] ?? 0);
  return r;
};

// Mapa: union de claves, join en los valores compartidos
const joinMapa = (a, b, joinValor) => {
  const r = { ...a };
  for (const [k, v] of Object.entries(b)) {
    r[k] = k in a ? joinValor(a[k], v) : v;
  }
  return r;
};

Y ahora los que no lo son, que enseñan más. La suma no sirve: mezclar dos veces el mismo estado duplica el resultado, de modo que no puede ser una cota superior mínima de nada. La media tampoco: agrupar de otra manera da otro número. La intersección de conjuntos es el caso sutil, porque sí es un semirretículo, pero del otro tipo: calcula cotas inferiores, no superiores. Converge, no falla el teorema, y sin embargo es inútil aquí porque su fusión significa «olvida todo lo que alguna réplica no viera», que en cuanto haya un poco de desconexión termina en el conjunto vacío en todas partes. El registro de la última escritura, en cambio, sí es un semirretículo de unión legítimo si el desempate entre marcas iguales es total y determinista: converge de forma impecable, y sigue destruyendo trabajo exactamente como denunciamos dos niveles atrás. Ninguna de esas dos observaciones contradice al teorema; las dos recuerdan que el teorema no promete corrección.

// El registro de ultima escritura tambien es un semirreticulo de union
// si el desempate es total y no depende de quien mezcla
const joinLWW = (a, b) => {
  if (b.ts !== a.ts) return b.ts > a.ts ? b : a;
  if (b.replica !== a.replica) return b.replica > a.replica ? b : a;
  return a; // mismo instante y misma replica: es el mismo hecho
};

// Converge de forma impecable y pierde trabajo de forma impecable.
// El teorema no distingue entre esas dos cosas: eso te toca a ti.

Ese último ejemplo condensa la moraleja de la lección. Es un semirretículo válido, pasa cualquier verificación, y su noción de saber más es «tener la marca de tiempo mayor», que es una noción pobrísima de conocimiento porque descarta información en lugar de acumularla. La estructura matemática no protege del mal diseño: solo garantiza que el mal diseño será consistente en todas partes. Escoger un orden que represente de verdad la acumulación de conocimiento de tu dominio es un trabajo intelectual que no se puede delegar en el álgebra.