<p>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 "<a href="http://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf" rel="nofollow">What's the difference? Efficient set reconciliation without prior context</a>" (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.</p>

CC BY-SA 3.0
2011-10-26T09:20:37.183Z
Uh, this sounds interesting! You're right that a direct comparison of the changeset IDs (yes,they're hash values) will work. We've just always tries to use the graph structure too: if we both know X, then I also know that you know all ancestors of X. That seems like important information, but maybe it isn't. I'll read your paper now, thanks for the pointer!
Martin Geisler
CC BY-SA 3.0
2011-10-26T20:05:50.773Z
@David: A precision (I am one of the author of the algorithm currently used by Mercurial). We actually care about the set of "common" nodes, no need to know the value of the missing node.
tonfa
CC BY-SA 3.0
2011-10-27T00:20:52.603Z
If you know what's different, then you also know what's in common: it's everything you have a copy of that's not part of the difference. But the difference should typically be relatively small even when the common part is large, so communicating only an amount of data proportional to the difference is better than communicating the whole history DAG or the common part.
David Eppstein
CC BY-SA 3.0
2011-10-28T07:48:02.900Z
@David: because of the ancestor relationship, we actually compute the heads (leaf nodes) of the common region. So that is still a small amount of data, even if there is a huge shared history.
Martin Geisler
CC BY-SA 3.0
2011-10-28T22:11:40.753Z
I updated my answer to include also the number of round trips used (which turns out to be very small).
David Eppstein
CC BY-SA 3.0
2011-10-22T15:58:30.387Z
2011-10-28T22:09:35.810Z
2011-10-28T22:09:35.810Z
David Eppstein
<p>In the solution we implemented for Mercurial, another concern was asymmetry: the server's load should be minimized for both outgoing bandwidth and CPU time, at the cost of the client's load.</p>

CC BY-SA 3.0
2011-10-26T10:31:03.400Z
Thanks, I've updated the question a little to note this.
Martin Geisler
CC BY-SA 3.0
2011-10-26T09:32:50.420Z
2011-10-26T09:32:50.420Z
Peter Arrenbrecht
<p>Sounds like a two step process to me. </p>

<ol>
<li>ask all clients if they have commits where the parent is c</li>
<li>if so, find all childs of c</li>
</ol>

<p>The task of 1. I think is mainly processed on the client side, and all the client need the the commit hash over the net.</p>

CC BY-SA 3.0
2011-10-18T11:12:06.613Z
What scenario are you describing? The case where I made `x` and `y` and need to pull `e` and `d` from the server? The inital problem there is that I (as a client) don't know the "branch point" `c`.
Martin Geisler
CC BY-SA 3.0
2011-10-18T10:35:42.193Z
2011-10-18T10:35:42.193Z
Ron
<p>In <a href="http://en.wikipedia.org/wiki/Distributed_revision_control" rel="nofollow">distributed version control</a> systems (such a <a href="http://mercurial.selenic.com/" rel="nofollow">Mercurial</a> and <a href="http://git-scm.com/" rel="nofollow">Git</a>) 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.</p>

<p>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 <code>a</code> to <code>e</code> were made one after each other:</p>

<pre><code>a --- b --- c --- d --- e
</code></pre>

<p>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 <code>a</code> to <code>c</code> and made <code>x</code> and <code>y</code> based on <code>c</code>:</p>

<pre><code>a --- b --- c --- x --- y
</code></pre>

<p>In Mercurial, I would do <code>hg pull</code> and download <code>d</code> and <code>e</code>:</p>

<pre><code>a --- b --- c --- x --- y
              \
                d --- e
</code></pre>

<p>The goal is to identify <code>d</code> and <code>e</code> efficiently when the graph has many (say, more than 100,000) nodes. Efficiency concerns both</p>

<ul>
<li><strong>network complexity:</strong> the number of bytes transferred and the number of network round-trips needed</li>
<li><strong>time complexity:</strong> the amount of computation done by the two servers that exchange changesets</li>
</ul>

<p>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 <code>e</code> and <code>y</code> 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 <em>asymmetric solution</em> is preferred: a centralized server should do little computation in comparison to its clients.</p>

CC BY-SA 3.0
2012-01-07T10:49:22.007Z
The discussion has continued a little [on Google Plus](https://plus.google.com/108957994038017966408/posts/G4DqYzZCiRF).
Martin Geisler
<cc.complexity-theory><dc.distributed-comp><directed-acyclic-graph>
Efficient DAG comparison over a network
Martin Geisler
# Efficient DAG comparison over a network

(Asked by: username_0 on 2011-10-18)

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.

**Tags:** cc.complexity-theory, dc.distributed-comp, directed-acyclic-graph
> **Comments:**
> **username_0**: The discussion has continued a little [on Google Plus](https://plus.google.com/108957994038017966408/posts/G4DqYzZCiRF).  

---

## 3 answers

### Answer by username_1 on 2011-10-22. Score: 13

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](http://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf)" (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.

> **Comments:**
> **username_0**: Uh, this sounds interesting! You're right that a direct comparison of the changeset IDs (yes,they're hash values) will work. We've just always tries to use the graph structure too: if we both know X, then I also know that you know all ancestors of X. That seems like important information, but maybe it isn't. I'll read your paper now, thanks for the pointer!  
> **username_2**: @David: A precision (I am one of the author of the algorithm currently used by Mercurial). We actually care about the set of "common" nodes, no need to know the value of the missing node.  
> **username_1**: If you know what's different, then you also know what's in common: it's everything you have a copy of that's not part of the difference. But the difference should typically be relatively small even when the common part is large, so communicating only an amount of data proportional to the difference is better than communicating the whole history DAG or the common part.  
> **username_0**: @David: because of the ancestor relationship, we actually compute the heads (leaf nodes) of the common region. So that is still a small amount of data, even if there is a huge shared history.  
> **username_1**: I updated my answer to include also the number of round trips used (which turns out to be very small).  

---

### Answer by username_3 on 2011-10-26. Score: 3

In the solution we implemented for Mercurial, another concern was asymmetry: the server's load should be minimized for both outgoing bandwidth and CPU time, at the cost of the client's load.

> **Comments:**
> **username_0**: Thanks, I've updated the question a little to note this.  

---

### Answer by username_4 on 2011-10-18. Score: 0

Sounds like a two step process to me.

1. ask all clients if they have commits where the parent is c
2. if so, find all childs of c

The task of 1. I think is mainly processed on the client side, and all the client need the the commit hash over the net.

> **Comments:**
> **username_0**: What scenario are you describing? The case where I made `x` and `y` and need to pull `e` and `d` from the server? The inital problem there is that I (as a client) don't know the "branch point" `c`.  

---

