Insertar: generar el sello, buscar el sitio y desempatar

Con el nodo definido, insertar consiste en responder tres preguntas seguidas: qué sello le doy, en qué punto del array lo coloco y qué hago cuando otra réplica ya puso algo justo ahí. Las tres respuestas caben en un puñado de líneas, y la tercera es la que da a RGA su reputación de algoritmo asombrosamente barato: el desempate entre hermanos concurrentes se resuelve comparando dos números, sin negociar nada con nadie y sin recordar nada de lo que pasó antes. Lo interesante es que el barrido que encuentra el sitio y el desempate entre hermanos son la misma línea de código, y que esa coincidencia no es un atajo de implementación sino una consecuencia directa del invariante que cerraba la lección anterior. Esta lección escribe esas líneas, las ejecuta y enseña qué sellos concretos genera cada réplica cuando dos personas teclean a la vez en el mismo punto.

Generar el sello: un reloj que solo sabe avanzar

El sello se fabrica con un contador local que sigue dos reglas y nada más. Al emitir una operación propia, el contador sube en uno. Al aceptar una operación ajena, el contador salta al máximo entre su valor actual y el contador que traía la operación recibida. Es el reloj de Lamport en su forma más desnuda, y garantiza justo lo que necesitamos: si una réplica vio un nodo antes de escribir, su sello nuevo será mayor que el de aquel nodo.

function insertar(rep, padre, valor) {
  rep.reloj += 1;                                // regla uno: emitir sube el reloj
  const op = {
    tipo: "insertar",
    id: { contador: rep.reloj, replica: rep.replica },
    padre,
    valor
  };
  aplicar(rep, op);
  return op;                                     // se devuelve para difundirla
}

La segunda regla vive en el receptor y es igual de corta: rep.reloj = Math.max(rep.reloj, op.id.contador). Sin ella el reloj de una réplica silenciosa se quedaría atrás y sus escrituras posteriores nacerían con sellos artificialmente pequeños, lo que rompería el invariante y colocaría los nodos en sitios absurdos. Con ella, el reloj de cada réplica es siempre al menos tan grande como todo lo que ha visto.

Encontrar el sitio: un barrido a la derecha del padre

Ya con el sello, colocar el nodo en el array linealizado es un bucle. Se localiza el padre por la tabla asociativa, se avanza una posición —el hueco inmediatamente a su derecha es el candidato natural— y a partir de ahí se avanza mientras el nodo que se encuentre tenga un sello mayor que el del nodo entrante. En cuanto aparece uno con sello menor, ahí va.

function integrar(rep, nodo) {
  let i = rep.lista.indexOf(rep.indice.get(clave(nodo.padre))) + 1;
  while (i < rep.lista.length && comparar(rep.lista[i].id, nodo.id) > 0) i += 1;
  rep.lista.splice(i, 0, nodo);
  rep.indice.set(clave(nodo.id), nodo);
}

flowchart TD
P[localizar el padre por la tabla de sellos] --> A[mirar la posicion siguiente]
A --> C{el sello de aqui es mayor que el mio}
C -->|si| D[avanzar una posicion]
D --> C
C -->|no| E[insertar aqui]
C -->|fin del array| E
style D fill:#f9e2af,color:#11111b
style E fill:#a6e3a1,color:#11111b

Enunciada así, la condición parece incompleta: si voy avanzando por el array, tarde o temprano me saldré del subárbol del padre y pisaré nodos que no son hermanos del entrante. ¿No habría que comprobar la paternidad en cada paso? La respuesta es que no, y la razón es el invariante de la lección anterior. Vale la pena desmontarla en los tres casos que pueden aparecer a la derecha del padre, porque entenderlos es entender RGA entero.

La segunda tarjeta es la que hace el trabajo silencioso. Cuando el barrido descarta a un hermano por tener sello mayor, también descarta gratis a toda su descendencia, porque el invariante garantiza que ningún descendiente puede tener un sello menor que su ancestro. No hace falta calcular tamaños de subárbol ni llevar contadores: la aritmética del reloj de Lamport ya ordenó el array de manera que un simple avanza mientras sea mayor recorre exactamente los subárboles que hay que recorrer y se detiene exactamente donde hay que detenerse.

La tercera es la que impide que el barrido se desmande. Lo primero que aparece tras el subárbol de un nodo es un hermano posterior de ese nodo o de alguno de sus ancestros; por la ordenación descendente entre hermanos, ese elemento tiene sello menor que el ancestro correspondiente, que a su vez es menor que el del padre, que a su vez es menor que el nuestro. El bucle se para ahí, sin que nadie se lo haya dicho.

La regla de desempate, ejecutada

Toda la regla está en comparar: gana el contador mayor y, si empatan, el identificador de réplica mayor en orden lexicográfico. El hermano que gana se coloca primero. Veámoslo con dos ráfagas genuinamente concurrentes sobre un documento sincronizado.

const ana = crearReplica("ana"), beto = crearReplica("beto");
const base = escribir(ana, 0, "HOLA");
for (const op of base) recibir(beto, op);      // las dos parten de HOLA

const deAna = escribir(ana, 4, "-uno");        // ana teclea al final
const deBeto = escribir(beto, 4, "-dos");      // beto tambien, sin ver a ana

console.log("sellos de ana :", deAna.map((o) => clave(o.id)).join(" "));
console.log("sellos de beto:", deBeto.map((o) => clave(o.id)).join(" "));
console.log("padres de ana :", deAna.map((o) => clave(o.padre)).join(" "));
console.log("padres de beto:", deBeto.map((o) => clave(o.padre)).join(" "));
console.log("comparar el primero de beto con el primero de ana:", comparar(deBeto[0].id, deAna[0].id));

for (const op of deBeto) recibir(ana, op);
for (const op of deAna) recibir(beto, op);
console.log("resultado: ana =", texto(ana), " beto =", texto(beto));

sellos de ana : 5@ana 6@ana 7@ana 8@ana
sellos de beto: 5@beto 6@beto 7@beto 8@beto
padres de ana : 4@ana 5@ana 6@ana 7@ana
padres de beto: 4@ana 5@beto 6@beto 7@beto
comparar el primero de beto con el primero de ana: 1
resultado: ana = HOLA-dos-uno  beto = HOLA-dos-uno

Esa salida contiene tres hechos que conviene leer despacio. El primero: los dos contadores arrancan en cinco, porque ambas réplicas habían visto exactamente los mismos cuatro caracteres. El empate es real y solo lo rompe el nombre de la réplica, donde beto es lexicográficamente posterior a ana. El segundo: solo el primer nodo de cada ráfaga tiene por padre a 4@ana; los tres siguientes cuelgan del anterior de su propia ráfaga. Por eso los bloques salen enteros y no alternados: la salida es -dos-uno, no una alternancia carácter a carácter de las dos ráfagas. El tercero: las dos réplicas terminan idénticas, y ninguna de las dos ve el texto que tenía localmente hace un instante. Ana escribió HOLA-uno y ahora lee HOLA-dos-uno.

Aplicar, aceptar y encolar: la inserción completa

Falta cerrar el circuito entre la operación que llega por la red y la integración. La función aplicar es la frontera: comprueba que el padre existe, descarta duplicados, sincroniza el reloj e integra. Devuelve un booleano, y ese booleano es el que decide si la operación se consume o se guarda para más tarde.

function aplicar(rep, op) {
  if (op.tipo === "insertar") {
    if (!rep.indice.has(clave(op.padre))) return false;   // aun no tengo el ancla
    if (rep.indice.has(clave(op.id))) return true;        // ya la tenia: idempotente
    rep.reloj = Math.max(rep.reloj, op.id.contador);      // regla dos del reloj
    integrar(rep, { id: op.id, padre: op.padre, valor: op.valor, borrado: false });
    return true;
  }
  const objetivo = rep.indice.get(clave(op.id));
  if (!objetivo) return false;
  objetivo.borrado = true;
  return true;
}

function recibir(rep, op) {
  rep.pendientes.push(op);
  let progreso = true;
  while (progreso) {                                      // reintentar hasta estancarse
    progreso = false;
    for (let i = 0; i < rep.pendientes.length; i += 1) {
      if (aplicar(rep, rep.pendientes[i])) {
        rep.pendientes.splice(i, 1); i -= 1; progreso = true;
      }
    }
  }
}

Las dos primeras líneas de aplicar son las que hacen que el resto del nivel funcione. La comprobación del padre convierte la exigencia teórica de entrega causal en una condición local y verificable: si falta el ancla, la operación no se pierde, se aparca. La comprobación de duplicado hace la operación idempotente, de modo que reenviar el mismo mensaje cien veces no cambia nada. Juntas permiten un transporte tonto —difusión sin garantías, reintentos ciegos, reconexiones que reenvían de más— sin que la corrección dependa de él.