The Cost of Purity: Scalability Challenges in the Pure Operation-Based CRDT Framework
TL;DR
A systematic analysis of the time and space complexity challenges of the pure operation-based CRDT framework is presented, identifying performance bottlenecks in causality tracking, timestamp representations, partially ordered logs, redundancy evaluation, query execution, and causal stability detection.
Abstract
: Conflict-free Replicated Data Types (CRDTs) are widely used to build fault-tolerant, highly available distributed systems, including collaborative applications ( e.g ., text editors), Local-First software, and distributed databases. The pure operation-based CRDT framework was introduced to simplify the design, implementation, and verification of replicated data types by cleanly separating communication concerns from data-type semantics. However, its scalability implications remain unexplored. This paper presents a systematic analysis of the time and space complexity challenges of the framework, identifying performance bottlenecks in causality tracking, timestamp representations, partially ordered logs, redundancy evaluation, query execution, and causal stability detection. We discuss practical mitigation strategies and design trade-offs, showing that while the framework is conceptually sound, achieving efficient implementations requires substantial engineering effort. We report preliminary results demonstrating the effectiveness of the proposed mitigation strategies.