The Long Convergence: What Became of the CRDT Idea

The Intellectual Genealogy of Conflict-Free Replicated Data Types

Concept by Carlos Baquero · Execution by Claude agents — August 2026 · PDF edition

Seed paper: Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. “Conflict-Free Replicated Data Types.” SSS 2011, LNCS 6976, pp. 386–400.

1The Original Intervention

Eventual consistency makes a simple promise: replicas of the data are allowed to diverge for a while but, once updates stop, all of them will reach the same state. By the late 2000s this promise had become industrial practice. Following the CAP trade-off, large services had learned to live with divergent replicas that would be reconciled at some later time. Amazon's Dynamo had also shown that reconciliation has its own subtle failure modes: deleted items reappeared in shopping carts. The building blocks were all available (version vectors, anti-entropy, last-writer-wins), but what was missing was a general criterion, a way of knowing in advance that a given replicated object would indeed converge. The 2011 papers were quite direct about this state of affairs: "published EC approaches are ad-hoc and error-prone."

If we ask where CRDTs came from, the standard answer is that they "emerged from distributed systems research in 2011." It is a convenient summary, but on two counts the historical record tells a different story. Next, we revisit both.

Old components

Let us start with the components, which were considerably older than the assembled machine. The last-writer-wins register already appears in 1976, in an RFC by Johnson and Thomas on duplicate databases. The tombstone sets and the stability algorithm date back to the replicated logs and dictionaries of Wuu and Bernstein, in 1984. The delivery substrate comes from the epidemic protocols introduced by Demers and colleagues in 1987. As for the semilattice idea, the mathematical core of the state-based approach, it was formulated in 1997 by Baquero and Moura, in a technical report from the University of Minho on convergent abstract data types for mobile computing. At the time, that report went mostly unnoticed. There is no dispute over this inheritance; the 2011 papers acknowledge it in plain terms: "The foundations of CvRDTs were introduced by Baquero and Moura. We extend their work with CmRDTs and a number of new results."

A detour through collaborative editing

The second correction is less well remembered. CRDTs did not begin inside distributed systems research; they began in collaborative editing, and they began with a failure. Since the work of Ellis and Gibbs in 1989, collaborative editors had been built on Operational Transformation (OT): each site executes its own operations immediately, and incoming remote operations are transformed to compensate. In 2005, Oster, Urso, Molli and Imine used an automated theorem prover to check the transformation functions that had been published for strings, and found them all to be incorrect. A way out was needed, and one of the candidates was somewhat radical: give up on transforming operations, and instead design the operations so that they commute. Their 2006 system WOOT took exactly that route, with unique identifiers and tombstones, and dispensing with vector clocks. The title makes the intention clear: "Real-Time Group Editors Without Operational Transformation."

The future CRDT authors were working on the same problem. Shapiro and Preguiça's Treedoc was a replicated sequence aimed at cooperative editing, and it was for Treedoc that the term "commutative replicated data type", the first expansion of the acronym, was coined. The editing groups and the CRDT authors kept in contact throughout, by citation and also through informal channels that leave no trace in citation databases: in the 2011 catalogue, two of the constructions are credited to Roh, and to Molli, Weiss and Skaf, via "private communication."

Two steps to a synthesis

The synthesis itself arrived in two steps, six months apart. In January 2011, the technical report "A comprehensive study of Convergent and Commutative Replicated Data Types" gathered around twenty specifications, among them the G-Counter, PN-Counter, LWW-Register, MV-Register, 2P-Set and OR-Set, plus graphs and sequences, and settled, on the theory side, for "quiescent consistency." In July, the companion paper, later published at SSS, kept the acronym but gave it a new expansion, "Conflict-free". It defined Strong Eventual Consistency (SEC), proved two sufficient conditions for achieving it (either the replica states form a monotonic semilattice, or concurrent operations commute under causal delivery), proved the equivalence of the two styles, and claimed "a solution to the CAP problem." Interestingly, while the acronym remained stable from the very beginning, the expansion behind it changed three times in the space of four years. "Quiescent consistency" survived for only six months; the authors themselves retired it in their next paper.

Neighbours, not descendants

Not every contemporary work belongs in this family tree, and two cases deserve mention because they sit just outside it. Roh and colleagues in Korea had "independently developed the Replicated Abstract Data Type concept, which is quite similar to CRDT"; the 2011 papers acknowledge the parallel invention, and the RGA construction was welcomed into the catalogue. And at SOSP, in the autumn of the same year, the COPS system defined causal+ consistency, the combination of causal consistency with convergent conflict handling. COPS cites no paper from the CRDT cluster. It grew in parallel from common ancestors, Bayou and Dynamo, and it was left to later observers to point out the family resemblance to SEC. As so often in the history of science, the same problem was maturing in several places at once.

What the 2011 papers contributed was therefore not a first spark. It was a synthesis: older components, a hard lesson learned in a neighbouring community, and a mathematical criterion, finally assembled under a single name. In the sections that follow, we trace what the communities that received this synthesis went on to do with it.

2The First Descendants

How does a research community receive a synthesis of this kind? In this case, the reception had three properties worth separating: it was fast, it was broad, and it was surprisingly selective.

Fast and broad are easy to document. Within two years, the citing literature already contained, in miniature, nearly everything that the following decade would develop at scale. Walter brought commutative sets into a transactional geo-replicated store. At Microsoft, Burckhardt's group began treating eventually consistent objects as a programming-language problem. At Berkeley, Hellerstein's group connected the semilattices to its own logic-based work on coordination avoidance. Applications appeared for semantic stores, for file systems, and for trees. Even the CAP discourse, which the paper had explicitly addressed, took notice within a year: Eric Brewer's own retrospective, "CAP Twelve Years Later," cites the work.

The selectivity only becomes visible when one reads the citing sentences instead of just counting them. We examined roughly 2,500 citation-context sentences, and the proportions are instructive. The CAP claim, which the paper lists as its first contribution, appears in about eleven of those sentences. The equivalence theorems are essentially absent. Two-thirds of the citations we could label by intent are background references, typically of the form "special-purpose types like CRDTs." In other words, the citing literature adopted the concept and left the theorems largely untouched. The paper was becoming a landmark that authors salute in passing, rather than a source from which results are taken.

The two-part cluster also produced a reception pattern of its own. During the first five years, the comprehensive technical report was cited nearly as often as the published paper. This makes sense, since what implementers needed was the catalogue rather than the theorems; Akka's documentation links the report's PDF to this day. After 2016, the citations consolidated onto the published paper, and after 2021 even the habit of citing both faded away. In the end, a single canonical reference was left standing.

3The Branching

By the middle of the decade, the descendants can be sorted into distinct research lines. Our count arrives at nine, a number that should be read with some caution: works were assigned to branches from metadata and sampled texts, and the corresponding entry in our evidence ledger remains open.

Two of the lines stayed close to the founding school. The systems line built platforms. SwiftCloud, Cure and AntidoteDB composed CRDTs with causal consistency and transactions; later came the invariants, with Indigo's "explicit consistency" and the Bounded Counter, answering an admission the paper itself had made, that some guarantees require "small doses of synchronisation." The efficiency line went after the costs. Delta-CRDTs propagate semilattice increments rather than full states, and pure operation-based CRDTs reduce the metadata to the bare operations, resorting to causal stability to garbage-collect what is no longer needed. Delta-CRDTs came from Almeida, Shoker and Baquero, the same Baquero of the 1997 report; the line that had opened the state-based idea returned, twenty years later, to repair its costs.

Three other lines built canons of their own, in other communities. The programming-languages line runs from Burckhardt's Cloud Types to the POPL 2014 paper by Burckhardt, Gotsman, Yang and Zawirski, the last of these a bridge author coming from the founding team. The question changed: no longer how to build a convergent object, but how to specify one, using visibility and arbitration relations, in a style reminiscent of weak memory models. The title of that paper deserves a second look: "Replicated Data Types," with no qualifier attached. The verification line starts in 2017, when Gomes, Kleppmann, Mulligan and Beresford mechanized SEC in Isabelle/HOL. Their stated motivation could have been written by any veteran of the OT episode: "many published algorithms have later been shown to be incorrect, even some that were accompanied by supposed mechanised proofs." The line then moved into synthesis, with Katara deriving CRDTs by verified lifting, and into verification languages. And the collaborative-editing line closed a circle: the sequence CRDTs (LSEQ, Yjs, the JSON CRDT, Automerge) returned the framework to peer-to-peer editing, the very problem from which WOOT had set out, and carried it, eventually, into mainstream software.

The remaining lines are of three different kinds. Berkeley's coordination-avoidance program, with CALM, Bloom^L and invariant confluence, is best described as a fellow traveller rather than a descendant: it has a root and a logic of its own, and its exchange of citations with the CRDT line is documented in both directions. The industrial line, visible in Riak, Redis and Akka, adopted the catalogue itself, and we return to it below. The critical line, the counter-attack mounted by the OT school, will get a section of its own. And the youngest line removes one of the original assumptions: the Byzantine CRDTs, to which we also return.

4Migration and Transformation

Every community that adopted CRDTs also changed them, and the changes all point in the same direction: away from how the objects are built, and towards what the objects mean.

Consider first the specification turn, which moved the objects from systems papers into semantics. What the 2011 papers had treated as a design discipline (prove the semilattice, prove the commutativity) the POPL 2014 framework recast as a specification problem, complete with lower bounds and optimality results. In the programming-languages literature the field is now called, simply, "replicated data types." That phrase appears more than five hundred times in our citation contexts, more often than "conflict-free" itself. The qualifier was dropped along the way; the concept no longer needed it.

The working vocabulary made a similar move. The catalogue's "Observed-Remove Set" is named after its mechanism: a removal only affects the elements it has observed. The literature increasingly prefers "add-wins set," a name for what the user obtains when an add and a remove race with each other. It is the same object under a new name, and the new name describes the outcome rather than the internals.

Industry, for its part, adopted the artifacts and dispensed with the citations. Akka implements the catalogue under the original names, GCounter, PNCounter, ORSet and LWWRegister, and links the 2011 technical report from its documentation. Redis built a product formerly named CRDB, documents it as "based on CRDT technology," and gives one of its documentation sections the title "Strong eventual consistency." Its only attribution is a link to Wikipedia. The ideas and their names survived the trip intact; the citing conventions did not.

The largest reframing came from the editing line. The 2019 local-first essay, by Kleppmann, Wiggins, van Hardenberg and McGranaghan, makes the case for software in which the primary copy of the data lives on the user's own device, and it names its enabling technology without hesitation: "we think CRDTs may be the foundation for collaborative software that gives users full ownership of their data" — the essay's stated analogy being packet switching. Nothing in the 2011 lists of future work, which mention complexity classes, invariants and a library, anticipates anything of the kind. A mechanism designed for convergence under network partitions was now serving as an argument about who should control the data.

The final import reversed an explicit assumption. The system model of 2011 states that processes are non-Byzantine. From 2019 onwards, the Merkle Search Trees, the Merkle-CRDTs of the IPFS ecosystem, and Kleppmann's "Making CRDTs Byzantine fault tolerant" brought together CRDT convergence and the hash-linking of content-addressed storage, so that adversarial replicas could be tolerated. The idea of convergence came through intact; the assumptions about trust did not.

5The Lost Citation Chain

If we follow the ideas beyond the reach of the citation indexes, two patterns emerge.

The first can be called hub attribution. Automerge's documentation states that Automerge is a CRDT and cites no paper at all; it links instead to crdt.tech. That site, in turn, credits the 2011 technical report and a 2018 overview, and it is maintained by Kleppmann, Bieniusa and Shapiro. Redis, as we saw, attributes to Wikipedia. Practitioner memory is thus organized in two tiers: the tools point to the hubs, and the hubs point to the founders. The pattern is familiar from everyday life, where we quote the encyclopedia and let the encyclopedia remember the sources. It is worth noticing, though, who runs the main hub here: the memory of the lineage is curated by the founding school itself. Seen from a citation database, the industrial adoption of CRDTs is almost invisible. Seen from the ground, no other community preserved the original vocabulary so faithfully, down to the exact spelling of GCounter.

The second pattern is the broken final hop, and LVars is the illustrative case. LVars, the lattice-based variables for deterministic parallelism proposed by Kuper and Newton in 2013, place least-upper-bound joins at the centre of a programming model, and cite no member of the founding cluster. They do cite CALM and Bloom^L, which cite it. On the documented record, then, the idea travelled from the 2011 cluster to Bloom^L, and from Bloom^L to LVars, with the last link back missing. To be fair, LVars also has independent roots of its own, in I-structures and in dataflow, and we class it as strong indirect descent with mixed ancestry. The general lesson deserves to be kept: when a single citation hop goes missing, an entire lineage becomes invisible to direct citation analysis.

We also record one negative result, as a matter of discipline. The convergent conflict handling of COPS resembles strong convergence, but COPS is not a descendant: it grew in parallel, from shared ancestors, and it was third parties who later drew the connection to SEC. Similarity is not inheritance, and a genealogy is only informative if it can turn down a plausible candidate now and then.

6Convergence, Fusion, and Reinterpretation

The strongest reinterpretations came from rivals, one working inside the lineage and one attacking from outside.

The inside case is that of the Mergeable Replicated Data Types, presented by Kaki, Priya, Sivaramakrishnan and Jagannathan in 2019. MRDTs keep the destination, replicated types that converge on their own, but change the engine that takes us there: convergence now comes from a three-way merge over explicit version histories, not from designing operations that commute. In essence, this is the answer familiar from Git, transported to replicated types. The paper cites the founding cluster and the POPL framework, so the descent is documented; yet it is a descent that abandons the very mechanism its ancestors saw as the heart of the matter.

The outside case is the OT school answering back. Between 2018 and 2020, Sun and colleagues published a series of papers claiming to have "revealed facts and evidences that refute CRDT claims over OT on all accounts": the correctness advantage was not real, the complexity was understated, and the deployed co-editors, which mostly run OT, had been ignored by CRDT advocacy. The choice of venue is revealing, since the papers appeared in the CSCW space, the community where OT had been born. The outcome is revealing as well: the editing line answered with repairs rather than retreats. The interleaving anomalies on which the critique pressed hardest were analysed and fixed within the CRDT line itself, with Peritext for rich text and Fugue for interleaving. In the end, the counter-attack did not stop the line; it made it better.

Underneath both episodes, the verification line was replaying the founding pattern. In 2005, a theorem prover broke the published OT functions. After 2017, it was the turn of published CRDT designs to be broken by theorem provers, including some that had arrived with supposedly mechanized proofs, and to be rebuilt on machine-checked foundations. A field born out of one correctness crisis reached maturity by putting itself through another, this time of its own making.

7Decline, Survival, or Canonization

Of decline, there is none to report. The merged citing corpus holds steady at fifty to eighty works per year from 2014 through 2026, and the volume of citation contexts actually peaks in 2025–26. Fifteen years after publication, the curve has not started to bend. What changed is the genre of the attention: two encyclopedia entries in 2018, one of them written by the founders; a place in the NoSQL survey canon; an ACM Computing Surveys treatment in 2024; and the product documentation already described. The concept migrated from research papers into works of reference, which is where a field stores what everyone is expected to know. It is a quieter form of success than a citation spike, and probably a more durable one.

Survival, on the other hand, was quite selective, and the names mattered. The catalogue's counters, registers, sets and sequences all made good careers; the graph types left only a thin trail. "Conflict-free" won over "convergent/commutative" in reception by roughly eight to one, though both survive technically as CvRDT and CmRDT. "Quiescent consistency" did not even survive its own cluster. The RADT name of the parallel invention died as well, while its artifact, RGA, prospers under the rival's name. Two forecast lines never grew at all: the complexity-class agenda announced in the paper's own future work, and the self-stabilization connection — the paper was, after all, published at a self-stabilization symposium, and the connection that its own venue seemed to invite never turned into a research line. (A note of caution is due on these dormancy claims: they are bounded by the coverage of our corpus, and absence of evidence is not evidence of absence.)

Strong Eventual Consistency had a career of its own. The formal literature adopted it as a named model, one that strengthens plain eventual consistency; the verification work turned it into the theorem that CRDT proofs establish; and Redis prints it as a heading in its documentation. Few definitions can claim a similar path.

8The Intellectual Legacy

What became, then, of the original contribution? It helps to consider its three parts separately, since each had a different fate.

The concept became infrastructure. The claim that replicated objects can be correct by construction, without coordination, travelled from contested proposal to the default frame in which distributed data types are now taught, specified, verified, shipped and disputed. The catalogue became a shared vocabulary, and part of it went further, into industrial identifiers. The formal core had the strangest fate of the three: rarely cited in ordinary contexts, it turned into the property that verification papers set out to prove and that the taxonomies of consistency models place on their maps. Its influence is strongest just where citation counts are blind.

If the whole genealogy has a through-line, it is the move from mechanism to meaning. The 2011 papers answered a question of how, with semilattices, commutativity and causal delivery. Each of the strong descendants then re-centred the discussion on a different what. What does a replicated type mean, formally? That was the specification turn. What should its conflict policy be called? That gave us add-wins. What is the technology for? Local-first ownership. What can be trusted? The Byzantine import. And what is the approach worth, when measured against a rival's engineering record? That question was posed by the OT counter-line.

Two sociological observations stand out. The first is that this lineage is unusually self-propelled. Within its own citing corpus, no community has been more productive than the founding school itself, which also maintains the hub through which practitioners remember the field. Part of the canonization, in other words, was carried out at home. The second is that the origin story is flatter than the origins. The sentence "CRDTs emerged in 2011" erases the 1997 semilattice report, the gestation inside the editing community, and the OT correctness crisis that forced the turn to commutativity. We should confess that our own first reconstruction made exactly the same mistake, and that it was a correction from one of the authors that fixed it. There is no better measure of how completely the flat story has won.

Did the 2011 paper cause the decade that followed? It did not. The times were rich in lattices, causal stores and editing algebras, and at least one sibling was invented independently. What the paper did was to give practitioners a criterion to design against, a catalogue of designs that meet it, and a name that let both circulate. The components had long been available; what was new was the synthesis. And this suggests a general rule for reading any famous paper: counting who cited it is only the beginning. One must follow the ideas themselves, and pay attention to the several names under which they travel.

Intellectual Genealogies · An intellectual genealogy follows ideas through history, not just papers through a citation network