Efficient DAG comparison over a network 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.
In this context, the graph nodes have some sort of unique identifier (a hash or checksum), right? So you don't need to do any kind of subgraph isomorphism testing, you just need a list of the nodes that differ between your two versions, and the edges aren't really useful at all for this step. My SIGCOMM 2011 paper "What's the difference? Efficient set reconciliation without prior context" (with Goodrich, Uyeda, and Varghese) considers exactly this problem: it turns out that you can determine the identities of the nodes that are held by one but not both of the two communicating servers, using an amount of communication that is proportional only to the number of changed nodes and using only a single round-trip. Once you have that information, it's easy to pull the changes themselves in a second round-trip, again with optimal communication.