Moving elements in list CRDTs
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Kleppmann, Martin https://orcid.org/0000-0001-7252-6958
Abstract
Conflict-free Replicated Data Types (CRDTs) for lists allow multiple users to concurrently insert and delete elements in a shared list object. However, existing algorithms behave poorly when users concurrently move list elements to a new position (i.e. reorder the elements in the list). We demonstrate the need for such a move operation, and describe an algorithm that extends a list CRDT with an explicit move operation. Our algorithm can be used in conjunction with any existing list CRDT algorithm. In addition to moving a single list element, we also discuss the open problem of moving ranges of elements.
Description
Keywords
46 Information and Computing Sciences, 4904 Pure Mathematics, 49 Mathematical Sciences
Journal Title
Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data
Conference Name
EuroSys '20: Fifteenth EuroSys Conference 2020
Journal ISSN
Volume Title
Publisher
ACM
Publisher DOI
Sponsorship
Isaac Newton Trust (19.08(m))
Leverhulme Trust Early Career Fellowship
Isaac Newton Trust