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.