Ordering operations for generic replicated data types using version trees
Ordering operations for generic replicated data types using version trees
复制标题
使用版本树对通用复制数据类型进行排序操作
DOI：
10.1145/3517209.3524038
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Wolski, Rich
中科院分区：
文献类型：
--
作者：
Saquib, Nazmus;Krintz, Chandra;Wolski, Rich
数据复制有助于分布式环境中的可用性和恢复。然而，对多个副本的并发更新会导致数据的发散。无重复数据类型（CRDTs）是抽象数据类型，它提供了一种异步协调这种差异的原则性方法。我们提出了一个不同的角度对数据的分歧，我们对待数据的分歧asversionsof的数据。也就是说，我们不仅将其视为一个需要解决的问题，还将其视为一个提供跟踪数据版本控制和演变的方法的功能。版本控制信息在多种情况下都很有用，比如出处跟踪和系统调试。这样做使我们能够利用文献中的版本树等概念来实现持久化（版本化）数据结构。我们发现，CRDTs中使用的许多技术来订购元素可以从版本树，这比CRDTs早20多年。使用版本树来维护顺序并使用仅添加日志来存储，我们提出了一种方法来确保任意数据类型的收敛，同时维护与数据演变相关的信息。
Data replication facilitates availability and recovery in a distributed environment. However, concurrent updates to multiple replicas result in divergence of data. Conflict-Free Replicated Data Types (CRDTs) are abstract data types that provide a principled approach to asynchronously reconcile this divergence. We propose a different perspective on the divergence of data, whereby we treat data divergences asversionsof the data. That is, instead of treating it only as a problem that needs to be solved, we consider it also to be a feature that provides a way to track versioning and evolution of data. Versioning information is helpful in multiple scenarios, such as provenance tracking and system debugging. Doing so allows us to leverage concepts such as theversion treefound in the literature for persistent (versioned) data structures. We show that many techniques used in CRDTs to order elements can be derived from version trees, which predates CRDTs by more than 20 years. Using version trees for maintaining order and append-only logs for storage, we propose a method to ensure convergence of arbitrary data types, while maintaining information related to the evolution of data.
登录
查看更多内容
计算几何交集的高效算法（决策树、隐藏线去除、图形、复杂性）
DOI：
--
发表时间：
1985
期刊：
影响因子：
--
作者：
G. Swart
通讯作者：
G. Swart
影响因子：
5.3
作者：
Martin Kleppmann;Dominic P. Mulligan;Victor B. F. Gomes;A. Beresford
通讯作者：
A. Beresford
应用随机访问堆栈
影响因子：
0.5
作者：
E. Myers
通讯作者：
E. Myers
无冲突复制数据类型 (CRDT)
DOI：
--
发表时间：
2018
期刊：
Encyclopedia of Big Data Technologies
影响因子：
--
作者：
Nuno M. Preguiça;Carlos Baquero;M. Shapiro
通讯作者：
M. Shapiro
DOI：
--
发表时间：
2019
期刊：
IFIP International Conference on Distributed Applications and Interoperable Systems
影响因子：
--
作者：
Kevin De Porre;Florian Myter;C. Troyer;Christophe Scholliers;W. Meuter;E. G. Boix
通讯作者：
E. G. Boix