algorithm - 登录 CRDT : interleaving of data on concurrent edits to the same spot?

Question

我想实现 Logoot对于最终收敛的 P2P 文本编辑，我遇到了一些问题。

我对 Logoot 的理解是，对象(原论文中的文本行，但可以是字符或单词)之间的间隔可以无限分割，因为标识符是无限的。这意味着对象的位置不是像 WOOT 中那样由其邻居确定(这需要墓碑)，而是由沿着字符串长度的固定数字点确定。与唯一的站点标识符相结合，这也为我们提供了一个整体秩序，并实现了最终的融合。

但是...当对同一位置进行并发编辑时，这不会导致问题吗？如果两个断开连接的客户端开始在相同的光标位置写新句子然后合并，他们的句子很可能会交错。

下面是我正在谈论的白板示例:

可以看到，B站和C站都是按照Logoot的规则划分“I”和“conquered”的区间，给我们在(20,A)和(25,A)位置之间的随机点).但是没有什么相对于彼此排列这些点，导致它们在合并时混合。同时，基于邻居的算法可以解决这个问题，因为保留了每个对象的因果关系链。

上面是一个小例子，但在更一般的情况下，想象一下如果两个用户想要在两个现有句子之间插入一个不同的句子。如果其中一个用户碰巧不在线，他们不应该回来乱码乱码!显然，为了保持意图，一个句子应该跟在另一个句子之后。

我在阅读这篇论文时是否遗漏了什么，或者这是 Logoot 固有的缺点？

(另外，为什么有一个记录的时钟值在算法中似乎未使用？该论文甚至指出，每个对象的标识符在没有时钟的情况下必然是唯一的。)

Answer 1

你是对的，这是 Logoot 和 LSEQ 中的真正异常。是否构成故意侵权取决于您对故意的定义是什么。对定义的扩展要求连续序列保持连续，除非它们被随意的后续操作分开，这在直觉上是有意义的。

时钟是不必要的。很可能作者使用 (site, clock) pair 或 Lamport timestamp 作为他们的 UUIDs 不符合惯例。一个站点永远不会创建两个相同的位置，因此永远不需要比较时钟。 (假设消息是按顺序从站点接收的，这对于 Logoot/LSEQ 的其他方面也是必需的。)