In computer science, especially when working with Distributed Systems, tracking causality is a crucial problem. Think of it as being similar to following the plot of your favourite movie - keeping track of the cause and effect of each event gives you a clear understanding of the story.
In the context of Conflict-Free Replicated Data Types (CRDTs), causality tracking helps us keep tabs on the order of operations applied to the data. This helps ensure that all replicas in the system converge to the same state, despite updates coming in different orders from different sources.
Imagine a super simple version of a CRDT system in the shape of a Python dictionary. As you might know, a dictionary in Python maintains a set of keys, each associated with a value. Now, consider each entry in the dictionary as an element in a CRDT and imagine you have multiple such dictionaries (or replicas) spread across a network. When a certain key (a CRDT element) gets updated by one replica, that update might not yet be visible to another replica. This creates a temporary divergence in the system.
So how does causality tracking come into play? It simply allows each replica to recognize the changes it has not seen yet, guiding the conflict resolution process towards system-wide convergence.
As you can see in the Python code snippet, we create a dictionary and add elements representing a simple CRDT. To illustrate divergence in the system, let's say Replica1 updates key 'A' to 5 and, at the same time, Replica2 updates key 'B' to 4. Tracking causality will help us manage these diverging updates to achieve system-wide agreement (convergence).
xxxxxxxxxx
if __name__ == "__main__":
# Python logic here
# Imagine a simple CRDTs system as a dictionary
crdt_dict = {}
# Adding elements in the dictionary
crdt_dict['A'] = 1
crdt_dict['B'] = 2
crdt_dict['C'] = 3
# Now imagine we have two replicas with different states
# Replica1 updates A to 5 and Replica2 updates B to 4
# There exists a divergence in the system
# Tracking cause helps to recognize the changes not seen by other replicas
# Thus guiding conflict resolutions
print(crdt_dict)
print("Print something")