ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing Moulay Driss Mechaouia,∗,1, Abdessamad Imineb,2 a CSTL Lab, University of Mostaganem - Abdelhamid Ibn Badis, Mostaganem, Algeria

arXiv:2607.28101v1 [cs.DC] 30 Jul 2026

b Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

ARTICLE INFO

ABSTRACT

Keywords: Collaborative editing Sequence CRDT Identiﬁer allocation Stern–Brocot tree Scalable distributed systems Strong Eventual Consistency (SEC) Red–Black tree.

Modern collaborative editing systems require eﬃcient mechanisms for managing concurrent updates across distributed replicas. Sequence Conﬂict-free Replicated Data Types (CRDTs) have become the de facto standard for supporting decentralized collaboration; they enable decentralized replicas to apply operations in arbitrary order while converging to a common state. Although existing sequence CRDTs guarantee Strong Eventual Consistency (SEC), they often suﬀer from uncontrolled identiﬁer growth and increasing memory consumption during long-running, highly concurrent editing sessions, which severely limits their scalability and performance. This paper presents the Extended Stern–Brocot Tree (ESBT), a mathematically grounded identiﬁer allocation scheme for distributed collaborative text editing. ESBT extends the classical Stern-Brocot Tree representation by combining bounded rational fractions (𝑓 ), sequence numbers (𝑠𝑛), and sequence paths (𝑠𝑐) into a hierarchical identiﬁer structure that provides a dense, deterministic, and compact identiﬁer space. This design bounds identiﬁer growth while preserving deterministic ordering and Strong Eventual Consistency. In addition, ESBT integrates a Red–Black tree document representation, enabling logarithmic-time (𝑂(log 𝑛)) insertion, deletion, and lookup operations. Experimental evaluation using workloads of up to 100,000 concurrent operations generated across 50 collaborating sites shows that ESBT improves responsiveness by 28 to 88% under pure insertions and 59 to 74% under mixed insertion/deletion workloads, while reducing identiﬁer memory consumption by 50 to 75% in beginning and random insertion patterns compared with the best-performing baseline sequence CRDTs (Logoot and LSEQ). Under the adversarial middle-insertion workload (10,000 operations), ESBT further improves responsiveness by 86.53% and reduces identiﬁer size by 92.81%. These results demonstrate that ESBT eﬀectively addresses the principal scalability limitations of existing sequence CRDTs and provides an eﬃcient and scalable foundation for largescale collaborative editing systems.

1. Introduction Collaborative editing platforms have become an essential component of modern distributed applications, enabling multiple geographically distributed users to update shared text, code, or graphical content simultaneously. To ensure high availability and low latency, each user maintains a local replica that can be updated independently without immediate synchronization across replicas. However, maintaining consistency across all replicas in a decentralized manner remains challenging. Beyond collaborative editing, maintaining deterministic ordering of concurrent operations is equally important in replicated data stores, distributed ledgers, replicated state machines, multiplayer game states, and other large-scale distributed systems. Classical coordination mechanisms such as Lamport timestamps [1] and vector clocks [2] can establish causality but fall short when it comes to enforcing a dense, deterministic order for concurrent operations. This limitation becomes highly evident in decentralized collaborative text editing. Without central coordination, replicas must independently resolve a consistent state, as multiple users simultaneously insert new characters directly between existing ones. Early collaborative editors ∗ Corresponding author

[email protected] (M.D. Mechaoui); [email protected] (A. Imine) ORCID (s):

First Author et al.: Preprint submitted to Elsevier

addressed this challenge using Operational Transformation (OT) [3], which oﬀers strong responsiveness through transformation functions that adjust the parameters (positions) of concurrent operations supporting arbitrary execution order. Although OT is eﬀective for online collaboration with low divergence, its transformation overhead increases as replicas diverge, limiting its scalability in highly distributed and intermittently connected environments. To avoid these scalability constraints, Conﬂict-Free Replicated Data Types (CRDTs) [4, 5, 6] have been widely adopted as an alternative replication paradigm. CRDTs shift the focus from operation transformation to operation commutativity. Speciﬁcally, Sequence CRDTs guarantee that concurrent operations commute naturally. This enables replicas to execute updates independently and automatically achieve Strong Eventual Consistency (SEC) [7]. This property is preserved by attributing each element a unique and immutable identiﬁer that deﬁnes its logical position within all replicas. Replicas can then merge concurrent insertions deterministically without centralized coordination, making sequence CRDTs the modern standard for decentralized collaborative architectures. Despite their advantages, existing sequence CRDTs continue to exhibit important scalability limitations. Existing sequence CRDTs have evolved along two main lines: (𝑖) Tombstone-based approaches [8, 9, 10] preserve deleted

Page 1 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

elements (tombstones) to maintain order [11], which leads to unbounded state growth over time and costly garbage collection. (𝑖𝑖) Identiﬁer-allocation approaches [4, 12] avoid tombstones by assigning dense position identiﬁers. However, under unfavorable or highly localized insertion patterns, these identiﬁers may grow substantially, increasing both memory consumption and identiﬁer comparison costs. To the best of our knowledge, existing sequence CRDTs do not simultaneously ensure (1) bounded identiﬁer growth, (2) tombstone-free deletion management, and (3) lightweight synchronization without replica-sized causal metadata with baseline guarantees of deterministic ordering and Strong Eventual Consistency. These limitations become increasingly signiﬁcant in dynamic collaborative environments characterized by long editing sessions, intermittent connectivity, and users joining or leaving collaboration session at any time. Contributions. To address these limitations, this paper proposes the Extended Stern-Brocot Tree (ESBT), a novel identiﬁer allocation strategy for sequence CRDTs. ESBT extends the mathematical properties of the classical Stern-Brocot tree [13, 14] to generate compact, deterministic, and densely ordered identiﬁers while preventing the unbounded growth of identiﬁers observed in existing identiﬁer-allocation schemes, and without relying on tombstones. Combined with a self-balanced Red-Black tree, ESBT achieves logarithmic 𝑂(log 𝑛) insertion, deletion, and lookup operations, making it suitable for largescale collaborative editing. Furthermore, ESBT introduces a lightweight dependency-based synchronization mechanism that preserves causal correctness using only direct operation dependencies, thereby avoiding replica-sized causal metadata while supporting dynamic participation in decentralized collaborative environments. The main contributions of this work are summarized as follows: • We propose ESBT, a novel Stern–Brocot-tree-based identiﬁer allocation algorithm for sequence CRDTs that generates compact and deterministic position identiﬁers while preserving dense ordering. • We introduce a bounded identiﬁer allocation mechanism that prevents uncontrolled identiﬁer expansion, and supports tombstone-free deletion management. • We propose a lightweight synchronization protocol based on direct operation dependencies that preserves causal correctness without maintaining replica-sized causal metadata. • We formally prove that ESBT guarantees identiﬁer uniqueness, deterministic total ordering, convergence, and Strong Eventual Consistency. • We experimentally evaluate ESBT against representative sequence CRDTs, including Logoot [4] and LSEQ [12] under multiple allocation strategies and collaborative workloads. The results demonstrate

First Author et al.: Preprint submitted to Elsevier

lower memory consumption, more compact identiﬁers, and faster execution times under heavy concurrency. Although motivated by collaborative text editing, the proposed identiﬁer allocation strategy can also be applied to a broader class of replicated ordered data structures, including hierarchical documents, XML, JSON, RDF graphs, Linked Data, and other Semantic Web data models [15]. Outline The rest of this paper is organized as follows. Section 2 reviews the properties of collaborative editing systems and introduces the necessary background. Section 3 presents the Extended Stern–Brocot Tree (ESBT) model. Section 4 describes the coordination model, while Section 5 details the ESBT synchronization layer. Section 6 formalizes the ESBT speciﬁcation, and Section 7 analyzes its asymptotic complexities. Section 8 reports the performance evaluation. Section 9 discusses related work, and Section 10 concludes the paper.

2. Background 2.1. Collaborative Editing Systems Collaborative editing systems typically rely on optimistic replication, which enables each user to independently modify a local replica of a shared document without immediate synchronization. This approach improves responsiveness and fault tolerance but poses the problem of ensuring that all replicas converge to an identical state despite simultaneous modiﬁcations. Several correctness models have been proposed for collaborative editing. Among them, the CCI (Convergence, Causality, and Intention Preservation) model [16] deﬁnes three essential requirements: all replicas must eventually converge to the same state, causal dependencies between operations must be preserved, and semantic intentions of users should be maintained whenever possible. Modern decentralized collaborative systems commonly adopt Strong Eventual Consistency (SEC) [7], which guarantees that replicas converge to the same state after all operations have been delivered, regardless of message ordering, provided that concurrent operations commute. SEC therefore provides the consistency model underpinning most CRDT-based collaborative editing systems. The Stern–Brocot tree [13, 14] provides a mathematical framework to generate an inﬁnite, densely ordered set of rational numbers, making it an attractive foundation for identiﬁer allocation in sequence CRDTs.

2.2. Stern-Brocot Tree The Stern-Brocot tree is an inﬁnite binary tree in which each node represents a distinct positive rational number in its reduced form that occurs exactly once [13, 14]. The tree is built by recursively inserting the mediant between two adjacent fractions, where the mediant of two fractions 𝑎𝑏 and 𝑑𝑐 is 𝑏𝑎 ++ 𝑑𝑐 . Starting from two sentinel nodes 01 and 10 ,

their mediant is the root node 11 , and the process continues Page 2 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

Figure 1: The Stern–Brocot tree structure [13].

recursively as depicted in Figure 1. Each node has a welldeﬁned level, which reﬂects its depth in the tree. The SternBrocot tree naturally sorts out the fractions in ascending order under an in-order traversal. By construction, every fraction created through the mediant is unique and preserves the numerical ordering of adjacent fractions. The Stern-Brocot tree has several properties that make it eﬃcient that make it attractive for identiﬁer allocation. First, each fraction is the mediant of its two parent fractions, making its value independent of other parts of the tree. Second, fractions within each level are always sorted by magnitude. These features allow for a targeted search, eliminating the need to compute the entire tree. Finally, the recursive mediant process generates an inﬁnitely dense sequence of fractions, which ensures that new fractions can always be allocated between adjacent fractions. These properties make the tree a particularly interesting candidate for generating unique identiﬁers per site (fraction, site identiﬁer) in collaborative editing systems. Nevertheless, the classical Stern-Brocot tree is not suﬃcient to resolve concurrent insertions that concurrently generate the same rational fraction at diﬀerent replicas. Additional mechanisms are therefore required to guarantee identiﬁer uniqueness while preserving deterministic ordering in decentralized collaborative environments.

3. Extended Stern-Brocot Tree This section presents the Extended Stern–Brocot Tree (ESBT), a novel identiﬁer allocation strategy for sequence CRDTs. ESBT extends the classical Stern-Brocot tree [13, 14] by augmenting mediant-based rational identiﬁers with additional disambiguation parameters to guarantee uniqueness, deterministic ordering, and bounded identiﬁer growth under concurrent insertions.

3.1. ESBT Deﬁnition ESBT generalizes the mediant-based enumeration of the Stern-Brocot tree by constructing composite identiﬁers that remain totally ordered, immutable, and unique under concurrent updates. Each identiﬁer encodes the logical position of a sequence element and serves as the basis for deterministic merging in collaborative editing. The fundamental identiﬁer in ESBT is the Weight, a composite identiﬁer that uniquely determines the logical position of an element within global order. Deﬁnition 1 (Weight). An ESBT weight is a quadruple 𝑊 = ⟨𝑓 , 𝑠𝑛, 𝑠𝑐, 𝛿⟩ where: First Author et al.: Preprint submitted to Elsevier

• 𝑓 = 𝑞𝑝 ∈ ℚ+ where gcd(p, q) =1, is an irreducible positive fraction (mediant) generated through the mediant operation of the Stern-Brocot tree and serves as the primary ordering key, • 𝑠𝑛 ∈ ℤ is a sequence number, used to distinguish successive insertions that share the same rational fraction. • 𝑠𝑐 ∈ ℕ∗ sequence path is a ﬁnite lexicographically ordered sequence of non-negative integers used only when all available sequence numbers associated with the same fraction have been exhausted. • 𝛿 is the replica (site) identiﬁer, used only as the ﬁnal deterministic tie-breaker when all preceding ordering components are identical. Consequently, identiﬁer ordering is determined primarily by the logical insertion position represented by 𝑓 , then by the local insertion order encoded by 𝑠𝑛, followed by the sequence path 𝑠𝑐. The replica identiﬁer 𝛿 is consulted only as a ﬁnal deterministic tie-breaker, thus preserving user intention while guaranteeing global uniqueness. Deﬁnition 2 (Total Ordering Relation). For two weights 𝑊𝑖 = ⟨𝑓𝑖 , 𝑠𝑛𝑖 , 𝑠𝑐𝑖 , 𝛿𝑖 ⟩ and 𝑊𝑗 = ⟨𝑓𝑗 , 𝑠𝑛𝑗 , 𝑠𝑐𝑗 , 𝛿𝑗 ⟩, ⎧ 𝑓𝑖 < 𝑓𝑗 , ⎪ ⎪or 𝑓𝑖 = 𝑓𝑗 ∧ 𝑠𝑛𝑖 < 𝑠𝑛𝑗 , 𝑊𝑖 < 𝑊𝑗 ⇔ ⎨ ⎪or 𝑓𝑖 = 𝑓𝑗 ∧ 𝑠𝑛𝑖 = 𝑠𝑛𝑗 ∧ 𝑠𝑐𝑖 ≺ 𝑠𝑐𝑗 , ⎪ ⎩or 𝑓𝑖 = 𝑓𝑗 ∧ 𝑠𝑛𝑖 = 𝑠𝑛𝑗 ∧ 𝑠𝑐𝑖 = 𝑠𝑐𝑗 ∧ 𝛿𝑖 ≺ 𝛿𝑗 where ≺ denotes lexicographic order on ﬁnite integer sequences. The hierarchical comparison ensures that the rational fraction remains the primary determinant of logical position. Additional components are consulted only when preceding components are identical, thereby preserving user-intended ordering while guaranteeing deterministic conﬂict resolution under concurrent insertions.

ESBT Tree Structure The ESBT is organized as an inﬁnite, ordered, and rooted binary tree of immutable weights. Two sentinel weights delimit the entire ordering space: 𝑊END = ( 10 , 0, [0], ∅). The 𝑊BEGIN = ( 10 , 0, [0], ∅), Page 3 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

fractions 10 and 10 represent the lower and upper boundaries of the rational ordering space, respectively, and ∅ denotes the null site identiﬁer reserved exclusively for sentinel ( ) nodes. The root node is deﬁned as 𝑊𝑟𝑜𝑜𝑡 = 11 , 0, [0], ∅ . Unlike the classical Stern–Brocot tree, every node in the ESBT stores a complete weight rather than only a rational fraction, allowing deterministic ordering under concurrent insertions.

Structural Invariants Deﬁnition 3 (Structural Invariants). The ESBT satisﬁes the following invariants: 1. Immutability. Every weight is immutable after creation and uniquely identiﬁes the logical position of a sequence element. 2. Ordering. For every node 𝑊𝑃 , all weights stored in the left subtree are smaller than 𝑊𝑃 , while all weights stored in the right subtree are greater than 𝑊𝑃 , according to the total ordering relation deﬁned in Deﬁnition 2. 3. Uniqueness. No two distinct sequence elements may share the same weight. When identical fractions are generated concurrently, the additional ordering components (𝑠𝑛, 𝑠𝑐, 𝛿) guarantee uniqueness without modifying previously allocated identiﬁers.

Allocation Principle Given two adjacent weights 𝑊𝐿 = ⟨𝑓𝐿 , 𝑠𝑛𝐿 , 𝑠𝑐𝐿 , 𝛿𝐿 ⟩,

𝑊𝑅 = ⟨𝑓𝑅 , 𝑠𝑛𝑅 , 𝑠𝑐𝑅 , 𝛿𝑅 ⟩,

3.2. Hierarchical Ordering Layers To guarantee unique and totally ordered identiﬁers under arbitrary concurrent insertions, ESBT organizes each weight into three hierarchical ordering layers. The fraction layer provides the primary logical position using the Stern–Brocot tree, the sequence number layer extends this ordering when fractional reﬁnement reaches the bound 𝐷max , and the sequence path layer resolves any remaining collisions lexicographically. Consequently, ESBT preserves deterministic ordering, guarantees uniqueness, bounds fraction growth, and expands identiﬁers only when required by concurrent conﬂicts.

3.2.1. Fraction Layer The fraction layer provides the primary ordering component of an ESBT weight. It exploits the density of the Stern–Brocot tree to allocate new weights between existing neighbors elements without requiring pre-allocation or global coordination. Each weight in this layer is represented by an irreducible fraction: 𝑓 = 𝑞𝑝 , 𝑝, 𝑞 ∈ ℕ, gcd(𝑝, 𝑞) = 1, which corresponds to a unique position in the inﬁnite Stern–Brocot tree. Ordering is immediate: 𝑝1 𝑝 < 𝑞2 ⇔ 𝑝1 𝑞2 < 𝑝2 𝑞1 . 𝑞1 2 The generation of a new weight proceeds by computing the mediant (of the)left and right neighbors: 𝑎+𝑐 . mediant 𝑎𝑏 , 𝑑𝑐 = 𝑏+𝑑 The mediant fraction lies strictly between its parents, which preserves order without needing global coordination. Repeated mediant operations allow for an arbitrarily dense embedding of new weights between any two existing ones.

Boundedness Constraint. To prevent unlimited numera-

where 𝑝 𝑓𝐿 = 𝐿 , 𝑞𝐿

𝑝 𝑓𝑅 = 𝑅 , 𝑞𝑅

ESBT allocates a new identiﬁer by computing the mediant 𝑓𝑀 =

𝑝𝐿 + 𝑝𝑅 . 𝑞𝐿 + 𝑞𝑅

tor or denominator growth, ESBT enforces a global threshold 𝐷max . Once this bound is reached, further fractional reﬁnement is suspended and identiﬁer allocation proceeds through the sequence number and sequence path layers. This design bounds growth in the hierarchy of the fraction space while preserving the ability to generate inﬁnite weights for each logical position.

The newly generated weight 𝑊𝑀 is inserted between 𝑊𝐿 and 𝑊𝑅 as 𝑊𝐿 < 𝑊𝑀 < 𝑊𝑅 thereby preserving the strict total ordering deﬁned in Deﬁnition 2.

Lemma 1 (Bounded Fraction Property). Let each weight in ESBT be deﬁned as: 𝑊 = ⟨𝑓 = 𝑞𝑝 , 𝑠𝑛, 𝑠𝑐, 𝛿⟩

Bounded Allocation Policy To prevent unbounded identiﬁer growth, ESBT introduces a conﬁgurable bound 𝐷max on the numerator and denominator of newly generated mediants. When this bound is exceeded, allocation proceeds hierarchically through the disambiguation layers 𝑠𝑛, 𝑠𝑐, and ﬁnally 𝛿, thereby preserving uniqueness, deterministic ordering, and bounded identiﬁer growth.

If the ESBT allocation enforces a bounded numerator or denominator constraint such that: 𝑝 ≤ 𝐷max or 𝑞 ≤ 𝐷max ,

First Author et al.: Preprint submitted to Elsevier

then every fraction 𝑓 generated by the allocator remains within a ﬁnite, dense, and totally ordered rational interval.

3.2.2. Sequence Number Layer The fraction 𝑓 is not suﬃcient to guarantee uniqueness when multiple sites (replicas) concurrently insert elements at the same fractional position. The second layer, sequence number (𝑠𝑛), provides a lightweight, integer-based disambiguation mechanism that ensures deterministic and Page 4 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

bounded ordering among elements sharing the same fraction. Formally, for any two weights: 𝑊𝑖 = ⟨𝑓𝑖 , 𝑠𝑛𝑖 , 𝑠𝑐𝑖 , 𝛿𝑖 ⟩ and 𝑊𝑗 = ⟨𝑓𝑗 , 𝑠𝑛𝑗 , 𝑠𝑐𝑗 , 𝛿𝑗 ⟩, if (𝑓𝑖 = 𝑓𝑗 ) then, their relative order is determined by comparing their local sequence numbers:

the two neighbors 𝑠𝑐𝐿 and 𝑠𝑐𝑅 . The algorithm compares both paths digit by digit and attempts to locate the ﬁrst depth where a numerical gap exists between the left value (𝑙𝑣) and right value (𝑟𝑣). If such a gap exists (𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 = 𝑟𝑣 − 𝑙𝑣 − 1 > 0), the algorithm allocates a new digit at the midpoint of the interval: 𝑛𝑒𝑤𝑉 𝑎𝑙 = 𝑙𝑣 +

𝑠𝑛𝑖 < 𝑠𝑛𝑗 ⇒ 𝑊𝑖 ≺ 𝑊𝑗 . This ordering rule ensures that weights originating from the same fractional interval are locally sequential and globally comparable across replicas. Each site maintains a local Tracker, a hash map indexed by fraction values whose median exceeds 𝐷𝑚𝑎𝑥 . Deﬁnition 4 (Site Tracker). Each site maintains a Tracker:  ∶ 𝑓 ↦ (𝑠𝑛𝐿 , 𝑠𝑛𝑅 ), where 𝑠𝑛𝐿 and 𝑠𝑛𝑅 denote, respectively, the next 𝑠𝑛 to be allocated when allocating immediately to the left or right of the fraction 𝑓 . The tracker allows controlled 𝑠𝑛 increment/decrement instead of unbounded fraction reﬁnement.

𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 +1 2

This midpoint allocation guarantees that the new path value lies strictly between its neighbors, ensuring deterministic ordering. If the gap is exhausted (𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 = 0), the common preﬁx is extended by appending 𝑙𝑣, and the algorithm descends to the next depth level. If all depth levels are explored without ﬁnding any available gap (𝑑𝑒𝑝𝑡ℎ ≥ 𝐷𝐸𝑃 𝑇 𝐻), a ﬁnal fallback digit is appended using the site identiﬁer: 𝑡𝑖𝑒 = 1 + (𝑠𝑖𝑡𝑒𝐼𝑑 mod (𝑏𝑎𝑠𝑒 − 1)) This ensures that each site still generates a unique sequence path, even under extreme concurrency. Algorithm 1 NEW SEQ(𝑙𝑒𝑓 𝑡, 𝑟𝑖𝑔ℎ𝑡, 𝑏𝑎𝑠𝑒, 𝐷𝐸𝑃 𝑇 𝐻 )

The bounded fractions (𝑓 <𝐷𝑚𝑎𝑥 ) remain untracked, ensuring that the structure remains lightweight and sparse. The sequence number layer resolves the conﬂict by monotonically increasing (or decreasing) 𝑠𝑛 according to the allocation direction: • Left Allocation: When a new weight must precede an existing one that shares the same fraction 𝑓 , the site consults the left counter 𝑠𝑛𝐿 and assigns the next available lower integer: 𝑠𝑛new = 𝑠𝑛𝐿 − 1. • Right Allocation: In contract, when a new weight must follow within the same fraction, the right counter 𝑠𝑛𝑅 is incremented: 𝑠𝑛new = 𝑠𝑛𝑅 + 1. The function C REATE_W EIGHT (see Algorithm 3.3) implements this policy by ensuring that, for any fraction 𝑓 reaching the 𝐷max boundary, an inﬁnite sequence of 𝑠𝑛 values is available without violating the order of neighboring weights. Each site allocates its local 𝑠𝑛 independently and deterministically for a given fraction, ensuring that all replicas converge to a consistent global order that maintains strong eventual consistency.

3.2.3. Sequence Path Layer The third layer is the sequence path 𝑠𝑐 where 𝑠𝑐 = [𝑐1 , 𝑐2 , … , 𝑐𝑘 ] with 𝑐𝑖 ∈ ℕ. The sequence path is a list of integers that acts as a deterministic tie-breaker in rare cases where two weights share the same fraction 𝑓 and sequence number 𝑠𝑛. By design, 𝑠𝑐 remains short or empty in most insertions; it is only created when 𝑠𝑛 alone cannot diﬀerentiate two concurrent insertions. When 𝑓 and 𝑠𝑛 are equal, the function N EW SEQ(𝑠𝑐𝐿 , 𝑠𝑐𝑅 , 𝑏𝑎𝑠𝑒, 𝐷𝐸𝑃 𝑇 𝐻) (Algorithm 1) is invoked to compute a new sequence path strictly between First Author et al.: Preprint submitted to Elsevier

1: 𝑠𝑐 ← [] 2: 𝑑𝑒𝑝𝑡ℎ ← 0 3: while true do 4: if 𝑑𝑒𝑝𝑡ℎ < |𝑙𝑒𝑓 𝑡| then 5: 𝑙𝑣 ← 𝑙𝑒𝑓 𝑡[𝑑𝑒𝑝𝑡ℎ] 6: else 7: 𝑙𝑣 ← 0 8: end if 9: if 𝑑𝑒𝑝𝑡ℎ < |𝑟𝑖𝑔ℎ𝑡| then 10: 𝑟𝑣 ← 𝑟𝑖𝑔ℎ𝑡[𝑑𝑒𝑝𝑡ℎ] 11: else 12: 𝑟𝑣 ← 𝑏𝑎𝑠𝑒 13: end if 14: 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 ← 𝑟𝑣 − 𝑙𝑣 − 1 15: if 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 > 0 then 16:

𝑛𝑒𝑤𝑉 𝑎𝑙 ← 𝑙𝑣 + (

𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 2

)+1

17: if 𝑛𝑒𝑤𝑉 𝑎𝑙 ≥ 𝑟𝑣 then 18: 𝑛𝑒𝑤𝑉 𝑎𝑙 ← 𝑟𝑣 − 1 19: end if 20: 𝑠𝑐.add(𝑛𝑒𝑤𝑉 𝑎𝑙) 21: return 𝑠𝑐 22: else 23: 𝑠𝑐.add(𝑙𝑣) 24: 𝑑𝑒𝑝𝑡ℎ ← 𝑑𝑒𝑝𝑡ℎ + 1 25: if 𝑑𝑒𝑝𝑡ℎ ≥ 𝐷𝐸𝑃 𝑇 𝐻 then 26: 𝑡𝑖𝑒 ← 1 + (𝑠𝑖𝑡𝑒𝐼𝑑 mod (𝑏𝑎𝑠𝑒 − 1)) 27: 𝑠𝑐.add(𝑡𝑖𝑒) 28: return 𝑠𝑐 29: end if 30: end if 31: end while

Example 1 (Gap available at low depth). Consider 𝑠𝑐𝐿 = [3] and 𝑠𝑐𝑅 = [7], with 𝑏𝑎𝑠𝑒 = 10, 𝐷𝐸𝑃 𝑇 𝐻 = 3, and 𝑠𝑖𝑡𝑒𝐼𝑑 = 2. Page 5 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

At depth 0: 𝑙𝑣 = 3, 𝑟𝑣 = 7, giving 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 = 3. A midpoint is chosen: 𝑛𝑒𝑤𝑉 𝑎𝑙 = 3 + 23 + 1 = 5. The resulting path is 𝑠𝑐𝑛𝑒𝑤 = [5], which lies strictly between the two neighbors. The process ends immediately since a valid midpoint was found.

Example 2 (No gap, deeper allocation required). Now take 𝑠𝑐𝐿 = [3] and 𝑠𝑐𝑅 = [4]. At depth 0: 𝑙𝑣 = 3, 𝑟𝑣 = 4, resulting in 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 = 0. Since there is no gap, the algorithm appends 3 and moves to depth 1. At this level, the defaults are 𝑙𝑣 = 0, 𝑟𝑣 = 10, producing 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 = 9. The midpoint allocation gives 𝑛𝑒𝑤𝑉 𝑎𝑙 = 0 + 92 + 1 = 5. The resulting sequence path is 𝑠𝑐𝑛𝑒𝑤 = [3, 5], which preserves strict order and stability. If all depth levels are exhausted without ﬁnding a gap, the fallback rule appends a deterministic tie digit derived from 𝑠𝑖𝑡𝑒𝐼𝑑, ensuring site-speciﬁc uniqueness. 3.2.4. Sequence Path Order Since 𝑠𝑐 is totally ordered lexicographically, any two paths under the same fraction 𝑓 and sequence number 𝑠𝑛 admit a deterministic comparison according the following deﬁnition. Deﬁnition 5 (Lexicographic Order on Sequence Paths). Let 𝑠𝑐𝑖 = [𝑐𝑖,0 , 𝑐𝑖,1 , … , 𝑐𝑖,𝑚 ] and 𝑠𝑐𝑗 = [𝑐𝑗,0 , 𝑐𝑗,1 , … , 𝑐𝑗,𝑛 ] be two sequence paths. We deﬁne the lexicographic order ≺ as: ) ( 𝑠𝑐𝑖 ≺ 𝑠𝑐𝑗 ⇔ ∃ 𝑑 𝑐𝑖,𝑑 < 𝑐𝑗,𝑑 ∧ ∀ 𝑘 < 𝑑, 𝑐𝑖,𝑘 = 𝑐𝑗,𝑘 . We say that, 𝑠𝑐𝑖 precedes 𝑠𝑐𝑗 if, at the ﬁrst position 𝑑 where they diﬀer, the digit of 𝑠𝑐𝑖 is strictly smaller, while all earlier digits are equal. With 𝑘 an index for all earlier positions than 𝑑. In ESBT, most allocations are resolved at the fractional or sequence number layers, meaning that the vast majority of weights maintain an empty sequence path 𝑠𝑐 = [0]. This layered design allows ESBT weights to achieve unlimited resolution while maintaining compactness, determinism, and performance eﬃciency across distributed replicas. Theorem 1 (Uniqueness). For every insertion operation, ESBT generates a globally unique identiﬁer through a hierarchical disambiguation process: 1. a fractional mediant 𝑓𝑚 is computed when 𝑓𝑚 ≤ 𝐷max ; 2. a sequence number 𝑠𝑛 is applied when mediants are exhausted 𝑓𝑚 > 𝐷max ; 3. and a deterministic sequence-path 𝑠𝑐 using N EW SEQ is applied when concurrent insertions still conﬂict. Consequently, the ordering relation < deﬁnes a total, replica-invariant order that remains consistent and preserved across all sites.

First Author et al.: Preprint submitted to Elsevier

Algorithm 2 CREATE_WEIGHT(𝜔1, 𝜔2 ) 1: 𝛿 ← site identiﬁer 2: 𝑏𝑎𝑠𝑒 ← available digit space at each depth level 3: 𝑑𝑒𝑝𝑡ℎ ← maximum number of levels 4: 𝑛𝑢𝑚 ← 𝜔1 .𝑝 + 𝜔2 .𝑝 5: 𝑑𝑒𝑛 ← 𝜔1 .𝑞 + 𝜔2 .𝑞 6: Let ∇ ← gcd(𝑛𝑢𝑚, 𝑑𝑒𝑛) 𝑛𝑢𝑚 7: 𝑓𝑚 .𝑝 ← , 𝑓𝑚 .𝑞 ← 𝑑𝑒𝑛 8: 𝑓𝑚 ←

∇ 𝑓𝑚 .𝑝

∇

𝑓𝑚 .𝑞

9: 𝐷max ← maximum 𝑛𝑢𝑚 and 𝑑𝑒𝑛 threshold 10: if (𝑓𝑚 .𝑝 < 𝐷max ) or (𝑓𝑚 .𝑞 < 𝐷max ) then 11: return (𝑓𝑚 , 0, [0], 𝛿) 12: end if 0 13: if 𝜔1 .𝑓 = then 1 14: 𝑓𝑏 ← 𝜔2 .𝑓 15: else 16: 𝑓𝑏 ← 𝜔1 .𝑓 17: end if 18: Tracker(𝑓𝑏 ) ← (𝑠𝑛𝐿 , 𝑠𝑛𝑅 ) 19: if (𝑓𝑏 < 𝜔2 .𝑓 ) or ((𝑓𝑏 = 𝜔2 .𝑓 ) and (𝑠𝑛𝑅 < 𝑤2 .𝑠𝑛)) then 20: 𝑠𝑛 ← 𝑠𝑛𝑅 + 1 21: 𝑠𝑐 ← 𝜔1 .𝑠𝑐 22: Update 𝑠𝑛𝑅 ← 𝑠𝑛 in Tracker 23: return (𝑓𝑏 , 𝑠𝑛, 𝑠𝑐, 𝛿) 24: else if (𝜔1 .𝑓 < 𝜔2 .𝑓 ) and (𝑠𝑛𝐿 − 1 < 𝜔2 .𝑠𝑛) then 25: 𝑠𝑛 ← 𝑠𝑛𝐿 − 1 26: 𝑠𝑐 ← 𝜔1 .𝑠𝑐 27: Update 𝑠𝑛𝐿 ← 𝑠𝑛 in Tracker 28: return (𝑓𝑏 , 𝑠𝑛, 𝑠𝑐, 𝛿) 29: else 30: 𝑠𝑛 ← 𝜔1 .𝑠𝑛 31: 𝑠𝑐 ← NEW S EQ(𝜔1 .𝑠𝑐, 𝜔2 .𝑠𝑐, 𝑏𝑎𝑠𝑒, 𝑑𝑒𝑝𝑡ℎ) 32: return (𝑓𝑏 , 𝑠𝑛, 𝑠𝑐, 𝛿) 33: end if

3.3. ESBT Allocation Function The CREATE_WEIGHT function (Algorithm 2) deﬁnes the core logic for allocating a new unique weight in ESBT. This function ensures consistent insertion order, bounded fraction precision, and convergence across replicas while preserving compact and ordered weights. The algorithm takes as input two adjacent weights 𝜔1 and 𝜔2 , and returns a new ESBT weight of the form (𝑓 , 𝑠𝑛, 𝑠𝑐, 𝛿).

Case 1: Mediant ﬁts within 𝐷𝑚𝑎𝑥 The function computes the mediant fraction 𝑓𝑚 between the two input fractions (lines 2–11): 𝑓𝑚 =

𝜔1 .𝑝 + 𝜔2 .𝑝 𝜔1 .𝑞 + 𝜔2 .𝑞

The resulting numerator and denominator are then reduced to the lowest terms using the greatest common divisor (GCD). This mediant provides a new rational value strictly between the two fractions, preserving the insertion order. If the simpliﬁed mediant numerator or denominator is less than 𝐷max , the function immediately returns a canonical weight with this fraction (𝑓𝑚 ), a default sequence number 𝑠𝑛 = 0, and a default sequence path 𝑠𝑐 = [0] (line 11). This case covers the majority of insertions in the sparse region Page 6 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

Figure 2: The Extended Stern–Brocot tree structure (with 𝐷𝑚𝑎𝑥 = 5 ).

of the weight space and avoids further disambiguation. ( ) 1 Example : Let 𝑤1 = , 0, [0], 𝛿 𝑤2 1 , 3 ( ) 1 , 0, [0], 𝛿1 , and 𝐷max = 10. 2

1+1 = 52 . Since (2 < 𝐷max ) and The computed mediant is : 3+2 (5 < 𝐷max ), the mediant is valid. The function returns the new weight: ( 25 , 0, [0],𝛿1 ).

Fallback Fraction Selection (Lines 13–16) If the mediant exceeds 𝐷max , the function falls back to the next allocation layer. A fallback fraction 𝑓𝑏 is selected from left weight 𝜔1 .𝑓 unless 𝜔1 is a sentinel (e.g., 10 ), in which case 𝜔2 .𝑓 is used. This ensures that disambiguation is always performed within a well-deﬁned and nonsentinel range. This strategy biases allocations towards the left weight (which has a smaller fraction value), yet this consistent preference simpliﬁes the algorithm’s logic. Case 2: Sequence Number Layer (Lines 18–28) The function uses a local Tracker to maintain the left (𝑠𝑛𝐿 ) and right (𝑠𝑛𝑅 ) sequence number boundaries for each fallback fraction ∀𝑓𝑏 ∶ 𝑠𝑛𝐿 ≤ 𝑠𝑛 ≤ 𝑠𝑛𝑅 . It attempts to assign a new sequence number using the following rules: • Right Allocation: If the fallback fraction 𝑓𝑏 is strictly less than 𝜔2 .𝑓 , or equal but with a smaller right 𝑠𝑛, a new 𝑠𝑛 is assigned as 𝑠𝑛𝑅 + 1 with 𝑠𝑐 = [0]. The right tracker is updated accordingly (lines 19–23). • Left Allocation: If 𝜔1 .𝑓 less than 𝜔2 .𝑓 and the left gap is suﬃcient (𝜔2 .𝑠𝑛 < 𝑠𝑛𝐿 − 1), a new 𝑠𝑛 is assigned as 𝑠𝑛𝐿 − 1, again with 𝑠𝑐 = [0]. The left tracker is updated accordingly (lines 24–28). These optimizations avoid generating deeper 𝑠𝑐 paths when a free sequence number is available, ensuring better compactness of the weight and faster comparison.

Case 3: Sequence Path Layer (line 29–32) This ﬁnal case is a fallback when the sequence number space between the relevant weights has been exhausted. The algorithm reuses the sequence number 𝑠𝑛1 and delegates the responsibility of creating a unique weight to the NEW SEQ function (line 31) as presented in Sub-Section 3.2.3. The role of NEW SEQ is to generate a new sequence path 𝑠𝑐𝑚 that is lexicographically between 𝑠𝑐1 and 𝑠𝑐2 . This guarantees that weights can always be inserted between any First Author et al.: Preprint submitted to Elsevier

two existing weights by extending the 𝑠𝑐 path when needed. The function then returns the new weight with the fallback fraction 𝑓𝑏 , the preserved sequence number, the newly generated 𝑠𝑐 path, and the local site identiﬁer 𝛿 (line 32). By prioritizing mediant fractions, falling back to 𝑠𝑛 when needed, and using 𝑠𝑐 paths only as a last resort, the algorithm ensures both eﬃciency and global convergence.

3.4. Illustrative Examples. Consider a collaborative document represented as an Extended Stern–Brocot Tree (ESBT) with 𝐷max = 5, 𝑏𝑎𝑠𝑒 = 10, 𝐷𝐸𝑃 𝑇 𝐻 = 3, and 𝑠𝑖𝑡𝑒𝐼𝑑 = 2. Suppose the current tree contains two adjacent weights at fraction layer: 𝑤1 = ( 41 , 0, [], 𝛿𝑎 ) and 𝑤2 = ( 32 , 0, [], 𝛿𝑎 ). Situation 1: Fraction Layer Insertion. When a user attempts to insert a new element between 𝑤1 and 𝑤2 , the mediant is computed as 𝑚 = 1+2 = 37 . Since the 4+3 denominator 7 > 𝐷max , the fraction layer cannot support this insertion, so the responsibility is delegated to the upper layers of the ESBT allocation strategy. Situation 2: Sequence Number Layer Insertion. If a user attempts to insert between 𝑤1 and 𝑤2 . The mediant is 73 , since its denominator exceeds 𝐷max , the algorithm falls back to the sequence number layer. Right Insertion. Inserting after ( 14 , 0, [0], 𝛿𝑎), the selected fallback fraction

is 𝑓𝑏 = 41 . The right boundary is 𝑠𝑛𝑅 = 0, hence the new sequence number is 𝑠𝑛 = 𝑠𝑛𝑅 + 1 = 1. The Tracker for 1 updates from (0, 0) to (0, 1), and the resulting weight is 4 ( 41 , 1, [0], 𝛿𝑎).

If another insertion occurs after ( 14 , 1, [0], 𝛿𝑎), the new sequence number is computed as 𝑠𝑛 = 2, the Tracker becomes (0, 2), and the new weight is ( 14 , 2, [0], 𝛿𝑎). Left insertion. Now consider inserting before 𝑤1 = ( 41 , 0, [], 𝛿𝑎). The left boundary is 𝑠𝑛𝐿 = 0, so the new sequence number is 𝑠𝑛 = 𝑠𝑛𝐿 − 1 = −1. The Tracker updates to (−1, 2), producing the weight ( 14 , −1, [0], 𝛿𝑎). If we insert again before ( 41 , −1, [0], 𝛿𝑎), then 𝑠𝑛 = −2, the Tracker updates to (−2, 2), and the new weight is: ( 41 , −2, [0], 𝛿𝑎). Page 7 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

Global order. The resulting order of weights is: ( 41 , −2, [0], 𝛿𝑎) < ( 14 , −1, [0], 𝛿𝑎) < ( 41 , 0, [0], 𝛿𝑎)

( 14 , 1, [0], 𝛿𝑎) < ( 14 , 2, [0], 𝛿𝑎) < ( 32 , 0, [0], 𝛿𝑎).

Situation 3: Sequence Path Layer Insertion. If a new element is inserted between ( 41 , 0, [0], 𝛿𝑎) and

( 14 , 1, [0], 𝛿𝑎) there is no integer available for the new 𝑠𝑛. In this case, the algorithm uses N EW SEQ for generating a reﬁned 𝑠𝑐. For instance, a possible 𝑠𝑐 path for the new element is 𝑤new = ( 41 , 0, [0, 5], 𝛿𝑎), which correctly orders it between the two existing weights: ( 14 , 0, [0], 𝛿𝑎) < ( 14 , 0, [0, 5], 𝛿𝑎) < ( 14 , 1, [0], 𝛿𝑎).

4. Distributed Coordination Model In our model, we consider an asynchronous distributed collaborative editing system composed of multiple sites connected through a network. We assume that the communication between sites is reliable, and the sites may join or leave the system at any time. Updates are disseminated using an epidemic propagation mechanism, ensuring that each modiﬁcation eventually reaches all sites, either directly or through intermediate relays [17].

4.1. Shared Document Representation Each replica stores the shared document as a selfbalancing Red–Black tree [18], in which nodes are ordered according to their ESBT weights. This balanced binary search tree guarantees worst-case 𝑂(log 𝑛) time complexity for insertion, deletion, and lookup operations while maintaining a balanced height regardless of the editing workload. Each document node is represented as the pair ⟨𝑊 , 𝐶⟩, where 𝑊 is an ESBT weight (Deﬁnition 1) that uniquely identiﬁes the logical position of the element, and 𝐶 denotes the associated content. The content may represent a character, paragraph, list item, JSON object, XML node, or any other structured element, enabling ESBT to support both linear and hierarchical collaborative data. The document is bounded by two immutable sentinel nodes ⟨𝑊BEGIN , ⊥⟩ and ⟨𝑊END , ⊤⟩, where ⊥ and ⊤ are reserved symbols denoting the lower and upper boundaries of the document, respectively. These sentinel nodes are system-deﬁned and are never created, modiﬁed, or deleted by user operations. This representation combines the deterministic ordering of ESBT weights with the logarithmic-time guarantees of Red– Black trees, providing an eﬃcient foundation for scalable collaborative editing. Since the ordering relation is total, the logical position of each document element is uniquely determined, and weights released after deletions can be safely reallocated without compromising uniqueness or consistency.

4.2. Editing Operations Users modify the state of the shared document through two primitive editing operations: (i) INS(𝜔𝑛𝑒𝑤 , 𝑒), which First Author et al.: Preprint submitted to Elsevier

inserts a new element 𝑒 into the document by associating a new weight 𝜔𝑛𝑒𝑤 . (ii) DEL(𝜔𝑒𝑥𝑖𝑠𝑡 ) which removes the element identiﬁed by the existing weight (𝜔𝑒𝑥𝑖𝑠𝑡 ). Unlike tombstonebased approaches, deleted weights are released and may subsequently be reused by the ESBT allocation protocol without violating uniqueness or consistency. Multiple replicas may execute editing operations concurrently. Operations are applied locally as soon as they are generated and propagated asynchronously to the remote replicas. Since ESBT weights are globally unique and totally ordered, all replicas deterministically converge to the same document state regardless of the order in which concurrent operations are received. The unique ESBT weight 𝜔 is generated inside the interval 𝑊BEGIN and 𝑊END . Let "≺" be a order relation between position weights. We use 𝜔, 𝜔′ , 𝜔1 , 𝜔2 , …, to denote all ESBT weights. To insert an element between two ESBT weights 𝜔1 and 𝜔2 , such that 𝜔1 ≺ 𝜔2 , simply requires generating a new weight 𝜔𝑛𝑒𝑤 such that: 𝜔1 ≺ 𝜔𝑛𝑒𝑤 ≺ 𝜔2 using CREATE_WEIGHT presented in Sub-Section 3.3.

5. ESBT Synchronization Layer This section introduces the synchronization layer of ESBT, which coordinates updates between replicas in a distributed environment. This layer resolves consistency issues, formalizes the causal relationship between operations, and presents a lightweight control procedure to ensure consistency with minimal communication and storage overhead.

5.1. Consistency Issues Even in collaborative editing systems, naïvely exchanging operations can lead to inconsistencies if causality and uniqueness are not carefully preserved. The following representative scenarios motivate the synchronization mechanism adopted by ESBT.

Scenario 1: Causal Dependency Between Insertion and Deletion Consider a shared document initially containing the text "XY" shown in Figure 3(a). User 1 inserts ’A’ between ’X’ and ’Y’, while User 3 subsequently deletes ’A’ after receiving the insertion. If another replica receives the deletion before the corresponding insertion due to message reordering, the deletion cannot be safely executed, since the referenced weight does not yet exist. Therefore, to ensure causal dependency, deletion must remain pending until its corresponding insertion has been integrated. 𝐼𝑛𝑠(𝜔𝐴 , 𝐴) → 𝐷𝑒𝑙(𝜔𝐴) Therefore, User 2 delays the execution of 𝑂2 until 𝑂1 has been received and applied, ensuring consistent convergence of all replicas.

Scenario 2: Concurrent deletions of the same elements Figure 3(b) illustrates two users concurrently deleting the same element ’A’. When one deletion reaches a replica where ’A’ has already been removed, executing the operation Page 8 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

(a) Causal dependency issue between insertion and deletion.

(b) Concurrent deletions issue of the same elements.

Figure 3: Consistency Issues Scenarios

again would be redundant. To address this issue, each user maintains a local 𝐿𝑜𝑔 of delete operations. Incoming delete operations targeting previously deleted weights are recognized and safely ignored, guaranteeing idempotent deletion and replica convergence.

Scenario 3: Reinsertion at the Same Position Figure 3(c) illustrates a more subtle case. User 1 inserts ’A’, deletes it, and later inserts ’B’ at the same logical position. Because both insertions are computed from the same neighboring weights, they may receive the same weight. If replicas observe these operations in diﬀerent orders, they cannot determine which insertion a deletion refers to. To distinguish reused weights, each insertion is associated with a monotonically increasing counter 𝑐. Weight identiﬁers are therefore represented as: 𝑊 = { (𝜔, 𝑐) ∣ 𝑐 ∈ ℕ } where each pair is considered distinct according to { 𝜔1 ≠ 𝜔2 , or (𝜔1 , 𝑐1 ) ≠ (𝜔2 , 𝑐2 ) iﬀ 𝜔1 = 𝜔2 and 𝑐1 ≠ 𝑐2 . The counter 𝑐 is used only to identify successive insertions sharing the same weight; it does not aﬀect the document ordering. Consequently, reused weights remain unique even under asynchronous message delivery.

of the insertion on which it depends, thereby establishing an explicit dependency between the two operations. Unlike vector clocks, this dependency information is independent of the ESBT ordering components (𝑓 , 𝑠𝑛, 𝑠𝑐) and therefore does not aﬀect identiﬁer allocation or document ordering. This dependency model allows replicas to correctly distinguish between successive insertions that may reuse the same ESBT weight after deletion. Consequently, deletion operations are always applied to their corresponding insertions, even in the presence of message reordering, duplication, or temporary network partitions. Since each operation carries only a single integer counter, the synchronization overhead remains constant and independent of the number of replicas.

5.2.1. Causal Dependency Between Operations To explicitly capture the causal relationship between insertions and deletions, ESBT associates every insertion with a local counter 𝑐. This counter uniquely identiﬁes the insertion at a given replica and is carried unchanged by the corresponding deletion operation. Deﬁnition 6 (Causal Dependency). Let Ins(𝜔, 𝑒, 𝑐) denote an insertion of element 𝑒 at weight 𝜔 with counter 𝑐, and let Del(𝜔, 𝑐) denote a deletion referring the insertion with the same weight 𝜔 and counter 𝑐. We say that Del(𝜔, 𝑐) is causally dependent on Ins(𝜔, 𝑒, 𝑐), denoted by : Ins(𝜔, 𝑒, 𝑐) → Del(𝜔, 𝑐)

5.2. ESBT Causal Dependencies ESBT is compatible with standard causal delivery protocols, including causal broadcast [19] and probabilistic causal broadcast [20]. These mechanisms correctly preserve causality, but often rely on replica-sized metadata, such as vector clocks, whose storage and communication costs increase with the number of participating replicas. To avoid this overhead, ESBT associates each locally generated insertion with a lightweight counter (denoted 𝑐), maintained in a small per-replica map. Every deletion operation carries the counter First Author et al.: Preprint submitted to Elsevier

iﬀ the deletion references the insertion identiﬁed by the same pair (𝜔, 𝑐). A deletion operation is applied only after its corresponding insertion has been integrated locally. If a deletion arrives before the referenced insertion due to message reordering, it is temporarily buﬀered until the dependency is satisﬁed. This explicit dependency model ensures that every deletion removes exactly the intended insertion, even when ESBT Page 9 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

weights are subsequently reused. Consequently, causal correctness is preserved without introducing replica-sized causal metadata or modifying the ESBT ordering layers.

5.3. Lightweight Synchronization Procedure Algorithm 3 presents the synchronization procedure executed independently at each replica. The protocol combines local-ﬁrst execution with the ESBT identiﬁer allocation scheme introduced in Section 3.3 and the dependency model presented in Section 5.2. As a result, replicas can process updates immediately while preserving deterministic convergence under asynchronous communication.

Generation of Local Operations Locally generated operations are executed immediately on the local replica before being propagated asynchronously to the remote participants. For an insertion, the procedure allocates a new ESBT weight 𝜔𝑒 using the C REATE_W EIGHT algorithm and increments the local insertion counter 𝑐. The pair (𝜔𝑒 , 𝑐) is stored in a local CounterMap, establishing a persistent association between the inserted element and its dependency information. This association allows to perform the local insertion operation on any remote site, regardless of their reception order, thus avoiding the inconsistency illustrated in Scenario 3 of Sub-Section 5.1. For deletion, the procedure retrieves the counter associated with the referenced insertion from CounterMap (line 27) and generates the operation Del(𝜔, 𝑐). The deletion is also stored in a local log (𝐿) to avoid ambiguities when previously released weights are later reused. This log prevents the issue described in Scenario 2 of Sub-Section 5.1. Finally, every generated insertion or deletion is disseminated using the underlying reliable broadcast mechanism, ensuring that all replicas eventually receive and integrate the operation. Integration of Remote Operations Each replica maintains a pending queue 𝑄 that contains remote operations whose causal dependencies have not yet been satisﬁed. Upon reception, an operation generated at another replica is inserted into 𝑄 and processed according to its type. Insertion operations are immediately integrated into the local document since they have no unresolved dependencies. In contrast, a deletion operation Del(𝜔, 𝑐) is applied only if its corresponding insertion, identiﬁed by the pair (𝜔, 𝑐), has already been integrated locally. Otherwise, the deletion remains buﬀered in 𝑄 until the required insertion is received, thus avoiding the issue illustrated in Scenario 1 of Sub-Section 5.1. Whenever an operation becomes causally ready, the procedure A PPLY(𝑂𝑝, 𝑆) is invoked to update the local document state 𝑆. This dependency-driven integration guarantees that every deletion is applied to its intended insertion despite message reordering, duplication, or temporary network partitions, while avoiding replica-sized causal metadata.

First Author et al.: Preprint submitted to Elsevier

Algorithm 3 ESBT Control Concurrency Algorithm 1: procedure M AIN 2: INITIALIZE 3: while running do 4: if there is a local input 𝑂𝑝 then 5: G ENERATEO PERATION(𝑂𝑝) 6: else 7: RECEIVEO PERATION 8: INTEGRATEREMOTEOPERATION 9: end if 10: end while 11: end procedure 12: procedure INITIALIZE 13: 𝑄←[] ⊳ Queue of pending operations 14: 𝐿←[] ⊳ Delete Log 15: 𝑆 ← 𝑆0 ⊳ Document state 16: 𝐶𝑜𝑢𝑛𝑡𝑒𝑟𝑀𝑎𝑝 ← {} ⊳ Mapping: weight → counter 17: 𝐶𝑜𝑢𝑛𝑡𝑒𝑟 ← 0 18: 𝛿 ← local site identiﬁer 19: end procedure 20: procedure G ENERATEO PERATION (𝑂𝑝) 21: if 𝑂𝑝 is INS between 𝜔𝑖 and 𝜔𝑖+1 then 22: 𝜔𝑒 ← CREATE_W EIGHT (𝜔𝑖 , 𝜔𝑖+1 ) 23: 𝐶𝑜𝑢𝑛𝑡𝑒𝑟 ← 𝐶𝑜𝑢𝑛𝑡𝑒𝑟 + 1 24: 𝐶𝑜𝑢𝑛𝑡𝑒𝑟𝑀𝑎𝑝[𝜔𝑒 ] ← 𝐶𝑜𝑢𝑛𝑡𝑒𝑟 25: 𝑂𝑝 ← INS (𝜔𝑒 , 𝑒, 𝐶𝑜𝑢𝑛𝑡𝑒𝑟) 26: else 27: 𝑂𝑝 ← D EL (𝜔𝑒 , 𝐶𝑜𝑢𝑛𝑡𝑒𝑟𝑀𝑎𝑝[𝜔𝑒 ]) 28: 𝐿 ← 𝐿 + 𝑂𝑝 29: end if 30: 𝑆 ← A PPLY(𝑂𝑝, 𝑆) 31: Broadcast 𝑂𝑝 to other users 32: end procedure 33: procedure R ECEIVEO PERATION 34: if there is an operation 𝑂𝑝 from the network then 35: 𝑄 ← 𝑄 + 𝑂𝑝 36: end if 37: end procedure 38: procedure INTEGRATEREMOTEO PERATION 39: for all 𝑂𝑝 ∈ 𝑄 such that ISCAUSALLYREADY(𝑂𝑝) do 40: 𝑄 ← 𝑄 − 𝑂𝑝 41: 𝑆 ← A PPLY(𝑂𝑝, 𝑆) 42: if 𝑂𝑝 is D EL then 43: 𝐿 ← 𝐿 + 𝑂𝑝 44: end if 45: end for 46: end procedure 47: function ISCAUSALLYR EADY(𝑂𝑝) 48: if 𝑂𝑝 is D EL(𝜔𝑒 , 𝑐) then 49: if 𝜔𝑒 ∈ 𝑆 then 50: return true ⊳ Insertion exists: Apply 51: else if (𝜔𝑒 , 𝑐) ∈ 𝐿 then 52: return false ⊳ Already deleted: Ignore 53: else 54: return false ⊳ Insertion not yet arrived: Wait 55: end if 56: else 57: return true ⊳ Insertions are always Ready 58: end if 59: end function

Page 10 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

6. Formal Model of ESBT To reason about correctness and convergence, we formalize the Extended Stern–Brocot Tree as an ordered set of weights. We state a series of theorems showing that ESBT preserves a strict total order, generates globally unique weights, and converges under arbitrary operation delivery. Theorem 2 (Mediant Constraint). Let 𝐷max ∈ ℕ be the predeﬁned bound for both numerator and denominator. For any attempted insertion between 𝑊𝐿 = (𝑓𝐿 , 𝑠𝑛𝐿 , 𝑠𝑐𝐿 , 𝛿𝐿 ) and 𝑊𝑅 = (𝑓𝑅 , 𝑠𝑛𝑅 , 𝑠𝑐𝑅 , 𝛿𝑅 ), compute the mediant 𝑓∗ =

𝑝𝐿 + 𝑝𝑅 , 𝑞𝐿 + 𝑞𝑅

𝑓𝐿 =

𝑝𝐿 𝑝 , 𝑓𝑅 = 𝑅 . 𝑞𝐿 𝑞𝑅

If max(num(𝑓 ∗ ), den(𝑓 ∗ )) ≤ 𝐷max , assign 𝑓 ∗ as the fraction for the new weight. Otherwise, ESBT handles this by: 1. Allocating an unused sequence number 𝑠𝑛 from the site’s tracker, 2. On concurrent collisions, generating a ﬁnite sequence path 𝑠𝑐 = N EW SEQ(𝑠𝑐𝐿 , 𝑠𝑐𝑅 , 𝑏𝑎𝑠𝑒, 𝐷𝐸𝑃 𝑇 𝐻). Consequently, ∃! 𝑊 = (𝑓 , 𝑠𝑛, 𝑠𝑐, 𝛿) such that 𝑊𝐿 < 𝑊 < 𝑊𝑅 , while the numerator and denominator of the fraction component remain bounded by 𝐷max .

Theorem 5 (Convergence). Given a ﬁnite set of insertion operations delivered to all replicas, ESBT ensures every replica converges to the same sequence of weights ordered by Deﬁnition 2. Proof Sketch. Weight generation is deterministic and independent of message delivery order. Since every replica eventually receives the same set of operations and applies the same total ordering relation, all replicas construct an identical ordered sequence. Therefore, ESBT guarantees deterministic convergence and satisﬁes Strong Eventual Consistency. Theorems 2 and 5 establish the fundamental correctness properties of ESBT. Theorem 2 guarantees bounded fraction allocation through hierarchical disambiguation, Theorem 3 proves that ESBT weights form a strict total order, Theorem 4 ensures global weight uniqueness, and Theorem5 establishes deterministic convergence across replicas. Together, these properties provide the formal foundation for ESBT and ensure Strong Eventual Consistency in distributed collaborative editing.

7. Asymptotic Complexity The computational cost of ESBT can be analyzed by distinguishing identiﬁer allocation from document integration.

Local Weight Allocation. Generating a new ESBT weight

Proof Sketch. If the mediant fraction satisﬁes the bound 𝐷max , it is uniquely determined by the Stern–Brocot tree and lies strictly between the neighboring fractions. Otherwise, ESBT deterministically reﬁnes the ordering using the sequence number 𝑠𝑛 and, if necessary, the sequence path 𝑠𝑐. Since each reﬁnement preserves the ordering relation, a unique weight is always generated without exceeding the predeﬁned fraction bound.

consists of computing a mediant fraction between two adjacent identiﬁers and, when the bound 𝐷max is reached, activating the successive disambiguation layers (𝑠𝑛, 𝑠𝑐, and ﬁnally 𝛿). Since each allocation performs a bounded number of arithmetic and comparison operations per reﬁnement level, the identiﬁer generation cost grows logarithmically with the search depth. Moreover, the bounded allocation policy limits the size of each identiﬁer component, yielding constant memory overhead per weight.

Theorem 3 (Strict Total Order). The relation < from Definition 2 forms a strict total order on the set of ESBT weights.

Document Integration. The shared document is indexed

Proof Sketch. The ordering relation compares weights hierarchically according to (𝑓 , 𝑠𝑛, 𝑠𝑐, 𝛿). Each component is itself totally ordered: fractions by rational order, sequence numbers by integer order, sequence paths lexicographically, and site identiﬁers deterministically. Consequently, every pair of distinct weights is comparable, establishing a strict total order. Theorem 4 (Weight Uniqueness). Every insertion operation generates a unique ESBT weight. No two distinct insertions can produce the same (𝑓 , 𝑠𝑛, 𝑠𝑐, 𝛿). Proof Sketch. The fraction component uniquely identiﬁes a position whenever a new mediant can be allocated. Concurrent fraction collisions are resolved using the sequence number, followed by the sequence path when necessary, while the site identiﬁer provides a ﬁnal deterministic tiebreaker. Therefore, no two insertions can generate identical ESBT weights. First Author et al.: Preprint submitted to Elsevier

by a Red–Black tree ordered according to ESBT weights. Consequently, searching for an existing weight, inserting a new element, and deleting an existing element all require 𝑂(log 𝑛), where 𝑛 denotes the number of elements of the document . Therefore, both locally generated and remotely received operations are integrated in logarithmic time. In general, ESBT combines bounded identiﬁer allocation with logarithmic-time document operations, making it suitable for large-scale collaborative editing with high concurrency.

8. Performance Evaluation This section evaluates the proposed ESBT approach from two complementary perspectives: (i) the inﬂuence of its allocator parameters on identiﬁer growth and memory consumption, and (ii) its performance relative to representative sequence CRDTs under standard collaborative editing workloads. The ﬁrst experiment investigates the impact of the ESBT Page 11 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing Table 1 ESBT weight size (in MB) under varying base conﬁgurations and worst-case insertion workload. Base 1 000 ops 10 000 ops 100 000 ops 28 0.490 49.900 3202.320 210 0.399 39.992 3999.920 216 0.262 25.129 2501.299 231 − 1 0.152 13.144 1292.735

allocator parameters (base and depth) on identiﬁer size and memory usage. The second experiment compares ESBT with two representative variable-size identiﬁer sequence CRDTs, namely Logoot [4] and LSEQ [12], using the Boundary, Random, and Mixed allocation strategies. The evaluation considers four representative insertion workloads: beginning, end, middle, and random. All experiments were executed on a machine with Processor 12𝑡ℎ Gen Intel® Core™ i9-12900K × 24, OS Name Ubuntu 22.04.5 LTS, and Memory 32.0 GiB. All algorithms were implemented in Java.

8.1. Impact of ESBT Allocator Parameters This experiment evaluates the inﬂuence of the ESBT allocator parameters on weight growth and memory consumption. Since the sequence path (𝑠𝑐) is the only variablelength component of an ESBT weight, the evaluation focuses on the behavior of the N EW SEQ function under the worstcase insertion pattern, namely repeated middle insertions. This workload maximizes identiﬁer reﬁnement by repeatedly extending the sequence path and therefore provides an upper bound on identiﬁer growth.

8.1.1. Experiment Setup The evaluation consists of two phases, each comprising up to 100 000 insertion operations. In the ﬁrst phase, four branching factors (bases) were evaluated: {28 , 210 , 216 , 231 − 1}. These values span small, medium, and large allocation spaces and were used to measure the total memory footprint after 1 000, 10 000, and 100 000 insertions. During this phase, the maximum depth was ﬁxed to 216 in order to isolate the inﬂuence of the branching factor. In the second phase, the best-performing branching factor identiﬁed in Table 1 was retained while varying the maximum depth. The objective was to determine the smallest depth that minimizes the sequence-path length without compromising scalability or identiﬁer allocation. 8.1.2. Results Phase 1. Table 1 reports the memory consumption of ESBT under the worst-case middle-insertion workload for diﬀerent branching factors (bases). The results show a clear inverse relationship between the base value and memory usage. Increasing the base enlarges the available allocation space between adjacent weights, thereby reducing the frequency of sequence path (𝑠𝑐) extensions. After 100 000 insertions, the conﬁguration with base 231 − 1 required 1 293 MB, compared with 3 202 MB for base First Author et al.: Preprint submitted to Elsevier

Table 2 ESBT weight sequence path (𝑠𝑐) depth length under diﬀerent insertion operation count. Operations 1 000 10 000 100 000

Average depth 16.22 161.37 1612.98

Max depth 32 323 3226

28 , corresponding to a memory reduction of approximately 59.6%. The intermediate conﬁgurations (210 and 216 ) exhibit the same trend, indicating that larger branching factors produce shallower identiﬁers and more compact memory representations. Based on these observations, the remaining experiments use a branching factor of 231 − 1, which provides the lowest memory consumption among the evaluated conﬁgurations. Phase 2. Table 2 reports the eﬀect of the maximum depth parameter on the length of the sequence path (𝑠𝑐). The results indicate that the average path length increases much more slowly than the number of insertions. Speciﬁcally, the average path length grows from 16.22 after 1 000 insertions to 1 612.98 after 100 000 insertions, while the maximum observed path length reaches 3 226 under the worst-case workload. These results show that deep sequence paths occur only under extreme repeated insertions at the same logical position, whereas most identiﬁers remain relatively shallow in practice. Although the theoretical maximum depth observed during the experiment is 3 226, a depth limit of 256 proved suﬃcient for all representative collaborative workloads considered in this study. Consequently, the remaining experiments adopt the following parameter conﬁguration: base = 231 − 1 and depth = 256, which provides a favorable trade-oﬀ between memory consumption, identiﬁer compactness, and allocation eﬃciency.

8.2. ESBT versus Baseline Sequence CRDTs This experiment compares the proposed ESBT with representative variable-size identiﬁer sequence CRDTs, namely Logoot [4] and LSEQ [12, 21] using its Boundary, Random, and Mixed allocation strategies. The objective is to evaluate both execution eﬃciency and identiﬁer compactness under identical collaborative editing workloads. Two performance metrics are considered: • Responsiveness, measured as the cumulative time required for identiﬁer generation and operation integration (ms). • Identiﬁer memory footprint, measured as the total memory occupied by position identiﬁers (MB). All measurements were averaged over multiple independent executions under identical JVM conﬁgurations to minimize runtime variability. The benchmark was implemented from scratch within a common Java framework. Although the implementations were inspired by the original Logoot [4] 1 1 https://github.com/t-mullen/logoot-crdt

Page 12 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

and LSEQ [12] 2 implementations, all algorithms were reimplemented using the same software architecture to ensure identical execution conditions and a fair comparison.

8.2.1. Experimental Setup The benchmark simulates a collaborative editing session involving 50 replicas. One replica is designated as the local site and performs both local editing operations and the integration of remote updates. The remaining 49 replicas generate concurrent operations that are asynchronously propagated to the local replica. For each experiment, the total number of operations ranges from 10 000 to 100 000. To maximize concurrency, each remote replica generates an equal share of the workload (e.g., 2 000 operations for a total workload of 100 000 operations). Two editing workloads are evaluated: 1. Insertion-only: 100% insertions. 2. Mixed editing: 80% insertions and 20% deletions. For each workload, three insertion patterns are considered: 1. Beginning: All insertions occur at the start of the document. 2. End: All insertions occur document’s end. 3. Random: Positions are chosen uniformly at random across the document.

Identiﬁer Size Measurement. To ensure a fair comparison, memory measurements exclude the JVM object header and account only for the raw identiﬁer ﬁelds. Under this model, an ESBT weight occupies 20 bytes, excluding the variable-length sequence path, whereas each Logoot/LSEQ identiﬁer component occupies 16 bytes. Consequently, the total identiﬁer size grows proportionally to the number of identiﬁer components generated by each allocation strategy.

Worst-case Middle Insertion. The middle-insertion workload was evaluated using up to 10 000 operations. Beyond approximately 55 000 operations, the Logoot and LSEQ implementations exhausted the available JVM heap due to rapid identiﬁer expansion. Restricting this workload ensures that all approaches can be compared under identical execution conditions. The impact of this behavior is further discussed in Sub-Section 8.3.

8.2.2. Pure (100%) Insertion Workload Results a) Responsiveness Figure 4 compares the responsiveness of ESBT with Logoot and the three LSEQ allocation strategies under a pure insertion workload. Under the Beginning insertion pattern (Figure 4(a)), all baseline approaches exhibit a steady increase in execution time as the number of operations increases. At 100 000 insertions, Logoot and LSEQ-Random require approximately 940 ms, reﬂecting the increasing cost of managing progressively longer identiﬁers. In contrast, ESBT requires only about 61

ms, representing an execution time reduction of approximately 93%. For the End insertion pattern (Figure 4(b)), execution times decrease for all approaches because newly generated identiﬁers remain relatively compact. Nevertheless, Logoot and the LSEQ variants still require approximately 470 ms after 100 000 operations, whereas ESBT remains nearly constant at approximately 55 ms, demonstrating stable allocation and integration performance. The Random insertion pattern (Figure 4(c)) produces the largest performance diﬀerences. Logoot and LSEQ-Random reach approximately 1 000 ms due to increased identiﬁer complexity under highly interleaved insertions. ESBT requires approximately 106 ms, oﬀering 10× lower latency than Logoot and LSEQ variants.

b) Identiﬁer Memory Footprint Figure 5 presents the total identiﬁer memory footprint for the same workloads. Under the Beginning insertion pattern (Figure 5(a)), the memory consumption of Logoot and the LSEQ variants increases steadily as identiﬁer lengths grow, reaching approximately 3.13 MB after 100 000 insertions. In comparison, ESBT increases from approximately 0.156 MB to 1.56 MB, maintaining a substantially smaller memory footprint throughout the experiment. For the End insertion pattern (Figure 5(b)), all approaches produce relatively compact identiﬁers because insertions occur at the document boundary. In this favorable scenario, ESBT identiﬁers are approximately 4 bytes larger than those of Logoot and LSEQ due to the additional metadata associated with the ESBT weight. However, this modest overhead is accompanied by signiﬁcantly lower execution times, as shown in Figure 4(b). The Random insertion pattern (Figure 5(c) ) highlights the scalability of the diﬀerent allocation strategies. Logoot and the LSEQ variants require between 6.3 to 9.3 MB after 100 000 insertions, whereas ESBT remains close to 1.56 MB. This corresponds to a reduction in identiﬁer memory consumption of approximately 75 to 83%, depending on the baseline algorithm. 8.2.3. Mixed (80% Insert + 20% Delete) Workload Results a) Responsiveness Figure 6 reports the responsiveness of the evaluated approaches under a mixed workload consisting of 80% insertions and 20% deletions. Introducing deletion operations reduces the number of active document elements and consequently lowers execution times for all approaches. Nevertheless, the relative performance trends remain unchanged. Under the Beginning insertion pattern (Figure 6(a)), Logoot and the LSEQ variants require approximately 366 ms after 100 000 operations, whereas ESBT completes the same workload in approximately 64 ms. For the End insertion pattern (Figure 6(b)), the baseline approaches stabilize around 220 ms owing to the reduced identiﬁer complexity associated with end insertions. ESBT again exhibits the

2 https://github.com/Chat-Wane/LSEQ

First Author et al.: Preprint submitted to Elsevier

Page 13 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing 1000

500

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

500

250

125

Number of Operations

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

900

Time (ms)

375

Time (ms)

750

1200

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

600

300

Number of Operations

x 10

(a) Beginning insertion pattern.

Number of Operations

x 10

(b) End insertion pattern.

10 4

x 10

Figure 4: Responsiveness time (ms) under diﬀerent insertion patterns and 100% insertion workload. 6

x 10

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

1.75

0.875

LSEQ−Boundary LSEQ−Random LOGOOT LSEQ−Mixed ESBT

1.5

Identifiers Size (Byte)

2.625

x 10

0.5

Number of Operations

x 10

(a) Beginning insertion pattern.

x 10

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

7.5

Identifiers Size (Byte)

3.5

2.5

Number of Operations

(b) End insertion pattern

10 4

x 10

Number of Operations

x 10

Figure 5: Identiﬁer size (MB) under diﬀerent insertion patterns and 100% insertion workload.

lowest execution time, remaining close to 56 ms throughout the experiment. The Random insertion pattern (Figure 6(c)) remains the most demanding scenario. Logoot, LSEQ-Random, and LSEQ-Mixed require approximately 400 ms after 100 000 operations, while ESBT requires only about 107 ms, corresponding to execution-time reductions ranging from approximately 73% to 89%, depending on the baseline considered. These results indicate that the performance advantages of ESBT remain consistent even when insertion and deletion operations are combined.

b) Identiﬁer Memory Footprint Figure 7 compares the total identiﬁer memory footprint under the mixed workload. For the Beginning insertion pattern (Figure 7(a)), Logoot and the LSEQ variants occupy between 1.8 to 1.9 MB after 100 000 operations. ESBT requires approximately 937 KB, reducing identiﬁer memory consumption by about 50%. Under the End insertion pattern (Figure 7(b) ), all approaches maintain relatively compact identiﬁers. ESBT remains approximately 20% larger than the baseline approaches because of its additional identiﬁer metadata. However, this small increase in memory usage is accompanied by substantially lower execution times, as shown in Figure 6(b). For the Random insertion pattern (Figure 7(b)), identiﬁer growth again becomes more pronounced for the baseline algorithms, whose memory footprint ranges from approximately 4.16 to 6.20 MB. ESBT remains close to 1.04 MB, reducing identiﬁer memory consumption by up to 79%.

First Author et al.: Preprint submitted to Elsevier

8.3. Middle-Insertion pattern in pure insertion Workloads The middle-insertion workload represents the worst-case scenario for sequence CRDTs because each new identiﬁer must be allocated strictly between two existing identiﬁers. This workload repeatedly reﬁnes the allocation interval and therefore stresses identiﬁer allocation strategies more than the other insertion patterns. For fairness, the evaluation was limited to 10 000 operations, corresponding to the largest workload that all evaluated algorithms could complete. During preliminary experiments, the baseline implementations were unable to complete larger workloads because of JVM heap exhaustion resulting from rapid identiﬁer growth. Speciﬁcally, Logoot failed beyond approximately 30 000 operations, LSEQ-Boundary and LSEQ-Mixed beyond approximately 40 000 operations, and LSEQ-Random beyond approximately 55 000 operations.

a) Responsiveness Figure 8 compares the responsiveness of ESBT with the evaluated baseline approaches. Execution time increases rapidly for all baseline CRDTs as the number of middle insertions grows. At 10 000 operations, Logoot and LSEQRandom require approximately 380 ms, whereas LSEQBoundary and LSEQ-Mixed exceed 700 ms. This behavior is consistent with the increasing complexity of identiﬁer allocation and comparison under repeated midpoint insertions. In contrast, ESBT increases from approximately 5 ms at 1 000 operations to only 52 ms at 10 000 operations.

Page 14 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing 400

250

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

200

100

125

62.5

Number of Operations

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

337.5

Time (ms)

187.5

Time (ms)

300

450

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

225

112.5

Number of Operations

x 10

(a) Beginning 80% insertion pattern.

Number of Operations

x 10

(b) End 80% insertion pattern.

10 4

x 10

Figure 6: Responsiveness time (ms) under diﬀerent insertion patterns and Mixed workloads. 6

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

x 10

LSEQ−Boundary LSEQ−Random LOGOOT LSEQ−Mixed ESBT

Identifiers Size (Byte)

1.5

0.5

x 10

Number of Operations

10 4

x 10

(a) Beginning 80% insertion pattern.

x 10

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

5.25

Identifiers Size (Byte)

3.5

1.75

Number of Operations

(b) End 80% insertion pattern.

x 10

Number of Operations

x 10

Figure 7: Identiﬁer size (MB) under diﬀerent insertion patterns and Mixed workload.

Compared with the baseline approaches, ESBT reduces execution time by approximately 86 to 93%, corresponding to a speedup ranging from 7× to 14×, depending on the allocation strategy.

b) Identiﬁer Memory Footprint Figure 8(b) reports the total identiﬁer memory footprint under the same workload. Repeated middle insertions produce rapid identiﬁer growth in all baseline approaches. At 10 000 operations, LSEQ-Boundary and LSEQ-Mixed require more than 8 MB of identiﬁer storage, whereas Logoot and LSEQ-Random require approximately 4.2 MB. These results explain why the baseline implementations were unable to complete larger workloads within the available JVM heap. In comparison, ESBT maintains a substantially smaller memory footprint, increasing from approximately 0, 015 MB at 1 000 operations to 0, 298 MB at 10 000 operations. This corresponds to a reduction in identiﬁer memory consumption ranging from approximately 93% to 96% (or 13× to 27× smaller) relative to the evaluated baseline approaches. These results demonstrate that the bounded identiﬁer allocation strategy of ESBT eﬀectively limits identiﬁer growth under repeated midpoint insertions, making it well suited for highly adversarial collaborative editing workloads. 8.3.1. Discussion The experimental results consistently show that ESBT achieves lower execution time and smaller identiﬁer memory footprints than the evaluated sequence CRDTs across all workloads. The largest improvements are observed under the Beginning, Random, and Middle insertion patterns, where First Author et al.: Preprint submitted to Elsevier

identiﬁer growth becomes the dominant factor aﬀecting the performance of existing variable-size identiﬁer allocation strategies. The observed performance improvements originate from two complementary design choices. First, ESBT bounds the growth of the fraction component through the parameter 𝐷max and delegates further disambiguation to successive identiﬁer layers only when necessary. Consequently, identiﬁer expansion remains proportional to the actual level of contention rather than to the number or locality of insertions. Second, storing document elements in a Red–Black tree preserves logarithmic-time 𝑂(log 𝑛) search, insertion, and deletion, allowing the execution time to remain stable even as the document size increases. Under the End insertion workload, ESBT exhibits a modest increase in identiﬁer size compared with the best-performing baseline. This diﬀerence is primarily due to the current prototype implementation, which explicitly stores the sequencepath ﬁeld even when it contains only its default value (𝑠𝑐 = [0]). Since this default value can be represented implicitly during serialization and reconstructed during deserialization, the additional storage cost is implementation-speciﬁc rather than intrinsic to the ESBT allocation strategy. In contrast, the growth observed in Logoot and LSEQ identiﬁers is an inherent property of their allocation mechanisms. As concurrent insertions repeatedly target the same allocation interval, additional identiﬁer components are introduced to preserve ordering, progressively increasing both memory consumption and comparison costs. This behavior becomes particularly pronounced under adversarial middle-insertion workload, where ESBT reduces execution time by up to Page 15 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing 6

800

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

400

200

0 1000

LSEQ−ALTERNATE LSEQ−HYBRID LOGOOT LSEQ−RANDOM ESBT

Identifiers Size (Byte)

Time (ms)

600

x 10

2000

3000

4000

5000

6000

7000

8000

9000

10000

Number of Operations

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

Number of Operations

(a) Responsiveness time under 100% middle- (b) Identiﬁer size under 100% middle-position inposition insertions sertions

Figure 8: ESBT and baseline CRDTs performance under a middle-insertion pattern with pure insertion workloads.

86.5% and identiﬁer memory consumption by up to 92.8% relative to the evaluated baselines. Finally, ESBT can be naturally extended to support very large-scale collaborative editing environments. The current implementation of fraction 𝑓 uses 32-bit integers, which are suﬃcient for the workloads evaluated in this paper. Extending these fraction ﬁelds to 64-bit integers would substantially enlarge the available identiﬁer space, allowing much deeper mediant reﬁnement before reaching the 𝐷max bound, without modifying the ESBT allocation algorithm, its correctness guarantees, or its asymptotic complexity.

9. Related Works Several sequence CRDTs have been proposed for collaborative editing. Each aims to maintain a consistent order of elements inserted simultaneously while avoiding centralized coordination. This section reviews representative approaches and discusses their respective strengths and limitations. WOOT (WithOut Operational Transforms) [22] is considered as the ﬁrst based-CRDT algorithm proposed in literature. In WOOT, each element of a text document is associated with a unique structure comprising its identiﬁer, its content, and the identiﬁers of its predecessor and successor elements. WOOT uses a monotonic linearization function to maintain convergence between sites, but does not allow the deletion of elements, which introduces additional memory and communication overhead as deleted elements accumulate over time. To address this issue, WOOT uses the tombstone technique [11], where deleted elements are retained but made invisible to users. However, this approach can lead to memory and bandwidth overhead problems [7]. Improved versions WOOTO [22] and WOOTH [23] have been proposed, but they only optimize integration complexity from 𝑂(𝑛3 ) to 𝑂(𝑛2 ) where 𝑛 denotes the number of elements. In [24], the authors provide a formal proof that WOOT achieves strong eventual consistency and propose size-optimized messages for update operations using a sort key-based protocol. TreeDoc [25] is a CRDT that uses a binary tree to represent the document. Each node of the tree contains an element and two children (left and right). Each node has a unique First Author et al.: Preprint submitted to Elsevier

identiﬁer which is its path in the tree. The content of node is represented by the inﬁx path of the tree. However, when many insertions occur near the end of the document, which is the normal editing situation, repeated localized insertions may increase tree depth and identiﬁer length. TreeDoc uses tombstone as it cannot delete a node that already has a children. But it can safely delete nodes that does not have any visible children. Moreover, maintaining balance and reclaiming tombstones may incur additional synchronization overhead in large-scale collaborative environments. Logoot [4] is a CRDT that considers a document as a set of lines all identiﬁed by absolute positions totally order using lexicographic order. These identiﬁers are only used once, meaning they cannot be reused. Logoot document consists of lines deﬁned as <pid, content> where the content is a line of text and the pid is a unique position identiﬁer. Logoot does not use tombstone for hiding deleted elements, it removes physically the elements form its document. However, when several insertions are applied in the same part of the document, the generated identiﬁers for these insertions progressively exhaust the available identiﬁer space. This leads to increasingly long identiﬁers and higher comparison costs. LSEQ [12, 21] reﬁnes Logoot’s identiﬁer allocation by using diﬀerent identiﬁer allocation strategies adapted to diﬀerent editing patterns. LSEQ combines two classical strategies: a Random allocator, which disperses identiﬁers uniformly within available intervals, and a Boundary allocator, which selects positions at interval extremities. While Random strategy enhances distribution fairness, Boundary strategy provides predictability at the cost of accelerated identiﬁers growth under high concurrency. LSEQ introduces an adaptive round-robin policy that alternates between these strategies to balance dispersion and stability while reducing identiﬁer depth compared to either strategy alone. Despite these improvements, LSEQ still suﬀers from unbounded identiﬁer growth under intense editing, path expansion in highly concurrent regions, and workload sensitivity, since boundary-heavy scenarios or repeated midpoint insertions can still produce long identiﬁer paths that degrade memory footprint and integration responsiveness. Also, LSEQ does not ensure deterministic and bounded identiﬁer allocation since it relies on several antagonist allocation strategies. Page 16 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing Table 3 Comparison of representative sequence CRDT algorithms. Algorithm

Complexity Local

Remote

WOOT [8] TreeDoc [25]

𝑂(𝑛) 𝑂(𝑛)

𝑂(𝑛2 ) 𝑂(𝑛 log 𝑛)

Logoot [4] LSEQ [12] RGA [9] Eg-Walker [27] ESBT

𝑂(𝑛) 𝑂(𝑛) 𝑂(𝑛) 𝑂(log 𝑛) 𝐎(log 𝐧)

𝑂(𝑛 log 𝑛) 𝑂(𝑛 log 𝑛) 𝑂(log 𝑛) 𝑂(log 𝑛) 𝐎(log 𝐧)

Data Structure Array List Extended Binary Tree Array List Array List Linked List B-Tree Red-Black Tree

Tombstone Based

GC Required

Identiﬁer Size

Metadata Overhead

Yes Yes

Fixed Variable

High High

No No Yes Yes No

Variable Variable Fixed Fixed Variable

High Medium High Low Low

Metadata overhead qualitatively reﬂects the amount of auxiliary information maintained by each algorithm, including tombstones, identiﬁer expansion, and synchronization metadata. Identiﬁer size characterizes the evolution of position identiﬁers: Fixed denotes constant-size identiﬁers, whereas Variable denotes identiﬁers whose size may increase depending on insertion patterns and editing workloads.

Therefore, without coordination among collaborators, identiﬁers can grow quadratically in size [26]. RGA (Replicated Growable Array) [9] is a linked-list data ordered consistently with the happened-before relation. Each element is assigned a unique timestamp-based identiﬁer (s4vector). RGA uses a hash table maps identiﬁers to document elements for eﬃcient lookup and conﬂict resolution. RGA uses tombstones to preserve ordering after deletions, and its correctness has been formally established in [7]. However, its message size grows with the number of replicas and update operations. Several extensions, including PRGA [28] and Fugue [29], have been proposed to improve performance, But still rely on tombstones, incurring metadata and garbage-collection overhead. Eg-walker [27] introduces a hybrid approach that combines principles of Operational Transformation (OT) and Conﬂictfree Replicated Data Types (CRDTs) that embeds editing updates operations as a directed acyclic graph (DAG) to maintain causal relations among operations. Eg-Walker constructs a causality-preserving walk over the DAG to derive a consistent total order, eliminating the need for variablelength identiﬁers as used in Logoot or LSEQ. However, EgWalker inherits several limitations associated with DAGbased representations including unbounded DAG growth, complex garbage collection, expensive graph traversal during integration, and high memory consumption under intense concurrent workloads which makes it less suitable for large-scale and long-lived collaborative documents. Table 3 summarizes the main characteristics of representative sequence CRDTs, comparing their computational complexity, underlying data structures, tombstone management, garbage collection (GC) requirement, identiﬁer behavior and metadata overhead. Existing approaches can generally be categorized according to their ordering strategy. Tombstonebased CRDTs maintain deleted elements to preserve ordering, which increases metadata size and may require garbage collection (GC) to reclaim obsolete state. For example, WOOT stores predecessor and successor references together with tombstones for each deleted element. RGA also maintains tombstones and additional timestamp-based identiﬁers First Author et al.: Preprint submitted to Elsevier

to preserve causal ordering. In contrast, identiﬁer-allocation approaches (e.g., Logoot and LSEQ) eliminate tombstones but may suﬀer from identiﬁer growth under unfavorable insertion patterns, increasing both memory consumption and comparison costs. These pathological insertion patterns may also be deliberately generated by an adversarial participant to inﬂate identiﬁer size and degrade system performance. ESBT maintains low metadata overhead by storing only the weight and a lightweight synchronization counter, without tombstones or auxiliary ordering structures. ESBT belongs to the second category but introduces a bounded Stern–Brocot-based identiﬁer allocation strategy with logarithmic-time operations through its integration with a self-balanced Red–Black tree. The eﬀectiveness of these design choices is quantitatively evaluated in Section 8 through execution time and memory consumption experiments under representative collaborative editing workloads.

10. Conclusion In this paper, we proposed ESBT, a novel sequence CRDT that addresses the scalability limitations of existing identiﬁer-allocation approaches for collaborative editing. ESBT combines deterministic identiﬁer allocation with eﬃcient synchronization, providing bounded identiﬁer growth, tombstone-free deletion management, and logarithmic-time document operations. Experimental results demonstrate that ESBT consistently reduces identiﬁer memory consumption and execution time compared with representative sequence CRDTs, including Logoot [4] and LSEQ [12, 21], across diverse collaborative editing workloads. The proposed approach also maintains stable performance under challenging insertion patterns while preserving deterministic ordering and Strong Eventual Consistency. Future work will focus on four directions. First, we will investigate adaptive mechanisms for automatically tuning the 𝐷max parameter according to observed editing dynamics and workload characteristics. Second, we will explore compact encoding and serialization techniques for the sequence path to further reduce identiﬁer storage requirements. Third, Page 17 of 18

ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing

we plan to integrate ESBT as a pluggable identiﬁer allocation strategy into existing collaborative editing frameworks, such as Yjs3 and Automerge4, and evaluate its eﬀectiveness under real-world collaborative workloads. Finally, we will investigate the behavior and performance of ESBT under adverse network conditions, including network partitions, prolonged disconnections, and replica recovery, to further assess its robustness in large-scale distributed collaborative environments.

References [1] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558–565, 1978. doi: 10.1145/359545.359563. [2] Friedemann Mattern. Virtual time and global states of distributed systems. In Cosnard M. et al., editor, Proc. Workshop on Parallel and Distributed Algorithms, pages 215–226, North-Holland, 1989. [3] Abdessamad Imine, Michael Rusinowitch, Gérald Oster, and Pascal Molli. Formal design and veriﬁcation of operational transformation algorithms for copies convergence. Theoretical Computer Science, 351(2):167–183, 2006. doi: https://doi.org/10.1016/j.tcs.2005.09. 066. [4] Stéphane Weiss, Pascal Urso, and Pascal Molli. Logoot: A scalable optimistic replication algorithm for collaborative editing on p2p networks. In ICDCS, pages 404–412, 2009. [5] Paulo Sérgio Almeida. Approaches to conﬂict-free replicated data types. ACM Comput. Surv., 57(2), 2024. doi: 10.1145/3695249. [6] António Barreto, Hervé Paulino, João A. Silva, and Nuno Preguiça. Ps-crdts: Crdts in highly volatile environments. Future Generation Computer Systems, 141:755–767, 2023. doi: https://doi.org/10.1016/ j.future.2022.12.013. [7] Victor B. F. Gomes, Martin Kleppmann, Dominic P. Mulligan, and Alastair R. Beresford. Verifying strong eventual consistency in distributed systems. Proc. ACM Program. Lang., 1(OOPSLA), 2017. doi: 10.1145/3133933. [8] Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine. Data consistency for P2P collaborative editing. In Proceedings of the 2006 ACM Conference on Computer Supported Cooperative Work, CSCW 2006, Banﬀ, Alberta, Canada, pages 259–268. ACM, 2006. doi: 10.1145/1180875.1180916. [9] Hyun-Gul Roh, Myeongjae Jeon, Jinsoo Kim, and Joonwon Lee. Replicated abstract data types: Building blocks for collaborative applications. J. Parallel Distributed Comput., 71(3):354–368, 2011. doi: 10.1016/J.JPDC.2010.12.006. [10] Pengcheng Zhang, Zhongbo Shao, Lin Xu, Jingju Gao, Tian Yu, Jifa Chen, and Ling Hu. Geo-crdt: Geometry-aware collaborative spatial editing with robust topology preservation. ISPRS International Journal of Geo-Information, 15(7), 2026. doi: 10.3390/ijgi15070302. [11] Gérald Oster, Pascal Molli, Pascal Urso, and Abdessamad Imine. Tombstone transformation functions for ensuring consistency in collaborative editing systems. In CollaborateCom, pages 1–10, 2006. doi: 10.1109/COLCOM.2006.361867. [12] Brice Nédelec, Pascal Molli, Achour Mostéfaoui, and Emmanuel Desmontils. LSEQ: an adaptive structure for sequences in distributed collaborative editing. In ACM Symposium on Document Engineering 2013, DocEng ’13, Florence, Italy, pages 37–46, 2013. doi: 10.1145/ 2494266.2494278. [13] Bruce Reznick. The stern-brocot tree. American Mathematical Monthly, 97(5):395–402, 1990. [14] Milad Niqui. Exact arithmetic on the stern–brocot tree. Journal of Discrete Algorithms, 5(2):356–379, 2007. doi: https://doi.org/10. 1016/j.jda.2005.03.007.

[15] Nadir Guetmi, Abdessamad Imine, and Moulay Driss Mechaoui. Mobirdf: A cloud-based collaborative editing service for mobile rdf data sharing. Journal of Web Semantics, 86:100864, 2025. ISSN 1570-8268. doi: https://doi.org/10.1016/j.websem.2025.100864. [16] Chengzheng Sun, Xiaohua Jia, Yanchun Zhang, Yun Yang, and David Chen. Achieving Convergence, Causality-preservation and Intentionpreservation in real-time Cooperative Editing Systems. ACM Trans. Comput.-Hum. Interact., 5(1):63–108, 1998. doi: 10.1145/274444. 274447. [17] N. M. Pregui, J. M. Marqu, M. Shapiro, and M. Letia. A commutative replicated data type for cooperative editing. In ICDCS, pages 395– 403, 2009. [18] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Cliﬀord Stein. Introduction to algorithms. MIT Press, 4th edition, 2022. [19] Ajay D. Kshemkalyani and Mukesh Singhal. Necessary and suﬃcient conditions on information for causal message ordering and their optimal implementation. Distrib. Comput., 11(2):91–111, 1998. doi: 10.1007/s004460050044. [20] P. Th. Eugster, R. Guerraoui, S. B. Handurukande, P. Kouznetsov, and A.-M. Kermarrec. Lightweight probabilistic broadcast. ACM Trans. Comput. Syst., 21(4):341–374, November 2003. ISSN 0734-2071. doi: 10.1145/945506.945507. [21] Brice Nédelec, Pascal Molli, and Achour Mostéfaoui. A scalable sequence encoding for collaborative editing. Concurr. Comput. Pract. Exp., 33(8), 2021. doi: 10.1002/CPE.4108. [22] Stéphane Weiss, Pascal Urso, and Pascal Molli. Wooki: A P2P wiki-based collaborative writing tool. In Web Information Systems Engineering - WISE 2007, Nancy, France, volume 4831 of Lecture Notes in Computer Science, pages 503–512. Springer, 2007. doi: 10.1007/978-3-540-76993-4\_42. [23] Mehdi Ahmed-Nacer, Claudia-Lavinia Ignat, Gérald Oster, HyunGul Roh, and Pascal Urso. Evaluating crdts for real-time document editing. In Proceedings of the 2011 ACM Symposium on Document Engineering, Mountain View, CA, USA, September 19-22, 2011, pages 103–112. ACM, 2011. doi: 10.1145/2034691.2034717. [24] Emin Karayel and Edgar Gonzàlez. Strong eventual consistency of the collaborative editing framework woot. Distributed Computing, 35:145–164, 2022. doi: 10.1007/s00446-021-00414-6. [25] 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 2009), Montreal, Québec, Canada, pages 395–403, 2009. doi: 10.1109/ICDCS.2009.20. [26] Brice Nédelec, Pascal Molli, Achour Mostéfaoui, and Emmanuel Desmontils. Concurrency eﬀects over variable-size identiﬁers in distributed collaborative editing. In Proceedings of the International workshop on Document Changes: Modeling, Detection, Storage and Visualization, Florence, Italy, 2013. [27] Joseph Gentle and Martin Kleppmann. Collaborative text editing with eg-walker: Better, faster, smaller. In Proceedings of the Twentieth European Conference on Computer Systems, EuroSys 2025, Rotterdam, The Netherlands, pages 311–328, 2025. doi: 10.1145/3689031. 3696076. [28] Weiwei Cai, Fazhi He, and Xiao Lv. Multi-core accelerated crdt for large-scale and dynamic collaboration. The Journal of Supercomputing, 78:10799–10828, 2022. doi: 10.1007/s11227-022-04308-7. [29] Matthew Weidner and Martin Kleppmann. The art of the fugue: Minimizing interleaving in collaborative text editing. IEEE Trans. Parallel Distributed Syst., 36(11):2425–2437, 2025. doi: 10.1109/ TPDS.2025.3611880.

3 https://docs.yjs.dev/api/internals 4 https://automerge.org/

First Author et al.: Preprint submitted to Elsevier

Page 18 of 18

Record · ID 414078 · SHA-256 8df7e817c50d2390
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.