Commit graphs in Version-Control Systems: incremental reachability and label discovery

Current distributed source version-control systems (such as Git and Mercurial), track the history of changes using an append-only directed acyclic graph, sometimes complemented by labels subsequently attached to commits.

We present a chain-based and a dichotomy-based framework, both leveraging incremental indices, to answer reachability queries in sub-linear time, and efficiently perform label synchronisation between users.

Our approaches perform competitively in practice upon evaluation on our newly released dataset of real-world graphs.