In distributed version control systems (such a Mercurial and Git) there is a need to efficiently compare directed acyclic graphs (DAGs). I'm a Mercurial developer, and we would be very interested in hearing about theoretical work that discuss the time- and network-complexity of comparing two DAGs.
The DAGs in question are formed by the revisions recorded. Revisions are uniquely identified by a hash value. Each revisions depend on zero (initial commit), one (normal commit) or more (merge commit) of the previous revisions. Here is an example where revisions a
to e
were made one after each other:
a --- b --- c --- d --- e
The graph comparison comes into the picture when someone has only part of the history and wants to retrieve the missing part. Imagine I had a
to c
and made x
and y
based on c
:
a --- b --- c --- x --- y
In Mercurial, I would do hg pull
and download d
and e
:
a --- b --- c --- x --- y
\
d --- e
The goal is to identify d
and e
efficiently when the graph has many (say, more than 100,000) nodes. Efficiency concerns both
- network complexity: the number of bytes transferred and the number of network round-trips needed
- time complexity: the amount of computation done by the two servers that exchange changesets
Typical graphs will be narrow with few parallel tracks like above. There will also typically be only a handful of leaf nodes (we call them heads in Mercurial) like e
and y
above. Finally, when a central server is used, the client will often have a couple of changesets that are not on the server, while the server can have 100+ new changesets for the clients, depending on who long ago the client last pulled from the server. An asymmetric solution is preferred: a centralized server should do little computation in comparison to its clients.