La estructura: un nodo que sabe de quién cuelga

Hasta aquí RGA ha sido un dibujo: un árbol de inserciones, una regla de desempate, unas lápidas. A partir de esta lección deja de serlo. Vamos a escribir la estructura completa, ejecutarla y comprobar en una consola real que dos réplicas que reciben las mismas operaciones en órdenes distintos terminan con el mismo texto, carácter a carácter. El punto de partida es la decisión más pequeña y más consecuente de todo el diseño: qué guarda un nodo. La respuesta son cuatro campos, y el tercero de ellos —una referencia al elemento que tenía a su izquierda cuando nació— es el que separa una estructura que converge de una que produce basura. Antes de escribir una línea de la estructura buena conviene ejecutar la mala, porque el fallo de la ingenua no es una intuición: es una salida de consola que se puede reproducir en diez segundos.

Por qué una posición no puede viajar por la red

El modelo que casi todo el mundo escribe primero manda la posición dentro de la operación: inserta una equis en el índice dos, borra el carácter del índice cero. Es cómodo, es lo que expone cualquier editor y es exactamente lo que falla. Una posición es un número relativo a un estado concreto, y en cuanto la operación llega a una réplica que ha visto otras ediciones, ese estado ya no es el mismo. No hace falta un caso rebuscado para verlo.

// Modelo ingenuo: la operacion viaja con una posicion numerica
function aplicar(texto, op) {
  return op.tipo === "insertar"
    ? texto.slice(0, op.pos) + op.valor + texto.slice(op.pos)
    : texto.slice(0, op.pos) + texto.slice(op.pos + 1);
}

const inicial = "HOLA";
const deAna = { tipo: "insertar", pos: 2, valor: "X" };
const deBeto = { tipo: "borrar", pos: 0 };

console.log("ana  aplica la suya y luego la de beto:", aplicar(aplicar(inicial, deAna), deBeto));
console.log("beto aplica la suya y luego la de ana :", aplicar(aplicar(inicial, deBeto), deAna));

ana  aplica la suya y luego la de beto: OXLA
beto aplica la suya y luego la de ana : OLXA

Dos réplicas, dos operaciones, ninguna pérdida de mensajes y ninguna red inestable: OXLA frente a OLXA. El borrado de Beto desplazó todo un lugar a la izquierda y la posición dos de Ana pasó a señalar otra cosa. La operación no era incorrecta cuando se emitió; dejó de ser correcta al viajar, porque su significado dependía de un contexto que se quedó en el origen. Esa es toda la enfermedad, y la cura consiste en que la operación lleve consigo aquello que la hace interpretable en cualquier réplica.

El nodo: sello, padre, valor y lápida

RGA sustituye la posición por una identidad. Cada carácter insertado recibe un sello propio que no se reutiliza jamás, y la operación no dice dónde va sino tras quién va. La referencia deja de ser un número frágil y pasa a ser el sello de otro nodo, que es inmutable: el elemento al que apunta puede quedar oculto, puede quedar rodeado de texto nuevo, puede desplazarse mil posiciones a la derecha, y la referencia sigue señalando exactamente lo mismo.

// Un nodo de RGA: cuatro campos y ni uno mas
const nodo = {
  id: { contador: 5, replica: "ana" },     // sello propio, unico y estable
  padre: { contador: 4, replica: "ana" },  // sello del vecino izquierdo al nacer
  valor: " ",                              // el contenido visible
  borrado: false                           // lapida logica
};

El sello es un par { contador, replica }: un reloj lógico de Lamport más el identificador de quien lo emitió. El contador ordena, la réplica desempata, y la pareja completa da un orden total sobre todos los sellos del sistema sin necesidad de coordinación alguna. Su tamaño es constante y no depende de cuánto se haya escrito antes ni de dónde: esa es la diferencia esencial con las familias posicionales del nivel 31, donde el nombre codificaba el lugar y por tanto tenía que crecer.

Merece la pena detenerse en la elección del vecino izquierdo y no del derecho. Es una asimetría deliberada, no un capricho. Al escribir, el cursor avanza hacia la derecha: cada carácter nuevo cuelga del que acabas de teclear, de modo que una ráfaga de escritura produce una cadena de nodos con contadores consecutivos, cada uno hijo del anterior. Esa regularidad es la que la lección 5 convertirá en compresión. Si hubiéramos elegido el vecino derecho, una ráfaga produciría nodos que cuelgan todos del mismo punto y competirían entre sí en cada inserción.

La raíz centinela y el invariante del sello creciente

Un nodo cuelga de otro, pero el primer carácter de un documento vacío no tiene de quién colgar. La solución es un centinela: un nodo con sello { contador: 0, replica: "" }, sin padre, sin valor y marcado como borrado desde el principio, que existe idéntico en todas las réplicas sin que nadie tenga que transmitirlo. Insertar al comienzo del documento es insertar tras la raíz, y así el caso especial desaparece del algoritmo.

flowchart TD
R[raiz sello 0] --> H[H sello 1 de ana]
H --> O[O sello 2 de ana]
O --> L[L sello 3 de ana]
L --> A[A sello 4 de ana]
A --> M[espacio sello 5 de ana]
A --> C[espacio sello 5 de beto]
M --> M2[M sello 6 de ana]
C --> C2[C sello 6 de beto]
style M fill:#89b4fa,color:#11111b
style C fill:#a6e3a1,color:#11111b

El diagrama muestra el documento HOLA con dos ráfagas concurrentes colgando de la misma A. Fíjate en dos cosas. La primera es que cada ráfaga forma su propia cadena descendente, y por eso los bloques no se entremezclan: la M de Ana no compite con nada de Beto, porque su padre es un nodo que Beto ni siquiera conoce. La segunda es que los dos espacios llevan el contador cinco: son genuinamente concurrentes, ninguno vio al otro, y decidir cuál va primero es el asunto de la lección siguiente.

const RAIZ = { contador: 0, replica: "" };
const clave = (id) => `${id.contador}@${id.replica}`;

function comparar(a, b) {
  if (a.contador !== b.contador) return a.contador - b.contador;
  return a.replica < b.replica ? -1 : a.replica > b.replica ? 1 : 0;
}

function crearReplica(replica) {
  const raiz = { id: RAIZ, padre: null, valor: "", borrado: true };
  return {
    replica,
    reloj: 0,
    lista: [raiz],                              // linealizacion, no arbol explicito
    indice: new Map([[clave(RAIZ), raiz]]),     // de sello a nodo, en tiempo constante
    pendientes: []                              // operaciones cuyo padre aun no llego
  };
}

Hay una decisión de representación en ese fragmento que conviene declarar en voz alta: el árbol no se materializa. Guardamos un array plano ya linealizado, y la relación de paternidad vive solo en el campo padre de cada nodo. Leer el documento es entonces recorrer el array de izquierda a derecha, sin recursión y sin ordenar nada. El precio de esa comodidad es que insertar exige encontrar el punto correcto del array, y ese es justamente el trabajo de la próxima lección.

La tabla indice merece un comentario aparte, porque su papel no es el que sugiere su nombre. No sirve para ordenar ni para buscar posiciones: sirve para responder en tiempo constante a la única pregunta que hace la integración, que es ¿tengo ya el nodo con este sello?. De esa pregunta dependen dos cosas distintas y ambas críticas. La primera es saber si el padre de una operación entrante está presente, y por tanto si la operación se puede aplicar o hay que aparcarla. La segunda es detectar duplicados, que es lo que hace que reenviar un mensaje no tenga ningún efecto. Sin esa tabla habría que barrer el array en las dos comprobaciones, y como se hacen una vez por operación recibida, el coste sería inaceptable en cuanto llegara una sincronización grande.

El invariante que sostendrá todo lo demás

Antes de escribir la inserción conviene enunciar una propiedad que parece anecdótica y que en la lección siguiente hará todo el trabajo pesado: el sello de un nodo es siempre mayor que el sello de su padre. La razón es que solo puedes insertar tras un elemento que ya has visto, y el reloj de Lamport se actualiza al máximo de lo observado antes de emitir. Por construcción, entonces, todos los descendientes de un nodo tienen sellos mayores que él, y un subárbol entero queda acotado por abajo por el sello de su raíz.

// Comprobacion sobre un documento ya construido con ediciones concurrentes
let ok = true;
for (const n of ana.lista) if (n.padre && comparar(n.id, n.padre) <= 0) ok = false;
console.log("todo hijo tiene sello mayor que su padre:", ok);

todo hijo tiene sello mayor que su padre: true

Esa línea de salida parece trivial y es la que permitirá que la inserción de la lección siguiente sea un bucle de tres líneas en vez de un recorrido de árbol con contabilidad de subárboles. Si todos los descendientes de un nodo tienen sellos mayores que él, entonces un barrido que avance mientras encuentre sellos mayores atraviesa subárboles completos sin necesidad de saber dónde empiezan ni dónde terminan, y se detiene exactamente en la frontera correcta. Conviene por eso tratar el invariante como una aserción de verdad y no como una curiosidad: si alguna vez lo rompes —por ejemplo olvidando sincronizar el reloj al recibir—, el algoritmo no fallará con una excepción, colocará nodos en sitios equivocados y las réplicas divergirán en silencio.