WOOT: el primero, y el precio de ordenar por precedencia

Antes de 2006, la edición colaborativa era territorio casi exclusivo de la transformación de operaciones, una familia de algoritmos que reescribe cada operación entrante en función de las que ya se aplicaron y cuya corrección depende de propiedades que resultaron sorprendentemente difíciles de demostrar en escenarios sin servidor: varias de las transformaciones publicadas en los años noventa fueron después refutadas con contraejemplos. WOOT —de WithOut Operational Transformation, presentado por Oster, Urso, Molli e Imine en 2006— atacó el problema por el lado contrario. En vez de corregir índices que el tiempo invalida, dio a cada carácter una identidad inmutable y derivó el orden del documento de relaciones de precedencia entre esas identidades. La idea era correcta y sigue siéndolo: es el molde del que salen todos los algoritmos posteriores de esta lista. El algoritmo que la encarnaba era, en cambio, tan caro que ninguna aplicación real lo adoptó, y merece estudiarse justamente por eso, porque separa con una nitidez poco habitual la aportación conceptual, que sobrevivió intacta, del coste de implantación, que sus sucesores dedicaron una década a rebajar.

El índice es el enemigo

El origen de todo el problema cabe en una frase: la posición tres no significa lo mismo en dos réplicas que han visto operaciones distintas. Si una réplica emite insertar la letra a en la posición 3 mientras otra borra el carácter 1, la operación llega a un documento donde el índice 3 ya designa otra cosa, y el resultado es una divergencia silenciosa que ninguna de las dos partes puede detectar localmente. La transformación de operaciones respondía ajustando el índice de la operación entrante contra cada operación concurrente ya aplicada; funcionaba, pero su corrección exigía que las funciones de transformación cumplieran ciertas propiedades de composición cuya verificación resultó ser un problema abierto durante años.

WOOT propone la única alternativa estructural disponible: si el índice no es estable, no lo uses como referencia. Cada carácter recibe en el momento de su creación un identificador único e inmutable, formado por el identificador de la réplica que lo escribió y un contador local que esa réplica nunca reutiliza. Una inserción deja de decir ponme en la posición 3 y pasa a decir ponme entre el carácter con identidad X y el carácter con identidad Y. Esa frase significa exactamente lo mismo en todas las réplicas y en cualquier momento del futuro, porque X e Y no se mueven: son nombres, no coordenadas.

De ahí sale el nombre del algoritmo. Al referirse a vecinos en lugar de a posiciones, la operación no necesita corrección alguna al llegar: se integra tal cual se emitió. La complejidad no desaparece —tiene que ir a alguna parte—, sino que se traslada del emisor al receptor, del momento de transformar al momento de decidir dónde cae exactamente el carácter cuando entre X e Y ya hay otros caracteres que no estaban allí cuando se emitió la operación.

La estructura: caracteres que declaran a sus vecinos

Un documento WOOT no es una cadena, es un conjunto de objetos llamados W-caracteres. Cada uno guarda su identificador, su valor, un indicador de visibilidad y las identidades de los dos caracteres entre los que se insertó originalmente. El documento se inicializa con dos centinelas, una marca de inicio y una marca de fin, que existen en todas las réplicas desde el primer instante y garantizan que cualquier inserción tenga siempre dos vecinos a los que referirse.

// Un W-caracter: identidad propia mas los dos vecinos declarados al nacer
const wchar = {
  id: { sitio: 7, reloj: 42 },      // unico, inmutable, jamas reutilizado
  valor: "a",
  visible: true,                     // el borrado solo apaga este indicador
  anterior: { sitio: 3, reloj: 9 },  // vecino izquierdo en el momento de crearse
  siguiente: { sitio: 0, reloj: 0 }  // vecino derecho, aqui la marca de fin
};

Dos consecuencias de esta estructura merecen atención inmediata. La primera es que el borrado no borra: apaga el indicador de visibilidad y deja el objeto en su sitio. No es una torpeza sino una necesidad, porque una operación concurrente emitida por otra réplica puede estar declarando como vecino precisamente ese carácter, y si el objeto desapareciera la operación entrante quedaría sin referencia. El objeto apagado se llama lápida, y en WOOT las lápidas son permanentes: el documento solo puede crecer.

La segunda es que la integración tiene una precondición de causalidad. Una inserción solo puede aplicarse cuando los dos caracteres que menciona ya están presentes en la réplica receptora; si aún no han llegado, la operación se pone en espera. Esto obliga a acompañar el algoritmo de un mecanismo de entrega causal, que es exactamente la maquinaria de relojes vectoriales del nivel 22, y explica por qué aquel bloque venía antes que este.

// La precondicion se implementa como una cola que se reintenta al llegar cada operacion
function recibir(doc, op, pendientes) {
  pendientes.push(op);
  let progreso = true;
  while (progreso) {
    progreso = false;
    for (const p of [...pendientes]) {
      if (!ejecutable(doc, p)) continue;        // faltan uno o los dos vecinos citados
      aplicar(doc, p);
      pendientes.splice(pendientes.indexOf(p), 1);
      progreso = true;                          // aplicar una puede desbloquear a otras
    }
  }
  return pendientes;
}

El bucle no es un detalle de implementación sino la forma en que el algoritmo admite el desorden de la red: las operaciones llegan en cualquier secuencia, se acumulan hasta que sus dependencias aparecen y entonces se aplican en cascada. Una réplica que ha estado desconectada recibe un montón de operaciones aparentemente inaplicables y las va desbloqueando unas a otras hasta vaciar la cola, sin que en ningún momento haya que negociar nada con nadie. Es la primera vez en el track que se ve la convergencia funcionando en el peor escenario de entrega, y conviene reconocer el patrón porque los cuatro algoritmos siguientes lo reutilizan sin cambios.

La integración recursiva y de dónde sale el coste

El caso fácil es cuando entre los dos vecinos declarados no hay nada: el carácter se coloca ahí y se acabó. El caso interesante es cuando otras réplicas insertaron concurrentemente en ese mismo hueco, y entonces hay que decidir un orden entre caracteres que nadie ordenó. WOOT lo resuelve reduciendo el intervalo: descarta de la ventana los caracteres cuyos vecinos declarados caen fuera de ella —porque su posición ya está determinada por una relación más externa— y sobre los que quedan aplica el orden total de los identificadores para elegir el punto de corte, repitiendo el procedimiento sobre el subintervalo resultante hasta que la ventana queda vacía.

// Esbozo fiel a la estructura del algoritmo publicado, no a una implementacion concreta
function integrarInsercion(doc, c, idIzq, idDer) {
  const ventana = subsecuencia(doc, idIzq, idDer);
  if (ventana.length === 0) return colocarEntre(doc, c, idIzq, idDer);

  // Solo compiten los caracteres cuyos dos vecinos caen fuera del intervalo
  const L = [idIzq, ...ventana.filter((w) => vecinosFuera(w, idIzq, idDer)).map((w) => w.id), idDer];

  let i = 1;
  while (i < L.length - 1 && menorQue(L[i], c.id)) i += 1;
  return integrarInsercion(doc, c, L[i - 1], L[i]);   // se repite sobre un hueco mas estrecho
}

El coste vive en las tres líneas centrales. Calcular la subsecuencia entre dos identidades exige recorrer el documento, y el documento incluye todas las lápidas acumuladas desde el primer día. Ese recorrido se repite en cada nivel de la recursión, y la recursión puede profundizar tantas veces como caracteres concurrentes haya en el hueco. Los análisis del periodo situaban el peor caso de la integración en un polinomio cúbico sobre el número de caracteres del documento, lápidas incluidas, y ese lápidas incluidas es lo que convierte un mal dato asintótico en un problema práctico: el coste no depende del texto visible sino de todo lo que se ha escrito y borrado en la historia del documento.

flowchart TD
OP[integrar c entre izq y der] --> S[calcular la ventana entre izq y der]
S --> V[la ventana esta vacia]
V --> INS[colocar c aqui y terminar]
S --> NV[hay caracteres concurrentes dentro]
NV --> F[descartar los que dependen de fuera]
F --> CMP[comparar identificadores y elegir el corte]
CMP --> REC[repetir sobre un hueco mas estrecho]
REC --> S
style INS fill:#a6e3a1,color:#11111b
style REC fill:#f38ba8,color:#11111b

Conviene hacer la cuenta con números concretos, porque el argumento asintótico se queda corto y el argumento de memoria es demoledor por sí solo. Un W-carácter guarda un valor de un carácter y tres identificadores: el suyo y los de sus dos vecinos. Si cada identificador ocupa lo que ocupa un par formado por un entero de réplica y un contador, el objeto pesa del orden de una o dos decenas de bytes para transportar un solo carácter de texto, y ese factor no baja nunca porque no hay nada redundante que eliminar entre un carácter y el siguiente: los vecinos declarados son distintos en cada uno. A eso hay que sumar que las lápidas nunca se van, de modo que un documento donde se ha escrito y reescrito durante meses guarda todas las versiones intermedias con su sobrecoste íntegro.

Las variantes posteriores atacaron exactamente esos puntos sin tocar el modelo conceptual. WOOTO, hacia 2007, añadió a cada carácter un grado de anidamiento que permite descartar candidatos por comparación numérica en lugar de inspeccionar sus vecinos, y WOOTH, evaluado hacia 2011 junto al resto de la familia, sustituyó el recorrido lineal por una tabla asociativa de identidad a nodo que hace constante la localización de un carácter. Las mediciones comparadas de aquel momento mostraron que la versión con tabla se comportaba muy por encima de lo que sugería el análisis del peor caso, pero llegaron cuando la comunidad ya había encontrado estructuras que no necesitaban esa rehabilitación.

Lo que sobrevivió

WOOT no se usa hoy en ningún producto que merezca ese nombre, y sin embargo casi todo lo que se usa desciende de él. Aportó tres piezas que ninguno de sus sucesores discute: la identidad inmutable por elemento como sustituto del índice, la lápida como precio de admitir referencias a lo borrado, y la idea de que el orden del documento debe ser una función determinista del conjunto de operaciones conocidas y no del orden en que llegaron. Lo que quedó atrás fue la representación concreta —dos referencias explícitas por carácter y una ventana que hay que recalcular— y la ausencia de cualquier mecanismo para reducir el coste de la historia acumulada.

Hay además una aportación negativa, en el sentido de que enseñó lo que no hay que hacer, y es igual de valiosa. WOOT nombra a los dos vecinos, que es la manera intuitiva de expresar ponme aquí en medio, y esa redundancia es justamente lo que obliga a recalcular ventanas y a comparar candidatos por su dependencia con el exterior del intervalo. La lección 3 muestra que basta con nombrar a uno solo, y que renunciar a la mitad de la información no cuesta corrección sino una anomalía menor de agrupamiento. Ese descubrimiento —que la referencia asimétrica es suficiente— es el que convierte un algoritmo polinómico en uno esencialmente local, y no se podía hacer sin haber recorrido antes el camino simétrico.

Las dos vías que la lección 2 y la lección 4 exploran nacen de rechazar la otra mitad del diseño de WOOT, la de las lápidas. Si el nombre de un carácter no menciona a ningún vecino sino que codifica directamente su posición en un orden denso, borrar deja de invalidar referencias y las lápidas desaparecen. Es una idea legítima, se llevó a la práctica dos veces y ambas veces se estrelló contra el mismo muro, que no es de rendimiento sino de aritmética. Así que el mapa del nivel puede resumirse como tres reacciones a WOOT: quitar la mitad de las referencias, quitar todas las referencias, o quitar las lápidas. La primera funcionó.