Operation-based CRDTs (CmRDTs)

Operation-based CRDTs (CmRDTs), or Commutative Replicated Data Types, achieve consistency by transmitting operations instead of states, requiring the ordering of operations to be preserved. It all revolves around the concept of commutativity, meaning order of operations doesn't matter, 5 7 gives the same result as 7 5.

Let's consider CmRDTs in the context of a movie enthusiast who loves making lists of their favorite movies. If you're updating your favorite movies list on various devices, each operation (addition or removal of a movie) made on any device must be replicated on all other devices to maintain consistency.

Just think of it like this, you have a list of favorite movies and you're changing it on your phone, tablet, and laptop. If any changes are made anywhere, they are reflected everywhere. If you add 'Inception' to the list on your phone, and then remove 'The Dark Knight' on your laptop, these changes will be replicated on all other devices. To implement this, each device needs to keep a log of operations (like a financial ledger), not just the state (the current list of movies).

For this, the design could be a simples set with add and remove operations, implemented in Python as below:

1{
2  "Inception",
3  "The Dark Knight"
4}

The above pseudo-Python script demonstrates how operations take place in CmRDTs. Consequently, if we add a movie, it is added to the set, and if a movie is removed, it is removed from the set.

One major upside to CmRDTs is that they allow offline operations which can be synchronized later. But the existence of duplicate operations could be a challenge, which can be solved by decision-making logic in the conflict resolution algorithm. Additionally, preserving the order of operations could also be a potential challenge in certain scenarios, hence the requirement for algorithms that ensure causal consistency.

xxxxxxxxxx

if __name__ == "__main__":

  # Python logic here

  class CmRDT:

    def __init__(self):

      self.set = set()

​

    def add(self, element):

      self.set.add(element)

    def remove(self, element):

      if element in self.set:

        self.set.remove(element)

​

  cmrdt = CmRDT()

  cmrdt.add("Inception")

  cmrdt.add("The Dark Knight")

  print("Print favorite movies:", cmrdt.set)