View in EDS

Specification and space complexity of collaborative text editing.

Saved in:
Bibliographic Details
Title: Specification and space complexity of collaborative text editing.
Authors: Attiya, Hagit1 (AUTHOR) hagit@cs.technion.ac.il, Burckhardt, Sebastian2 (AUTHOR), Gotsman, Alexey3 (AUTHOR), Morrison, Adam4 (AUTHOR), Yang, Hongseok5 (AUTHOR), Zawirski, Marek6 (AUTHOR)
Source: Theoretical Computer Science. Feb2021, Vol. 855, p141-160. 20p.
Subjects: Technical specifications, Editing, Metadata, Space, Suretyship & guaranty
Abstract: Collaborative text editing systems allow users to concurrently edit a shared document, inserting and deleting elements (e.g., characters or lines). There are a number of protocols for collaborative text editing, but so far there has been no abstract, high-level specification of their desired behavior, which is decoupled from their actual implementation. Several of these protocols have been shown not to satisfy even basic expectations. This paper provides a precise specification of a replicated abstract list object, which models the core functionality of replicated systems for collaborative text editing. We define a strong list specification, which we prove is implemented by an existing protocol, as well as a weak list specification, which admits additional protocol behaviors. A major factor determining the efficiency and practical feasibility of a collaborative text editing protocol is the space overhead of the metadata that the protocol must maintain to ensure correctness. We show that for a large class of list protocols, implementing either the strong or the weak list specification requires a metadata overhead that is at least linear in the number of elements deleted from the list. The class of protocols to which this lower bound applies includes all list protocols that we are aware of, in particular CRDT and OT protocols, and we show that one of these protocols almost matches the bound. The result holds for peer-to-peer protocols, even if the network guarantees causal atomic broadcast. The result also holds for the metadata cost at the clients in client/server protocols. 1 [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Collaborative text editing systems allow users to concurrently edit a shared document, inserting and deleting elements (e.g., characters or lines). There are a number of protocols for collaborative text editing, but so far there has been no abstract, high-level specification of their desired behavior, which is decoupled from their actual implementation. Several of these protocols have been shown not to satisfy even basic expectations. This paper provides a precise specification of a replicated abstract list object, which models the core functionality of replicated systems for collaborative text editing. We define a strong list specification, which we prove is implemented by an existing protocol, as well as a weak list specification, which admits additional protocol behaviors. A major factor determining the efficiency and practical feasibility of a collaborative text editing protocol is the space overhead of the metadata that the protocol must maintain to ensure correctness. We show that for a large class of list protocols, implementing either the strong or the weak list specification requires a metadata overhead that is at least linear in the number of elements deleted from the list. The class of protocols to which this lower bound applies includes all list protocols that we are aware of, in particular CRDT and OT protocols, and we show that one of these protocols almost matches the bound. The result holds for peer-to-peer protocols, even if the network guarantees causal atomic broadcast. The result also holds for the metadata cost at the clients in client/server protocols. 1 [ABSTRACT FROM AUTHOR]
ISSN:03043975
DOI:10.1016/j.tcs.2020.11.046