Эффективное сравнение DAG по сети

В распределенных системах контроля версий (таких как Mercurial и Git ) существует необходимость эффективного сравнения направленных ациклических графов (DAG). Я - разработчик Mercurial, и нам было бы очень интересно услышать о теоретической работе, в которой обсуждается сложность времени и сети при сравнении двух групп DAG.

Рассматриваемые группы обеспечения доступности баз данных формируются по зарегистрированным изменениям. Редакции однозначно идентифицируются хеш-значением. Каждая ревизия зависит от нуля (начальная фиксация), одной (нормальная фиксация) или более (фиксация слияния) предыдущих ревизий. Ниже приведен пример , где изменения aк eбыли сделаны один за другим:

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

Сравнение графиков входит в картину, когда кто-то имеет только часть истории и хочет извлечь недостающую часть. Представьте, что я должен aбыл cи сделал xи yна основе c:

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

В Mercurial я бы сделал hg pullи скачал dи e:

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

Цель состоит в том, чтобы идентифицировать dи eэффективно, когда граф имеет много (скажем, более 100 000) узлов. Эффективность касается как

• сложность сети: количество переданных байтов и количество необходимых сетевых обходов
• временная сложность: объем вычислений, выполненных двумя серверами, которые обмениваются наборами изменений

Типичные графики будут узкими с несколькими параллельными дорожками, как указано выше. Также обычно будет только несколько конечных узлов (мы называем их головами в Mercurial), как eи yвыше. Наконец, когда используется центральный сервер, у клиента часто будет несколько наборов изменений, которых нет на сервере, в то время как на сервере может быть более 100 новых наборов изменений для клиентов, в зависимости от того, кто давно клиент последний раз брал с сервера , Асимметричное решение является предпочтительным: централизованный сервер должен сделать небольшое вычисление по сравнению со своими клиентами.

В этом контексте узлы графа имеют своего рода уникальный идентификатор (хэш или контрольную сумму), верно? Таким образом, вам не нужно выполнять какие-либо тесты на изоморфизм подграфов, вам просто нужен список узлов, которые отличаются между вашими двумя версиями, а ребра на этом этапе вообще не нужны. Моя статья SIGCOMM 2011 "В чем разница? Эффективное согласование набора без предварительного контекста«(с Goodrich, Uyeda и Varghese) рассматривает именно эту проблему: оказывается, что вы можете определить идентификаторы узлов, которые удерживаются одним, но не обоими двумя взаимодействующими серверами, используя объем связи, который пропорционален только на количество измененных узлов и использование только одного приема-передачи. Как только у вас есть эта информация, легко получить сами изменения во втором и обратно, опять же с оптимальной связью.

В решении, которое мы внедрили для Mercurial, еще одной проблемой была асимметрия: нагрузка на сервер должна быть минимизирована как для исходящей полосы пропускания, так и для времени ЦП, за счет нагрузки на клиента.

Похоже, двухступенчатый процесс для меня.

1. спросите всех клиентов, есть ли у них коммиты, где родитель
2. если так, найдите всех детей

Задача 1. Я думаю, что в основном обрабатывается на стороне клиента, и все клиенты нуждаются в хеше коммитов по сети.