Comparación eficiente de DAG en una red

En los sistemas de control de versiones distribuidas (como Mercurial y Git ) existe la necesidad de comparar eficientemente los gráficos acíclicos dirigidos (DAG). Soy un desarrollador de Mercurial, y estaríamos muy interesados ​​en escuchar sobre el trabajo teórico que discute la complejidad del tiempo y la red de comparar dos DAG.

Los DAG en cuestión están formados por las revisiones registradas. Las revisiones se identifican de forma exclusiva por un valor hash. Cada revisión depende de cero (confirmación inicial), una (confirmación normal) o más (confirmación de fusión) de las revisiones anteriores. Aquí es un ejemplo donde las revisiones aa ese hicieron una después de la otra:

a --- b --- c --- d --- e

La comparación gráfica aparece cuando alguien tiene solo una parte del historial y quiere recuperar la parte que falta. Imagínese que tenía aa ce hice xy ybasándonos en c:

a --- b --- c --- x --- y

En Mercurial, haría hg pully descargaría dy e:

a --- b --- c --- x --- y
              \
                d --- e

El objetivo es identificar dy eeficientemente cuando el gráfico tiene muchos (digamos, más de 100,000) nodos. La eficiencia concierne a ambos

• complejidad de la red: la cantidad de bytes transferidos y la cantidad de viajes de ida y vuelta necesarios
• complejidad de tiempo: la cantidad de cómputo realizado por los dos servidores que intercambian conjuntos de cambios

Los gráficos típicos serán estrechos con pocas pistas paralelas como las anteriores. Por lo general, solo habrá un puñado de nodos hoja (los llamamos cabezas en Mercurial) como ey por yencima. Finalmente, cuando se usa un servidor central, el cliente a menudo tendrá un par de conjuntos de cambios que no están en el servidor, mientras que el servidor puede tener más de 100 conjuntos de cambios nuevos para los clientes, dependiendo de quién hace mucho tiempo que el cliente se retiró del servidor por última vez . Se prefiere una solución asimétrica : un servidor centralizado debería hacer pocos cálculos en comparación con sus clientes.

En este contexto, los nodos del gráfico tienen algún tipo de identificador único (un hash o suma de comprobación), ¿verdad? Por lo tanto, no necesita hacer ningún tipo de prueba de isomorfismo de subgrafo, solo necesita una lista de los nodos que difieren entre sus dos versiones, y los bordes no son realmente útiles para este paso. Mi documento SIGCOMM 2011 " ¿Cuál es la diferencia? Conciliación eficiente de conjuntos sin contexto previo"(con Goodrich, Uyeda y Varghese) considera exactamente este problema: resulta que puede determinar las identidades de los nodos que están en poder de uno pero no de los dos servidores de comunicación, utilizando una cantidad de comunicación que es proporcional solamente a la cantidad de nodos modificados y utilizando solo un solo viaje de ida y vuelta Una vez que tenga esa información, es fácil extraer los cambios en un segundo viaje de ida y vuelta, nuevamente con una comunicación óptima.

En la solución que implementamos para Mercurial, otra preocupación era la asimetría: la carga del servidor debería minimizarse tanto para el ancho de banda saliente como para el tiempo de CPU, a costa de la carga del cliente.

Suena como un proceso de dos pasos para mí.

1. preguntar a todos los clientes si tienen compromisos donde el padre es c
2. si es así, encuentre todos los hijos de c

La tarea de 1. Creo que se procesa principalmente en el lado del cliente, y todo el cliente necesita el hash de confirmación en la red.