2

The internals of an add/remove set CRDT is monotonic, because we only ever add to the internal sets, so the internal state of the CRDT cannot ever go backwards in logical time.

However, the observed state of the CRDT is that we're adding and removing elements, so the observed state doesn't have to be monotonic.

If we chain these systems together and take actions based on the presense or non-presense of an element, it doesn't look very monotonic anymore. The final state will still converge eventually, but we may or may not see some elements for a while before it stabilizes. It's not unlikely that some side-effect happens because of that intermediate state, such as a user reading the state of the system and reacting before it converges.

What does it mean for a CRDT to be monotonic?

Filip Haglund
  • 13,919
  • 13
  • 64
  • 113

2 Answers2

2

Just to add a TL;DR on top of alekibango's awesome answer:

Monotonicity refers to the fact that once operations are observed and applied by a replica, the object's state will always take into consideration that operation.

Once an operation is applied, it will never be un-applied.

The observed non-monotonicity of (most) CRDT Sets does not invalidate the CRDT monotonic property.

CRDT Sets that support the remove operation are at its core two G-Sets:

  • One of the G-Sets is the set of elements that were added.
  • The other G-set is the set of elements that were removed.

The observed state is the set of added elements minus the set of removed elements. Although each of the internal sets is clearly monotonic, their difference can appear to be non-monotonic.

João Neto
  • 1,732
  • 17
  • 28
1

CRDT means Conflict-Free Replicated Data Type

This means (diverging) instances of CRDT might merge together (in whatever order and repetitions) to finally get into correct, consistent state.

Monotonicity might help with implementing this (see CALM -- Consistency as Logical Monotonicity). But it is not a requirement for your set instance.

Read those notes on crdt: https://github.com/pfrazee/crdt_notes

Some Examples of CRDT sets are:

  • G-set (grow only set, only adding items)
  • 2P-set (keeps tombstones, element can be inserted once only)
  • LWW-set uses timestamps for marking 'time' of adding/removing item, allows adding/removing an item multiple times. Concurrent add and remove is decided using bias.
  • OR-set - similar to lww set, but uses unique tags to be sure which element we are removing.
  • Optimized OR-Sets - can be able to be useable without having many tombstones around, see those if your sets are big (and have many changes).

some links to read more:

alekibango
  • 11
  • 1
  • 2