Presenting Mercurial Discovery Algorithm at LAGOS 2023

Over its almost 20 year of existence, Mercurial has encountered many challenges and developed data-structures and algorithms to overcome them. As the feature-set and scale at which Mercurial is used grow, these challenge evolve and require deeper knowledge about the challenges we face, and iterative improvements to the existing solution.

Yet, this knowledge and algorithms tend to remain "hidden" within the Mercurial source code and community. To improve the situation, Octobus has been working with computer scientists. These researchers are happy to be provided with real-life challenges and algorithms, and in return can offer their expertise in formal analysis. This collaboration allows to document the existing knowledge accumulated by the Mercurial community and to offer a fresh perspective to further improve the existing solutions.

One of the visible results of this joint work is our contribution to the LAGOS 2023 Conference where our paper about The Problem of Discovery in Version Control Systems has been presented. It describes the concept of "changeset discovery" that takes place during each exchange (push or pull) between peers, where the local client queries the server to figure out which parts of the history are missing and need to be exchanged and which parts are common and do not need to be sent over the network. The article described the Mercurial approach to this problem and how it evolved over time. It compares it to what Git does and offers ideas on how to improve it further.