1 Search Results for "Elvinger, Victorien"

Document
DOI: 10.4230/LIPIcs.OPODIS.2019.14
A Generic Undo Support for State-Based CRDTs

Authors: Weihai Yu, Victorien Elvinger, and Claudia-Lavinia Ignat

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{yu_et_al:LIPIcs.OPODIS.2019.14,
  author =	{Yu, Weihai and Elvinger, Victorien and Ignat, Claudia-Lavinia},
  title =	{{A Generic Undo Support for State-Based CRDTs}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.14},
  URN =		{urn:nbn:de:0030-drops-118009},
  doi =		{10.4230/LIPIcs.OPODIS.2019.14},
  annote =	{Keywords: Data replication, eventual consistency, state-based CRDT, delta-state CRDT, concurrent undo}
}
  • Refine by Author
  • 1 Elvinger, Victorien
  • 1 Ignat, Claudia-Lavinia
  • 1 Yu, Weihai

  • Refine by Classification
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Human-centered computing → Asynchronous editors
  • 1 Human-centered computing → Synchronous editors
  • 1 Information systems → Data replication tools
  • 1 Theory of computation → Distributed computing models

  • Refine by Keyword
  • 1 Data replication
  • 1 concurrent undo
  • 1 delta-state CRDT
  • 1 eventual consistency
  • 1 state-based CRDT

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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 Imprint Privacy Contact