Different conflict behavior for derived nodes

[seefeldb]

[This requires some bigger changes in the client as well as storage, so mostly noting for future discussion]

When multiple tabs are open and each derives the same values that are then synced, we're going to see a lot more conflicts, since they all derive the same values, often triggered by the same underlying change. There's of course an optimization downstream to not sync those changes at all, but let's not rely on that alone. Instead we could support conflict semantics that match the idea of derived data:

Each change could specify what data and what version of the data the change is based on:

• Today's CAS behavior is effectively a change that depends on the previous value only
• A derived value is a change that depends on other data at specific versions

A transaction is allowed when

• The current value isn't based on any newer data than the proposed transaction depends on
• If the transaction depends on the to be changed document, then it must be based on the current version of the document

Note: A transaction might refer to a value it changes itself, so it'll have to express "current transaction" as version. TBD whether we should allow cycles (in principle a propagator network could that came to a stable point after several iterations could look like that, but maybe we want to record that differently).

For derive we need to base it on since, so it's comparable. Hence I wonder whether we should change that for self-referential changes as well, or keep cause as today. (We'd still want to store a causal chain, though interestingly atproto only does that for commits, capturing the before and after hashes)

[Gozala]

I'm not sure I fully understand all the nuances but here some notes that are worth considering

1. If two tabs are deriving data from the same input they I would expect them to arrive to the same derived data (producing same merkle-reference). If this is the case there should be no conflicts because if we have two concurrent A → B updates they both should succeed as long as state is B. In other words if state was A and we received A → B we will transition to state B, then if we receive another A → B transaction still succeeds and state remains B. This seems to suggest that our state derivation logic is either non deterministic and second update is A → C instead of A → B or there is some other concurrent change B → D that happens which is why second A → B fails.

• Either way, it seems that failure is expected or it would cause a tabs to override each other.

2. Current system has cause so that each entity can be updated concurrently with other entities. If we only relied on a single commit history denoted by since we would dramatically reduce amount of concurrency system can support and consequently I would expect more conflicts not less.
   • Perhaps thinking here is that if you're updating derived data based on outdated since we could simply disregard update ? We can actually do that already with cause we simply report it back. Furthermore transaction can claim that it expects commit to be a specific one (which corresponds to since) and if it is not the case it will be rejected, so in a way you can express what since you expect although bit indirectly.