matching a pair of DAGs, specifically a pair of monotone revision graphs A "comparison" is: "I have rev XXX, do you also have it?" After every comparison: * each side marks as shared all revs that it has that are ancestors (inclusive) of a known-shared rev * each side marks for send all revs that it has that are descendants (inclusive) of a known-unshared rev 1) compare heads Generally, an individual dev won't be active on all branches. So, the client will still have many heads that were fetched from the server. (maybe note that these are heads, so any descendants the other side has can be immediately marked for send) 2) compare roots (maybe) If it is assumed that each history has several heads, then any common roots would have likely been eliminated in (1). So check any remaining roots before going random, as these are likely to not be shared. 3) compare random revisions until all is known Or maybe try to split the revision graph into N+1 equal chunks, where N is the number of revs checked at once (checking several at once due to round-trip latency). Should be about O(log n), but significantly better in the common case. Only ask about revs that are in your sync set, but reply for revs you have regardless of whether they're in the sync set. This would avoid the problem where, say, pushing a new feature branch with a glob that *doesn't* include the base branch will re-send large portions of the base branch.