Document Open Access Logo

A Generic Undo Support for State-Based CRDTs

Authors Weihai Yu, Victorien Elvinger, Claudia-Lavinia Ignat

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.14.pdf
  • Filesize: 477 kB
  • 17 pages

Document Identifiers

Author Details

Weihai Yu
  • University of Tromsø - The Arctic University of Norway, Norway
Victorien Elvinger
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000, Nancy, France
Claudia-Lavinia Ignat
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000, Nancy, France

Funding

The research was mostly carried out during Yu’s sabbatical stay at Inria, LORIA, financed by University of Tromsø - The Arctic University of Norway.

Acknowledgements

The authors thank the members of the COAST team at Inria, LORIA, in particular Matthieu Nicolas and Gérald Oster, for interesting discussions.

Cite As Get BibTex

Weihai Yu, Victorien Elvinger, and Claudia-Lavinia Ignat. A Generic Undo Support for State-Based CRDTs. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.OPODIS.2019.14

Abstract

CRDTs (Conflict-free Replicated Data Types) have properties desirable for large-scale distributed systems with variable network latency or transient partitions. With CRDT, data are always available for local updates and data states converge when the replicas have incorporated the same updates. Undo is useful for correcting human mistakes and for restoring system-wide invariant violated due to long delays or network partitions.
There is currently no generally applicable undo support for CRDTs. There are at least two reasons for this. First, there is currently no abstraction that we can practically use to capture the relations between undo and normal operations with respect to concurrency and causality. Second, using inverse operations as the existing partial solutions, the CRDT designer has to hard-code certain rules and design a new CRDT for almost every operation that needs undo support.
In this paper, we present an approach to generic support of undo for CRDTs. The approach consists of two major parts. We first work out an abstraction that captures the semantics of concurrent undo and redo operations through equivalence classes. The abstraction is a natural extension of undo and redo in sequential applications and is straightforward to implement in practice. By using this abstraction, we then device a mechanism to augment existing CRDTs. The mechanism provides an "out of the box" support for undo without the involvement of the CRDT designers. We also present a practical application of the approach in collaborative editing.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Computing methodologies → Concurrent algorithms
  • Information systems → Data replication tools
  • Human-centered computing → Synchronous editors
  • Human-centered computing → Asynchronous editors
Keywords
  • Data replication
  • eventual consistency
  • state-based CRDT
  • delta-state CRDT
  • concurrent undo

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Gregory D Abowd and Alan J Dix. Giving undo attention. Interacting with Computers, 4(3):317-342, 1992. Google Scholar
  2. Deepthi Devaki Akkoorath, Alejandro Z. Tomsic, Manuel Bravo, Zhongmiao Li, Tyler Crain, Annette Bieniusa, Nuno M. Preguiça, and Marc Shapiro. Cure: Strong Semantics Meets High Availability and Low Latency. In 36th IEEE International Conference on Distributed Computing Systems, (ICDCS), pages 405-414, 2016. Google Scholar
  3. Paulo Sérgio Almeida, Ali Shoker, and Carlos Baquero. Delta state replicated data types. J. Parallel Distrib. Comput., 111:162-173, 2018. Google Scholar
  4. Luc André, Stéphane Martin, Gérald Oster, and Claudia-Lavinia Ignat. Supporting adaptable granularity of changes for massive-scale collaborative editing. In CollaborateCom, 2013. Google Scholar
  5. Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker. Making Operation-Based CRDTs Operation-Based. In 14th IFIP WG 6.1 International Conference Distributed Applications and Interoperable Systems (DAIS), volume 8460 of Lecture Notes in Computer Science, pages 126-140. Springer, 2014. Google Scholar
  6. Annette Bieniusa, Marek Zawirski, Nuno M. Preguiça, Marc Shapiro, Carlos Baquero, Valter Balegas, and Sérgio Duarte. A optimized conflict-free replicated set. Rapport de recherche, 8083, October 2012. Google Scholar
  7. Eric A. Brewer. CAP twelve years later: How the "rules" have changed. IEEE Computer, 45(2):23-29, 2012. Google Scholar
  8. Russell Brown, Sean Cribbs, Christopher Meiklejohn, and Sam Elliott. Riak DT map: a composable, convergent replicated dictionary. In The First Workshop on the Principles and Practice of Eventual Consistency, pages 1-1, 2014. Google Scholar
  9. Aaron G. Cass and Chris S. T. Fernandes. Using Task Models for Cascading Selective Undo. In Karin Coninx, Kris Luyten, and Kevin A. Schneider, editors, Task Models and Diagrams for Users Interface Design, pages 186-201. Springer Berlin Heidelberg, 2007. Google Scholar
  10. Jean Ferrié, Nicolas Vidot, and Michèle Cart. Concurrent Undo Operations in Collaborative Environments Using Operational Transformation. In CoopIS/DOA/ODBASE (1), volume 3290 of Lecture Notes in Computer Science, pages 155-173. Springer, 2004. Google Scholar
  11. Armando Fox and Eric A. Brewer. Harvest, Yield and Scalable Tolerant Systems. In The Seventh Workshop on Hot Topics in Operating Systems, pages 174-178, 1999. Google Scholar
  12. Hector Garcia-Molina and Kenneth Salem. Sagas. In 1987 ACM SIGMOD International Conference on Management of Data, pages 249-259. ACM, 1987. Google Scholar
  13. Vijay K. Garg. Introduction to Lattice Theory with Computer Science Applications. Wiley, 2015. Google Scholar
  14. Seth Gilbert and Nancy Lynch. Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-tolerant Web Services. SIGACT News, 33(2):51-59, 2002. Google Scholar
  15. Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno M. Preguiça, and Rodrigo Rodrigues. Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 265-278, 2012. Google Scholar
  16. Christopher Meiklejohn and Peter Van Roy. Lasp: a language for distributed, coordination-free programming. In the 17th International Symposium on Principles and Practice of Declarative Programming, pages 184-195, 2015. Google Scholar
  17. Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine. Data consistency for P2P collaborative editing. In CSCW, pages 259-268. ACM, 2006. URL: http://dx.doi.org/10.1145/1180875.1180916.
  18. Douglas Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, Allen Stoughton, Bruce J. Walker, Evelyn Walton, Johanna M. Chow, David A. Edwards, Stephen Kiser, and Charles S. Kline. Detection of Mutual Inconsistency in Distributed Systems. IEEE Trans. Software Eng., 9(3):240-247, 1983. Google Scholar
  19. Nuno M. Preguiça, Marek Zawirski, Annette Bieniusa, Sérgio Duarte, Valter Balegas, Carlos Baquero, and Marc Shapiro. SwiftCloud: Fault-Tolerant Geo-Replication Integrated all the Way to the Client Machine. In 33rd IEEE International Symposium on Reliable Distributed Systems Workshops (SRDS Workshops 2014), pages 30-33, 2014. Google Scholar
  20. Nuno M. Preguiça, Joan Manuel Marquès, Marc Shapiro, and Mihai Letia. A Commutative Replicated Data Type for Cooperative Editing. In 29th IEEE International Conference on Distributed Computing Systems, (ICDCS), pages 395-403, 2009. Google Scholar
  21. Matthias Ressel and Rul Gunzenhäuser. Reducing the problems of group undo. In GROUP, pages 131-139. ACM, 1999. Google Scholar
  22. Bin Shao, Du Li, and Ning Gu. An algorithm for selective undo of any operation in collaborative applications. In GROUP, pages 131-140. ACM, 2010. Google Scholar
  23. Marc Shapiro, Nuno M. Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-Free Replicated Data Types. In 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, (SSS 2011), pages 386-400, 2011. Google Scholar
  24. Chengzheng Sun. Undo as concurrent inverse in group editors. ACM Trans. Comput.-Hum. Interact., 9(4):309-361, 2002. Google Scholar
  25. David Sun and Chengzheng Sun. Context-Based Operational Transformation in Distributed Collaborative Editing Systems. IEEE Trans. Parallel Distrib. Syst., 20(10):1454-1470, 2009. URL: http://dx.doi.org/10.1109/TPDS.2008.240.
  26. Stéphane Weiss, Pascal Urso, and Pascal Molli. Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks. In 29th IEEE International Conference on Distributed Computing Systems, (ICDCS), pages 404-412, 2009. Google Scholar
  27. Stéphane Weiss, Pascal Urso, and Pascal Molli. Logoot-Undo: Distributed Collaborative Editing System on P2P Networks. IEEE Trans. Parallel Distrib. Syst., 21(8):1162-1174, 2010. URL: http://dx.doi.org/10.1109/TPDS.2009.173.
  28. Weihai Yu. Supporting string-wise operations and selective undo for peer-to-peer group editing. In GROUP, pages 226-237. ACM, 2014. Google Scholar
  29. Weihai Yu, Luc André, and Claudia-Lavinia Ignat. A CRDT Supporting Selective Undo for Collaborative Text Editing. In 15th IFIP WG 6.1 International Conference Distributed Applications and Interoperable Systems (DAIS), volume 9038 of Lecture Notes in Computer Science, pages 193-206. Springer, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact