Concurrent conflict resolutions

Question
1

Hi!

I wonder about the expected behavior for Pijul in situations where different authors resolve the same conflict in the same way. As far as I understand, resolving a conflict produces a change, so would concurrent conflict resolutions become a conflict again as soon as those authors exchange their changes, even if they resolve it in exactly the same way?

2 Likes
2

I think if you’re adding identical edges between lines you’ll be fine, while having conflicting “A before B” + “B before A” ones would be a problem.

1 Like
3

Hi! And welcome here! This is an excellent question! There are many things to say as an answer.

  • First, Pijul has an internal datastructure which generalises files. Patches always operate on that datastructure, which means that there is a mapping from that internal representation to actual files users can edit, and a mapping from changes in these files to patches on the internal representation.

    This means in particular that there are two levels to your question: one is on the internal representation, on which things are pretty much decided (see my second point), and the other one is on the UX, in which things can always be improved.

  • Now, the internal datastructure is a graph of chunks of bytes, and the only two operations people do when using Pijul is adding new vertices, and changing the labels of existing edges. There are multiple kinds of conflicts, but assuming the kind you’re talking about is when two authors add new content to the same part of a file. In that case, the conflict is solved by adding one empty vertex between their two new vertices. So, if two authors solve the conflict in the same way, they each add a new empty vertex, and since the order between these two vertices is not decided, Pijul calls that a conflict. Now, the way Pijul informs the user can vary: for example, Pijul could decide to never show conflicts between empty vertices, and keep the “conflict” forever. I’m not fully happy with the current options for how things are output or how diffs are made, I think they could be more customisable (since Pijul represents conflicts internally, outputting conflicts as comments in the file’s programming language is definitely possible, for example).

  • Now, you may ask: why do we want to add a new vertex, when adding just an edge between the conflict’s sides intuitively seems enough? There are a number of reasons: one is to try and minimise the number of different basic operations, in order to make proofs (and debugging!) easier. The other reason is related to inverting patches: the issue is that Pijul, like most distributed systems, is “append-only”: a patch deleting a vertex essentially marks the incoming edges to the vertex as deleted. However, the inverse of adding an edge is unclear, since one form of conflict is when incoming edges disagree on their label. Therefore, if we had an operation for adding edges, and used it to solve conflicts, “unsolving” the conflict would either create another conflict on the target of the edge, or else add a whole new layer of complexity.

    Finally, once an edge exists, its label can be changed by future patches, and hence the edge becomes hard to kill, since applying these other patches may reintroduce it (or at least create undefined behaviour).

Even though this sounds complicated, I want to add that unlike in Git, I don’t think it is necessary to understand how things work internally in order to work with Pijul. In all but a few cases (conflicts between conflict resolutions, or some forms of conflicts on file names), you don’t need to understand any of the internals in order to mentally predict Pijul’s behaviour.

Here are other facts and puzzles related to conflicts:

  • As @fyr mentioned, solving the conflict in different ways makes the graph cyclic, which Pijul does detect. The current algorithm to solve these situations in Pijul is to delete both sides, and replace them with a properly ordered version.
  • Similarly, what should happen if we have two directories a and b, and Alice moves a into b (as b/a), while Bob moves b into a concurrently (into a/b)?
2 Likes
4

Hi!

Thanks a lot for a detailed answer!

I was wondering about that mostly because I’m taking inspirations from Pijul for a project I’m working on right now. It’s a decentralized publishing platform with automatic version control for publications, history preservation, async collaboration, and fair content reuse. No blockchain, hehehe :slight_smile: At the moment we also represent documents as sets of changes, similar to Pijul. But our approach doesn’t have to be generic, so we have better time choosing tradeoffs.

Anyways, thanks a lot for working on Pijul. I think it’s a great and very useful project. Hopefully eventually we get a sensible version control system that would be widespread. People used to think SVN wasn’t going anywhere, but then came Git. Maybe something similar will happen again one day :slight_smile:

5

Taking inspiration is quite ambitious in my opinion (there’s quite a bit of work to get it working efficiently), why not just use it instead?

6

There’re multiple reasons (both technical, and product-wise) why we can’t use Pijul directly. We don’t need a lot of what Pijul is doing, and at the same time Pijul is not doing a lot of what we need. Basically the goals of the two projects are too different.