How exactly are conflicting changes resolved between clones?

[mcalligator]

A collaborator on a project asked (in another channel):

'how do you achieve convergence when multiple (possibly conflicting) edits of the structured data come in different order in remote nodes?

'I am mostly interested in this statement from Concurrency topic in the docs "Transaction operations combine to realise the final convergent state of every clone" - how do these transactions "combine"?'

[gsvarovsky]

This question gets asked a lot! We need to get it into the FAQs or the docs on the website.

When a user is editing information in an app, it's immediately committed to the local clone and published to other clones. So, if more than one user edits information in the same domain, they could edit the same data at the same time. m-ld guarantees that both users will eventually see the same data. But how does it merge the edits, without conflicts?

Because the information in m-ld is actually a graph, the most basic behaviour is a 'graph merge'. Imagine that every JSON property entered by a user is an "edge", going from the JSON object itself, to the JSON value. All of the information in the domain is represented like this, so, the m-ld domain is actually a Set of graph edges.

In an update, the app might delete some edges and insert some others (this is why Updates have the structure they do). The algorithm for the 'graph merge' is published computer science – an SU-Set CRDT – but its effects are simple: inserting an edge wins over deleting the same edge; and otherwise the order doesn't matter and all changes are applied.

This strategy is simple, but it can give rise to some effects which an app has to deal with. For example, if one user changes a JSON property to "name": "Fred", and at the same time another changes it to "name": "Freddy", the final state in the domain is "name": ["Fred", "Freddy"] – two graph edges for the same JSON property.

At this point, it's natural to think this should be magically resolved. However, first of all, in many apps it would be good to show both values to the user; after all, this situation was caused by a human interaction, it makes sense to have another human interaction to resolve it.

Another option is for the app to have a sensible default in its presentation, like picking the highest value, without actually resolving the conflict in the domain. In that case one user might see that they have 'lost', and re-do their change, collapsing the two values back to one; but if not, it might be good to know later that a conflict happened and no-one dealt with it. In highly interactive apps these options give the users autonomy instead of letting the machine make all the decisions; that's why the default is not to resolve every "conflict".

Of course there are situations in which the machine can make a good, obvious decision, and it would simplify app development if the data were guaranteed to always conform to some data schema – like a certain field must only ever have one value. For this, m-ld has a way to extend the domain with constraints. We've shown that constraints can be used to implement quite sophisticated rules (including embedding other CRDTs). We're currently experimenting with improved ways to declare them using a schema language, and we'd welcome your input.

Finally, there are situations in which conflict resolution is not possible without some kind of coordination between clones. This is necessary for security, and for changes to the schema itself. Our active research into this will lead to the ability to integrate with – or supplant – other highly-coordinated information systems, like blockchains.

There's lots more we could talk about like text support (#35) and git-style branch & merge (#68). In the meantime what do you think?

[kroky]

This makes a lot of sense - leaving the resolution to the app when conflicts cannot be automatically resolved. When the app (user) decides which value is the correct one to stay (like Freddy for example), does it send another update to the clone which effectively changes the name edge from ["Fred", "Freddy"] back to Freddy?

Having text merge support out of the box in m-ld might mean even tighter integration with Tiki as we have been considering different approaches for years here but never really shipped with something stable.

[gsvarovsky]

does it send another update to the clone

Yes, exactly. In this case the app could explicitly delete the wrong prior value:

{
  "@delete": { "@id": "fred", "name": "Fred" }
}

or just remove any previous values with a wildcard and insert the right one:

{
  "@delete": { "@id": "fred", "name": "?" },
  "@insert": { "@id": "fred", "name": "Freddy" }
}

[gsvarovsky]

• PHP platform #100

😇