Many applications model their data in a general-purpose storage format such as JSON. This data structure is modified by the application as a result of user input. Such modifications are well understood if performed sequentially on a single copy of the data, but if the data is replicated and modified concurrently on multiple devices, it is unclear what the semantics should be. In this paper we present an algorithm and formal semantics for a JSON data structure that automatically resolves concurrent modifications such that no updates are lost, and such that all replicas converge towards the same state (a conflict-free replicated datatype or CRDT). It supports arbitrarily nested list and map types, which can be modified by insertion, deletion and assignment. The algorithm performs all merging client-side and does not depend on ordering guarantees from the network, making it suitable for deployment on mobile devices with poor network connectivity, in peer-to-peer networks, and in messaging systems with end-to-end encryption.
Conflict-Free Replicated Data Types
Replicating data under Eventual Consistency (EC) allows any replica to accept updates without remote synchronisation. This ensures performance and scalability in large-scale distributed systems (e.g., clouds). However, published EC approaches are ad-hoc and error-prone. Under a formal Strong Eventual Consistency (SEC) model, we study sufficient conditions for convergence. A data type that satisfies these conditions is called a Conflict-free Replicated Data Type (CRDT). Replicas of any CRDT are guaranteed to converge in a self-stabilising manner, despite any number of failures. This paper formalises two popular approaches (state- and operation-based) and their relevant sufficient conditions. We study a number of useful CRDTs, such as sets with clean semantics, supporting both add and remove operations, and consider in depth the more complex Graph data type. CRDT types can be composed to develop large-scale distributed applications, and have interesting theoretical properties.
An Algebraic Approach to Bi-directional Updating
In many occasions would one encounter the task of maintaining the consistency of two pieces of structured data that are related by some transform — synchronising bookmarks in different web browsers, the source and the view in an editor, or views in databases, to name a few. This paper proposes a formal model of such tasks, basing on a programming language allowing injective functions only. The programmer designs the transformation as if she is writing a functional program, while the synchronisation behaviour is automatically derived by algebraic reasoning. The main advantage is being able to deal with duplication and structural changes. The result will be integrated to our structure XML editor in the Programmable Structured Document project.
The CRDT Dictionary: A Field Guide to Conflict-Free Replicated Data Types - Ian Duncan
A comprehensive guide to CRDTs and their tradeoffs, from counters to sequences. Written in the spirit of the Typeclassopedia, exploring how different CRDTs solve the distributed consensus puzzle.
Composing capability security and conflict-free replicated data types — Spritely Institute
In August, I attended the DWeb Seminar where a small group of builders gathered to discuss the state-of-the-art and open problems in the distributed web space. Some in the group are primarily concerned with distributed data and focus on sync algorithms and local-first use cases. I am mainly concerned with distributed behavior and focus on the object capability security model. Both areas of study are steeped in their own lore and research papers, which makes it difficult for the two camps to communicate effectively with each other.
A Categorical Theory of Patches
When working with distant collaborators on the same documents, one often uses a version control system, which is a program tracking the history of files and helping importing modifications brought by others as patches. The implementation of such a system requires to handle lots of situations depending on the operations performed by users on files, and it is thus difficult to ensure that all the corner cases have been correctly addressed. Here, instead of verifying the implementation of such a system, we adopt a complementary approach: we introduce a theoretical model, which is defined abstractly by the universal property that it should satisfy, and work out a concrete description of it. We begin by defining a category of files and patches, where the operation of merging the effect of two coinitial patches is defined by pushout. Since two patches can be incompatible, such a pushout does not necessarily exist in the category, which raises the question of which is the correct category to represent and manipulate files in conflicting state. We provide an answer by investigating the free completion of the category of files under finite colimits, and give an explicit description of this category: its objects are finite sets labeled by lines equipped with a transitive relation and morphisms are partial functions respecting labeling and relations.
Go sync.Map: The Right Tool for the Right Job
Go’s sync.Map isn’t a magic bullet for all concurrent map needs. It’s got some good tricks up its sleeve, like handling reads without locking, but it’s not always the best choice. This article dives into how sync.Map works under the hood, from its two-map system to the bottom line of expunged entries.
Preserving Order in Concurrent Go Apps: Three Approaches Compared
Concurrency breaks ordering by design, but sometimes we need both. Explore three methods to preserve order in concurrent Go applications, from standard ReplyTo channels to sophisticated permission passing, with benchmarks and real-world trade-offs.
Protocol Buffers
Protocol Buffers are language-neutral, platform-neutral extensible mechanisms for serializing structured data.
Cambria | Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data
This summary was generated using automated tools and was not authored or reviewed by the article's author(s). It is provided to support discovery, help readers assess relevance, and assist readers from adjacent research areas in understanding the work. It is intended to complement the author-supplied abstract, which remains the primary summary of the paper. The full article remains the authoritative version of record. Click here to learn more.
Willow - Willow’25
Peer-to-peer protocols which scale up, down, and sideways. Sychronisable data storage, fine-grained access control, private and efficient synchronisation, and secure data delivery by any means possible.
Permissioned Data Diary 2: Buckets - Daniel's Leaflets
The second in a series of posts building up a solution to permissioned data on atproto. We introduce buckets: a new protocol primitive for creating a shared social context.
new data diary! this is the most in the weeds yet, all revolving around our proposed URI structure for permissioned data. turns out you can figure out a lot about a protocol from the uri! as always, let me know what you think :)
Permissioned Data Diary 5: What’s in a Name?
dholms.leaflet.pub