# The Emergence of CRDTs

The formal concept of Conflict-free Replicated Data Types (CRDTs) was first
introduced in Marc Shapiro's 2011 paper,
[Conflict-Free Replicated Data Types](https://inria.hal.science/hal-00932836/file/CRDTs_SSS-2011.pdf).
However, it can be argued that the groundwork for CRDTs was laid earlier, in the
2006 study [Woot](https://doi.org/10.1145%2F1180875.1180916): An Algorithm for
Collaborative Real-time Editing. The primary motivation behind developing CRDTs
was to address the challenges associated with designing conflict resolution
mechanisms for eventual consistency. Prior to the introduction of CRDTs,
literature on the subject offered limited guidance, and ad hoc solutions were
often prone to errors. Consequently, Shapiro's paper presented a simple,
theoretically sound approach to achieving eventual consistency through the use
of CRDTs.

(PS: Marc Shapiro actually wrote a paper
[Designing a commutative replicated data type](https://hal.inria.fr/inria-00177693v2/document)
in 2007. In 2011, he reworded commutative into conflict-free in 2011, expanding
the definition of commutative to include state-based CRDT)

According to [CAP theorem](https://en.wikipedia.org/wiki/CAP_theorem), it is
impossible for a distributed computing system to perfectly satisfy the following
three points at the same time.

- _Consistency_: each read receives the result of the most recent write or
  reports an error; it behaves as if it is accessing the same piece of data
- _Availability_: every request gets a non-error response - but there is no
  guarantee that the data fetched is up-to-date
- _Partition tolerance_: the ability of a distributed system to continue
  functioning properly even when communication between its different components
  is lost or delayed, resulting in a partition or network failure.

If the system cannot achieve data consistency within the time limit, it means
that partitioning has occurred and a choice must be made between C and A for the
current operation, so "perfect consistency" is in conflict with "perfect
availability".

CRDTs do not provide "perfect consistency", but
Strong Eventual Consistency (SEC). This
means that site A may not immediately reflect the state changes from site B, but
when A and B synchronize their messages they both regain consistency and do not
need to resolve potential conflicts (CRDT mathematically prevents conflicts from
occurring). _Strong Eventual Consistency_ does not conflict with _Availability_
and _Partition Tolerance_. CRDTs provide a good CAP tradeoff.

![CPA](./crdt-images/a4858e2a50bc1a2d79722060156e89b0cac5815cf25e8c67e409aa0926280cef.png)
_CRDT satisfies A + P + Eventual Consistency; a good tradeoff under CAP_

(PS: In 2012, Eric Brewer, author of the CAP theorem, wrote an article
[CAP Twelve Years Later: How the "Rules" Have Changed](https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/),
explaining that the description of the "two out of three CAP features" is
actually misleading, and that the CAP actually prohibits perfect availability
and consistency in a very small part of the design space, i.e., in the presence
of partitions; in fact, the design of the tradeoff between C and A is very
flexible. A good example is CRDT.)