Consider two directed acyclic graphs where each node has a hash that depends on its value and its parent's hashes. Suppose you have a slow connection and one of

Consider two directed acyclic graphs where each node has a hash that depends on its value and its parent's hashes. Suppose you have a slow connection and one of the graphs is remote, how do you figure out as efficiently as possible which nodes both graphs have? The trick is to sample random nodes from the remote graph. If you get back a node that has the same hash as a node in your graph, you know that local and remote have all the same ancestors of the node too. Otherwise, you know that local doesn't have any of the children (on remote) of that node. Turns out that is basically what mercurial does [1]. [1] https://www.mercurial-scm.org/repo/hg/file/tip/mercurial/setdiscovery.py https://www.mercurial-scm.org/repo/hg/file/tip/mercurial/set...