Re: "git-send-pack"

["H. Peter Anvin" <hpa@zytor.com>]

It seems to me that git always defines a DAG of objects, such that if 
you have a list of terminals (defined as objects not referenced by other 
objects), you can, given access to the same objects, figure out all 
intervening objects.

The tricky bit becomes finding the DAG both sides have in common with as 
little traffic as possible.

For producing minimum network traffic, I think something like this would 
work:

a) The sender sends a list of its terminals to the receiver.

b) The receiver sends a list of nodes it needs, plus a list of all its 
own meta-terminals, obtained by pruning its own DAG according to the 
terminals list of the sender.

c) This may have to be performed iteratively?  I need to sit down and 
work out the exact algorithm for all cases, including branch trees and 
multi-rooted DAGs.

d) Once the sender knows the subset of its own DAG available to the 
receiver, it can transmit either all objects that it has the sender does 
not, or all objects on the path to one or more specific objects (e.g. HEAD.)

	-hpa