Sounds amazing. Why the extra round trip for 1B over 1M? Something to do with limits in how much data you can send in a single packet?
Discussion
In rsync the entire diff is sent in one round trip, but this can be massive if there are lots of gaps in the data. Negentropy employs a divide and conquer strategy where it recursively splits the ranges in half and fixes up subranges in batches. It’s more efficient and the communication rounds scales O(log n) which is why it’s increasing so slowly from 1 million to 1 billion.
The article explains this very well in more detail with visualizations and everything.