按年被提到
20072012 · 1 次2026
系统、数据库与网络›分布式数据与 CRDT·arXiv:0710.1784 · cs.DC

Designing a commutative replicated data type

Marc Shapiro, Nuno Preguiça · 2007
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2012-03-02 · 最近 2019-03-04
2不同的人
2活跃月份
2讨论串
33被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Commuting operations greatly simplify consistency in distributed systems. This paper focuses on designing for commutativity, a topic neglected previously. We show that the replicas of \emph{any} data type for which concurrent operations commute converges to a correct value, under some simple and standard assumptions. We also show that such a data type supports transactions with very low cost. We identify a number of approaches and techniques to ensure commutativity. We re-use some existing ideas (non-destructive updates coupled with invariant identification), but propose a much more efficient implementation. Furthermore, we propose a new technique, background consensus. We illustrate these ideas with a shared edit buffer data type.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论pbailis · 2012-03

“Right; you need some notion of a total order or commutativity in your update functions. f(A,B) = f(B,A). "Last writer wins" is one example of commutativity, but that isn't often what you want. What you want is something like a "Commutative Replicated Data Type" [1], where you define a commutative function specific to your application. Libraries like Stat…”

How Eventual is Eventual Consistency? 原评论 ↗
评论chalst · 2019-03

“This article has led me to Shapiro & Preguiça (2007) https://arxiv.org/pdf/0710.1784.pdf The whole idea that commutativity gives you a better-behaved transition to consistency reminds me of how the theory of patches gives DARCS/Pijul better handling of branches than Git. Cf. Mimram & Giusto (2013) https://arxiv.org/pdf/1311.3903.pdf”

Serverless collaborative editor using CRDT原评论 ↗