Large distributed systems often rely on geo-replication, replicating data across geographically dispersed data centers. This technique offers several advantages, including lower latency, im- proved fault tolerance, and higher availability for users. In addition to performance improve- ments, the ability of replicas to remain available during network partitions is often desirable. However, achieving availability under partitioning comes at the cost of weakening the system’s consistency guarantees. In many distributed systems, though, strong consistency is not a strict requirement, making this trade-off acceptable.

Conflict-free Replicated Data Types (CRDTs) are abstract data types designed to meet these availability needs. Replicas in a CRDT system can be independently queried and updated with- out coordination, resulting in high availability. CRDTs provide a Strong Eventual Consistency guarantee: all replicas that have received the same updates will eventually reach equivalent states. From a programmer’s perspective, CRDTs offer a simple interface and out-of-the-box convergence, abstracting away much of the complexity of distributed replication. Developers need only reason about the operations defined by the interface, while the underlying system handles synchronization and consistency.

To ensure convergence, many CRDT designs use specialized metadata to track the causality of operations. This, however, introduces a computational overhead as metadata must be main- tained locally at each replica and transmitted across the network, resulting in increased memory usage and communication costs. In particular, operation-based CRDTs often rely on reliable and causally ordered message delivery, requiring the use of vector clocks, buffers, counters, and unique identifiers. These structures are stored at each replica and included with every mes- sage exchanged between replicas. The pure operation-based framework [1] introduces several concepts that help limit such overhead. In this model, replicas transmit only operations and their arguments, maintaining a partially ordered log (PO-log) of operations and their times- tamps. Through redundancy mechanisms the PO-log is kept as small as possible to minimize the CRDT’s state. Although effective in shrinking the CRDT’s overall state size in the memory of a replica, this approach does require some additional memory usage for the maintenance of its causal stability oracle. Other existing work has explored optimizations on CRDTs, but often in an ad-hoc manner or targeting large-scale cloud systems, rather than constrained environments.

As part of a master’s thesis at the Distribution and Concurrency (DisCo) Research Group within the Software Languages Lab (SOFT) at Vrije Universiteit Brussel (VUB), we explored how CRDTs could be brought to low-memory edge computing devices. In particular, we focused on executing CRDT applications on microcontrollers such as the ESP32-based M5StickC, featuring just 520KB of SRAM and a 240MHz dual-core processor. To enable this, we propose a two-fold solution:

First, we improve upon traditional causality tracking by proposing a new delta vector clock de- sign that integrates with the pure operation-based CRDT framework. Vector clocks, commonly used to track causality, scale poorly with the number of replicas, consuming increasing amounts of memory and bandwidth. Furthermore, transmitting vector clocks often carries redundant information. Delta vector clocks, proposed by Singhal et al., mitigate this issue by sending only the necessary clock entries (the deltas). However, the original delta vector clock design was not built for causal order delivery and introduced a prohibitive O(n^2) memory overhead where n is the number of replicas. This overhead comes in the form of buffers that are re- quired to maintain the delta vector clocks. As a contribution, we propose an extended version of this approach that integrates with the pure operation-based CRDT framework, and reduces overhead by reusing existing bookkeeping mechanisms that are needed by the causal stability determination algorithms of the pure-op framework. This reduces the additional overhead of delta vector clocks to O(n).

Second, we developed a low-level CRDT framework in C, explicitly optimized for memory- constrained environments. The framework provides abstractions that help developers define and implement new CRDT types with minimal overhead. In addition, it employs a modular networking stack, where all communication passes through independent middleware layers, each responsible for providing specific messaging guarantees. Messages move from the application layer to a reliable broadcasting layer, which ensures exactly-once, reliable FIFO delivery using acknowledgments and buffers. Subsequently, messages pass through a tagged causal delivery layer, which maintains vector clocks and buffers out-of-order messages to guarantee causal or- dering. Each middleware layer serializes its required metadata into a shared buffer, which is then transmitted over the network. Upon reception, replicas deserialize the byte array and sequentially process the message through the corresponding middleware layers, independently enforcing their respective guarantees.

Thanks to its modular design, the framework also facilitates evaluation of the delta vector clock optimization. The standard tagged causal broadcasting layer can be replaced with an optimized version that uses delta vector clocks. Preliminary evaluations on arrays of microcontrollers show promising results. Messages transmitted between replicas are significantly smaller when using the optimized causality tracking compared to traditional vector clock approaches.