La convergencia no basta: el problema de fusionar la memoria de un programa en vivo

Fuentes: Convergence Is Not Enough

Alex Warth, junto a Dan Ingalls y Peter Van Hardenberg, desarrolla dentro del proyecto Livelymerge un sistema inspirado en Lively Kernel cuyo montículo completo —objetos, clases y métodos— es un documento de Automerge. La promesa de Automerge es la convergencia: tras sincronizar cambios, todos los clientes llegan al mismo estado. Sin embargo, Warth advierte de que la convergencia resulta insuficiente cuando Automerge debe fusionar la memoria de un programa en ejecución, incluidos sus punteros, porque el algoritmo reejecuta efectos y no intenciones.

Para ilustrarlo, el artículo recurre a una lista enlazada 1→2→3→4. El cliente A intercambia 2 y 3 y el cliente B intercambia 3 y 4. Tras la fusión, dependiendo del orden elegido por Automerge, la lista queda truncada o genera un ciclo infinito. Ambas situaciones cumplen la garantía de convergencia, pero violan la invariante de la estructura. El problema se amplía a listas doblemente enlazadas, árboles —incluido el grafo de morphs de Morphic—, cuentas cacheadas o cualquier restricción que abarque más de una propiedad u objeto.

En la práctica, los autores han paliado la cuestión apoyándose en los tipos de datos integrados de Automerge y evitando representaciones redundantes, pero reconocen que la programación cuidadosa no es una solución definitiva. Como dirección prometedora, proponen tipos de datos conscientes de la fusión: que Automerge exponga no solo listas, mapas y contadores, sino también la posibilidad de definir tipos nuevos cuyas operaciones de alto nivel se registren en el historial y se fusionen con semántica propia. Citan como precedente el trabajo de Kleppmann et al. sobre árboles replicados, que incorpora la invariante «reparentar nunca crea un ciclo» directamente en la fusión, y mencionan sistemas como BASIL para ilustrar la viabilidad del enfoque.