Jagannathan, Suresh

On a distributed system, each replica should [eventually] converge to the same state. Commutative Replicated Data Types (CRDTs) can accept updates and achieve consistent without remote synchronization.

The Need for Commutativity

Say we have a queue \( 1 \to 2 \). Suppose two replicas, \(r_1\) and \(r_2\), independently call pop(). Each replica will have \(2\) on their queue.

However, on receiving an update that the other replica popped, each replica will call pop() to be consistent, thereby deleting \(2\).