CROWD: New CRDT replacer

[nin-jin]

Hi, I'm working on CROWD Stores which is like CRDT, but have some key differences:

• CRDT has stronger guarantees for events commutativity. This gives a strong restriction on deleting old data. CROWD slightly weakens the guarantees (deltas from one peer shouldn't reorder), which gives more compact data representation without garbage collection and compactification.
• Some CROWD storages is accidentally dCRDT too.
• Stored CROWD State can be reinterpredeted by different CROWD Storages. Different CROWD Storages may be cross merged. CRDT structures are incompatible in general.

More info.

What do you think about this way?

@ept @gritzko @pgte @amark @dmonad @ai @marijnh @josephg

[josephg]

I'm sort of confused by CROWD, and I have been since I saw it mentioned. It just sounds like a specialization of CRDTs (or a particular implementation), rather than a new thing. I can't tell if I'm missing something or what.

• Some CRDTs (particularly state CRDTs) already don't store any history and don't need history to function.
• I'm not sure what to make of this "CROWD state can be reinterpretted by different storages" claim. What does that mean? Does that mean the same data can be interpretted by different implementations? If so that seems like a property of the implementation, not a property of the algorithm. I could make diamond-types compatible with automerge or yjs's data; but that doesn't change anything about the CRDT semantics of RGA or YATA.

[dmonad]

The phrasing is indeed a bit unclear. However, I can confirm that CRDT algorithms usually expect a reliable connection. A UDP connection is not sufficient as it does not guarantee that all messages are delivered.

[ept]

See the original CRDT paper, theorem 2.2 on page 8. The Wikipedia page is a bit sloppy.

[nin-jin]

Ok, thank you. About op-based we can read:

We assume an underlying reliable causally-ordered broadcast communication protocol,
i.e., one that delivers every message to every recipient exactly once and in an order consistent
with happened-before. Such protocols are a standard feature of distributed systems; they
do not require consensus and they deliver to all correct processes as long as any network
partition eventually recovers (as we assumed earlier).

But there is no same limitation for state-based. In other words:

• CmRDT requires partial-order delivery guarantee (all events from same source must be applied in the same order on all replicas).
• CvRDT requires no order delivery guarantee (all events can be applied in any order on any replica).
• OT requires full order delivery guarantee (all event must applied on all replicas in the same order).

[josephg]

Yes thats right. Many state based CRDTs do not need an in-order delivery guarantee for correctness. Eg we can define a state based CRDT which stores the max of a set of values. When a new value arrives, we define the subsequent value as value = MAX(current_value, new_value) If two new values arrive - 5 and 7, it doesn't matter if we process them in the order of 5, 7 or 7, 5. The values are commutative.

We don't need to store any history for this CRDT to function correctly. Is CROWD different from this?

[nin-jin]

In this meaning, CROWD is a CmRDT where only one "apply delta" operation is defined.

[nin-jin]

Hey guys, I've coming with good news.

I have reworked the CROWD. Now it's completely new algorithm, which can be classified as Delta State-based CRDT.

New CROWD Doc is special directed graph, with virtual nodes, and storing all data inside the edges. This graph can represent registers, structs, ordered lists, ordered maps, text etc.

Every chunk(edge) is simple LWW-Register. It can be cryptographically signed to prevent forgery and encrypted to prevent unauthorized access. And we can merge deltas without resigning or decrypting.

There is no interleaving problem and parasitic changes. It doesn't produce an unreadable word. No GC is required. Deltas is compact and batched. Implementation is fast and very small.

I described it in more detail here. Tell me if you see any problems with this or any ideas.