Las tres propiedades: conmutativa, asociativa e idempotente

La lección anterior describió la estructura desde fuera, dibujando el orden y señalando la cota superior mínima. Esta la describe desde dentro, que es como se programa: en lugar de definir el orden y deducir la mezcla, escribes la mezcla y compruebas tres igualdades sobre ella. Conmutatividad, asociatividad e idempotencia. La correspondencia entre ambas descripciones es exacta y no es folclore: una operación binaria que cumple las tres induce un orden parcial en el que ella misma es la cota superior mínima, y cada una de las tres sostiene uno y solo uno de los tres axiomas del orden. Eso convierte la verificación de un sistema distribuido en tres pruebas unitarias que corren en una sola máquina, sin red y sin concurrencia. También conviene saber qué se rompe exactamente cuando falta cada una, porque los tres fallos son distintos, y los tres han hundido productos reales.

Conmutatividad: el orden de llegada deja de existir

La primera igualdad es la más fácil de enunciar y la más fácil de incumplir sin darse cuenta: mezclar a con b debe dar el mismo resultado que mezclar b con a. Nada más. Lo que compra es enorme, porque la red no ofrece ninguna garantía sobre qué mensaje llega antes a qué réplica: dos actualizaciones que salen a la vez pueden alcanzar a un dispositivo en un orden y a otro en el contrario, y con esta propiedad ambos terminan idénticos sin haber hablado entre ellos.

El incumplimiento típico no es exótico. Cualquier mezcla que en caso de duda prefiera uno de sus dos argumentos por su posición —el primero, el segundo, el local, el remoto— es no conmutativa por construcción. Y la formulación que más veces se ha colado en producción es la del registro de última escritura mal rematado: cuando las dos marcas de tiempo coinciden, el código se queda con el argumento local. Cada réplica se queda entonces con su propio valor, la mezcla se ejecuta sin errores, los registros no muestran nada raro y la divergencia es permanente. Es el peor tipo de fallo posible, porque es silencioso y estable.

El arreglo es tan barato que da rabia: basta con que el desempate sea una función de los propios valores y no de su posición. Comparar el identificador de réplica, el resumen criptográfico del contenido, cualquier cosa que produzca siempre el mismo ganador se mire desde donde se mire. Ese desempate no hace la operación más justa —seguirá tirando el trabajo del perdedor— pero la hace conmutativa, que es lo que aquí se está discutiendo.

Hay una variante del mismo requisito en la familia basada en operaciones que conviene no confundir con esta. Allí no se pide que la mezcla de estados sea conmutativa, porque no hay mezcla de estados, sino que los efectos de dos operaciones concurrentes conmuten entre sí. La diferencia es importante y además es una buena noticia: las operaciones que están causalmente ordenadas no tienen que conmutar en absoluto, porque el canal se compromete a entregarlas en orden. Puedes tener una operación que fija un valor y otra que lo borra sin que su composición sea conmutativa, siempre que nunca puedan ser concurrentes; lo que hay que estudiar, una por una, son las parejas que sí pueden ocurrir sin verse.

Asociatividad: el agrupamiento deja de existir

La segunda igualdad dice que al mezclar tres estados da igual dónde pongas los paréntesis: mezclar el resultado de a con b junto a c produce lo mismo que mezclar a con el resultado de b con c. Si la conmutatividad neutraliza el orden, la asociatividad neutraliza el troceo, y el troceo es una variable que en un sistema real nadie controla.

Piénsalo en términos operativos. Una réplica que estuvo desconectada tres días recibe al reconectar un solo estado consolidado, porque el servidor de sincronización juntó por su cuenta todo lo que había pendiente. Otra réplica, siempre conectada, recibió esos mismos cambios de uno en uno según se producían. Una tercera recibió dos bloques, uno por cada vez que abrió la aplicación. Los tres agrupamientos son distintos y no dependen de ninguna decisión del programa, sino de la conectividad de cada aparato. La asociatividad es lo único que garantiza que los tres lleguen al mismo sitio.

Hay además una consecuencia de rendimiento que se usa constantemente. Si la operación es asociativa, un intermediario puede preagregar: mezclar por su cuenta veinte actualizaciones pendientes y enviar una sola. Toda la familia de optimizaciones basadas en deltas, en resúmenes y en compactación de colas descansa en esta propiedad y en ninguna otra. Sin asociatividad no hay derecho a juntar nada antes de tiempo, y el sistema queda obligado a transportar cada actualización por separado hasta su destino final.

flowchart LR
R1[replica uno recibe a luego b luego b repetida] --> E[estado final identico]
R2[replica dos recibe b luego a] --> E
R3[replica tres recibe un unico bloque con a y b ya mezclados] --> E
style E fill:#a6e3a1,color:#11111b

Merece la pena notar quién se beneficia de esa libertad, porque no es solo el cliente. Un servidor de retransmisión que solo reenvía puede, si la operación es asociativa, guardar un estado consolidado por documento y responder a cualquier cliente que se conecte con una sola respuesta en lugar de con el historial completo. Ese servidor no es una autoridad ni arbitra nada —sigue sin decidir quién tiene razón— y sin embargo convierte el arranque en frío de una réplica nueva en una única descarga. Toda la arquitectura de los servidores de sincronización modernos, que se anuncian como tontos a propósito, vive exactamente en este hueco que abre la asociatividad.

Idempotencia: la duplicación deja de existir

La tercera igualdad parece la más rara y es la que más dinero ahorra: mezclar un estado consigo mismo devuelve ese mismo estado. Formulada así suena a trivialidad, pero su alcance real es que aplicar dos veces la misma actualización no cambia nada, y eso es justo lo que necesita cualquier protocolo de transporte honesto.

La razón es que la entrega exactamente una vez no existe en una red asíncrona sin un aparato considerable de identificadores y acuses persistentes. Lo que sí existe, y es barato, es la entrega al menos una vez: reintentar hasta recibir confirmación, sabiendo que a veces la confirmación se pierde y el mensaje viaja dos veces. Con una mezcla idempotente, ese caso deja de ser un problema y se convierte en un no-suceso. El emisor puede reenviar con toda tranquilidad, el receptor no necesita llevar registro de qué ha visto, y los protocolos de antientropía, que consisten literalmente en «mándame tu estado de vez en cuando por si acaso», pasan a ser correctos por defecto.

El contraejemplo canónico es el contador que se sincroniza sumando, y su arreglo enseña la técnica que usaremos una y otra vez. Si cada réplica lleva su propio subtotal y la mezcla toma el máximo por réplica en lugar de sumar, la operación pasa a ser idempotente sin dejar de contar bien: el total es la suma de los máximos, calculada al leer. Ha desaparecido la suma de la mezcla, que era donde molestaba, y ha aparecido en la lectura, que es donde no hace daño.

// Contador ingenuo: la mezcla suma y por tanto duplica en cada reenvio
const joinMal = (a, b) => a + b;             // joinMal(5, 5) = 10

// Contador correcto: un subtotal por replica y maximo componente a componente
const joinBien = (a, b) => {
  const r = { ...a };
  for (const [k, v] of Object.entries(b)) r[k] = Math.max(a[k] ?? 0, v);
  return r;
};

const total = (s) => Object.values(s).reduce((x, y) => x + y, 0);
// joinBien es idempotente, conmutativa y asociativa: reenviar sale gratis

Junto con las dos anteriores, la idempotencia produce el resultado que la lección quinta usará como pieza central: mezclar una colección de estados deja de depender de cuántas veces aparece cada uno. El multiconjunto de mensajes recibidos se colapsa en su conjunto subyacente, y con ello el estado pasa a ser función del conjunto entregado, que era literalmente el enunciado del teorema.

// Las tres propiedades como comprobacion ejecutable sobre cualquier candidato
function verificar(join, iguales, muestras) {
  const fallos = [];
  for (const a of muestras) {
    if (!iguales(join(a, a), a)) fallos.push("idempotencia");
    for (const b of muestras) {
      if (!iguales(join(a, b), join(b, a))) fallos.push("conmutatividad");
      for (const c of muestras) {
        const izq = join(join(a, b), c);
        const der = join(a, join(b, c));
        if (!iguales(izq, der)) fallos.push("asociatividad");
      }
    }
  }
  return [...new Set(fallos)];
}

Esa función de veinte líneas es, en un sentido muy literal, la verificación de tu sistema distribuido. No hay red en ella, no hay concurrencia, no hay fallos de nodo y no hay relojes: hay una función binaria y unas cuantas muestras. En proyectos serios se ejecuta con generación aleatoria de casos, porque la lista de muestras escritas a mano siempre olvida el estado raro que produce el fallo.

Qué se rompe exactamente cuando falta una

Aquí llega la parte que hace que las tres propiedades dejen de parecer arbitrarias. Cada una sostiene uno de los tres axiomas del orden parcial, y la correspondencia es biunívoca. Recuerda que el orden se puede derivar de la mezcla con la regla «x <= y cuando mezclar x con y devuelve y». Con esa definición, la reflexividad —x <= x— es literalmente la idempotencia reescrita. La antisimetría sale de la conmutatividad: si mezclar x con y da y y mezclar y con x da x, la conmutatividad iguala los dos lados izquierdos y por tanto x e y son el mismo estado. Y la transitividad sale de la asociatividad: si mezclar x con y da y y mezclar y con z da z, entonces mezclar x con z es mezclar x con la mezcla de y y z, que reagrupada es mezclar la mezcla de x e y con z, o sea y con z, o sea z.

Los tres contraejemplos clásicos son buenos compañeros de memoria. La suma es conmutativa y asociativa pero no idempotente, y por eso un contador que se sincroniza enviando su total y sumando es correcto hasta el primer reintento del transporte. La media es conmutativa pero no asociativa: promediar el promedio de dos con un tercero no es promediar los tres, así que el resultado depende de cómo se agruparon los envíos, que es la variable menos controlable de todas. Y quedarse con el argumento local en caso de empate es asociativa e idempotente pero no conmutativa, con el desenlace peor: convergencia aparente y divergencia real.

// Tres candidatos y la propiedad que le falta a cada uno
const suma  = (a, b) => a + b;         // suma(3, 3) = 6, no idempotente
const media = (a, b) => (a + b) / 2;   // media(media(0, 0), 6) = 3
                                       // media(0, media(0, 6)) = 1.5, no asociativa

const ultimaEscritura = (a, b) =>      // empate resuelto por posicion:
  b.ts > a.ts ? b : a;                 // devuelve a si a.ts === b.ts, no conmutativa

// El arreglo de la tercera: desempate por contenido, no por posicion
const ultimaEscrituraBien = (a, b) =>
  b.ts > a.ts || (b.ts === a.ts && b.replica > a.replica) ? b : a;

Un aviso final sobre el alcance de la verificación, porque es donde se cuelan los errores de quien ya sabe todo esto. Las tres propiedades hay que comprobarlas sobre los estados que tu sistema puede producir de verdad, no sobre cualquier estructura que encaje en el tipo. Es perfectamente posible escribir una mezcla que sea conmutativa, asociativa e idempotente sobre estados bien formados y deje de serlo sobre estados que solo aparecen tras una migración de esquema, una versión antigua de la aplicación o un campo que llega vacío. Por eso la generación aleatoria debe partir del estado inicial y aplicar operaciones reales: lo que se está verificando no es una función abstracta, es una función sobre el conjunto de estados alcanzables de tu programa.