Re: pack negotiation algorithm between 2 share-nothing repos

Duy Nguyen [off-list ref] writes:

I know this is a corner case, but because it has a valid use case,
maybe we should do something about it. Immediate reaction is to add an
option to send no "have"s. But maybe you guys have better ideas.

This and similar corner cases were discussed in very early days of
Git.

One interesting idea floated back then but was not pursued was to
dig and send have's sparsely and then back up.  Instead of digging
and sending _all_ commits in a contiguous history, after sending the
tip, you skip the commits from the history before sending the next
one, and progressively make the skipping larger (e.g. Fibonacci, or
exponential).  You need to remember what you sent and for each of
what you sent its topologically-oldest descendant you sent earlier
that you heard the other side does not have.

Then, when you get an Ack, you know a stretch of history between a
commit that is known to be common (i.e. the one you heard an Ack
just now) and its descendant that is known only to you (i.e. the
topologically-oldest one you remember that you did send and they
didn't say is common).  At that point, you and the other end can
bisect that range.