添加/删除集合CRDT是单调的吗？

Question

添加/删除集合CRDT的内部是单调的，因为我们只添加到内部集合，所以CRDT的内部状态在逻辑时间内永远不会倒退。

然而，CRDT的观察状态是我们正在添加和删除元素，因此观察到的状态不必是单调的。

如果我们将这些系统链接在一起，并根据元素的存在或不存在采取行动，那么它看起来就不再是单调的了。最终状态仍然会收敛，但在它稳定之前，我们可能会也可能看不到一些元素。由于中间状态而发生一些副作用并不是不可能，例如用户读取系统状态并在系统收敛之前做出反应。

CRDT是单调的是什么意思？

Answer 1

在alekibango令人惊叹的答案之上添加一个TL;DR：

单调性指的是，一旦副本观察到并应用了操作，对象的状态将始终考虑该操作。

一旦操作被应用，它将永远不会被取消应用。

观察到的(大多数) CRDT集的非单调性不会使CRDT的单调性失效。

支持remove运算的CRDT集是其核心的两个G集：

• 其中一个G-集合是添加的元素集合。
• 另一个G-集合是删除的元素集合。

观察到的状态是添加的元素集减去删除的元素集。尽管每个内部集合显然是单调的，但它们的差异可能看起来不是单调的。

Answer 2

CRDT表示无冲突复制数据类型

这意味着(分散的) CRDT实例可能会合并在一起(以任何顺序和重复)，最终进入正确、一致的状态。

单调性可能有助于实现这一点(参见CALM -- Consistency as Logical Monotonicity)。但这不是set实例的要求。

请在crdt上阅读这些注释：https://github.com/pfrazee/crdt_notes

CRDT集的一些示例如下：

• G-set (仅增长集合，仅添加项目)
• 2P- set (保留墓碑，元素只能插入一次)
• LWW-set使用时间戳标记添加/删除项目的时间，允许多次添加/删除项目。并发添加和删除是使用偏置来决定的。集合OR-集合-类似于lww集合，但使用唯一的标签来确定我们是哪个元素-集合OR- removing.
• Optimized -可以在没有太多墓碑的情况下使用，如果您的集合很大(并且有许多变化)，请查看这些。

阅读更多内容的一些链接：

• https://hal.inria.fr/inria-00609399v1/document
• https://github.com/CBaquero/delta-enabled-crdts
• https://doc.akka.io/docs/akka/2.5/distributed-data.html
• https://www.youtube.com/watch?v=ebWVLVhiaiY
• https://www.youtube.com/watch?v=veeWamWy8dk
• https://www.youtube.com/watch?v=xxjHC3yLDqw
• https://www.youtube.com/watch?v=PQzNW8uQ_Y4