The Problem of Discovery in Version Control Systems

Laurent Bulteau (1) , Pierre-Yves David (2) , Florian Horn (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Octobus
3 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale

Version Control Systems, used by developers to keep track of the evolution of their code, model repositories as Merkle graphs of revisions. In order to synchronize efficiently between different instances of a repository, they need to determine the common knowledge that they share. This process is called discovery. In this paper, we provide theoretical definitions for the problem of discovery and establish some universal upper and lower bounds on its communication complexity. We also present and analyze some algorithms that are used in extant VCSs, such as Mercurial and Git.

Domaines: Informatique [cs]

Laurent Bulteau, Pierre-Yves David, Florian Horn. The Problem of Discovery in Version Control Systems. 2022. ⟨hal-03830513v1⟩