HackerPapers

arXiv:0710.1784cs.DC

Designing a commutative replicated data type

Marc Shapiro, Nuno Preguiça

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.DCDistributed, Parallel, and Cluster Computing

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Mar 2012 to Mar 2019.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Serverless collaborative editor using CRDT 1 comment

    • 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.…

      chalstView on HNParent context

  2. How Eventual is Eventual Consistency? 1 comment

    • 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…

      pbailisView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.