Using Bloom filters to efficiently synchronise hash graphs
Published: 2 December 2020
Tags: math, git
How do you go about figuring out "the minimal set of commits that the two nodes need to send to each other in order to make their graphs the same" in git? Well, you could write a research paper on it like Martin Kleppmann and Heidi Howard did. In this extensive article, Martin discusses the scope of the problem, introduces the solution in the form of Bloom filters, describes the practical relevance, and goes into the details on why Bloom filters are a better fit than the current algorithm git uses.