Append-Only Ropes

An observation on binary antimonotone graphs outside the context of log verification.

Suppose you want to build a version control system like git. You have a file that evolves over time, and you want to be able to access it at arbitrary points in its evolution. The trivial solution is to store a full copy at each timestep. This is however very inefficient. An alternative is to only store the changes (deltas) between the versions. The very first version is stored as the delta to the empty file.

While this helps with storage needs, there's a different problem now: Reconstructing a file now takes time linear in its time point. To solve this, could introduce caches at regular intervals that store the file at that particular point. Binary antimonotone graphs offer a different solution.

At each point in time, we store both the delta to the previous state, and the delta to the predecessor in the above graph. This ensures that for each node, we can reconstruct the state by applying only a logarithmic number of deltas. Another cool feature: We can construct the delta between any two nodes by combining the deltas on the shortest path between them - taking time logarithmic in the difference of the time points.

Viewn abstractly, restoring a state corresponds to quickly computing a bunch of monoidical operations, and computing a delta between two arbitrary points corresponds to subtraction in an additive group). A different, less mathematical viewpoint can regard this example as a specific instance of an event sourcing architecture.

While this is kinda nice, it's fairly unexciting if you already know about ropes. Ropes can do the same, but also handle deletions and insertions at arbitrary points, whereas the binary antimonotone graphs are append-only. But this restricted scope comes with some advantages.

First, ropes need rebalancing logic, an additional source of complexity. The inner nodes change over time, which means updating a bunch of state even though it lies in the past. To fix this, you could take the general concept of a rope, but disallow all operations other than appending at the end. You could then build the rope out of perfect binary trees. But suppose we had such a rope of eight entries (forming a tree of height four). A ninth entry would have an edge to the root of that tree. When adding the tenth entry though, that edge would need to be deleted, and instead nine and ten would get a common ancestor, and that one would link to the root. This would continue as more nodes are added, adding the 16'th node would require restructuring four nodes (since there would be that many complete binary trees before adding it). Overall, the complexity of the append operation is O(log(n)). Interestingly enough, this O(log(n)) append is more or less exactly what #hypercore does.

The binary antimonotone graph however has O(1) append, while still providing the same quick computations over monoid and group data as a general rope. In that sense, it seems fitting to call an (optimal) binary antimonotone graph a (ternary) append-only rope.

(Yes, I am aware that the version control example is unrealistic because compression is a thing.)

And a less satisfying solution, that still keeps good bounds and that can use off-the-shelf collections: Keep a max-heap current of currently used identifiers, and a min-heap freed. If you want a new id, use the minimum of the smallest id in freed and the the successor of the largest element in current. When using an id from freed, remove it from freed, when using any id, add it to current, when stopping usage of an id, move it from current to freed.