The Concept of Causality

Total ordering in natural phenomena

As humans, we grow accustomed to total ordering, because most of the natural phenomena around us appear to be subject to it.

When we go shopping, we are placed in a queue to be served in a total order.

Similarly, cars waiting for the signal to change at an intersection are also ordered in the same way.

However, there are scenarios especially prevalent in software systems where a total ordering is not really necessary.

Causal ordering using logical clocks

For instance, look at some of the social media platforms people use nowadays, where they can create posts and add comments to the posts of other people. Do we really care about the order in which two unrelated posts are shown to us? Probably not. As a result, the system could potentially leverage a partial ordering, where posts that can’t really be ordered are displayed in an arbitrarily chosen order.

However, there is still a need to preserve the order of some events that are tightly linked. For example, if a comment $C_B$ is a reply to a comment $C_A$, then we would most probably like to see $C_B$ after $C_A$. Otherwise, a conversation could end up being confusing and hard to follow.

Causality

What we just described is the notion of causality, where one event contributes to the production of another event.

Looking back at one of the introductory lessons, consistency models, we can find the description of a consistency model, called the causal consistency model. This model ensures that events that are causally related are observed by the various nodes in a single order, where causes precede the effects.

Violating causality can lead to behaviors that are really hard to understand by the users of a system.

Fortunately, as we will explore in the next lessons of this chapter, it’s possible to track causality without the need for physical time.

The notion of causality is also present in real life. We subconsciously use causality when planning or determining the feasibility of a plan.

Determining causality

Causality is determined based on a set of loosely synchronized clocks (i.e., wristwatches, wall clocks, etc.) under the illusion of a global clock. This appears to work in most cases because the time duration of events is much more coarse-grained in real life, and information “flows” much more slowly than in software systems.

For instance, compare the time a human needs to go from London to Manchester and the time needed for 10 kilobytes to travel the same distance via the Internet. So, small differences between clocks do not create significant problems in most real-life scenarios.

However, in distributed computing systems, events happen at a much higher rate and higher speed, and their duration is several orders of magnitude smaller. Consequently, if the physical clocks of the various nodes in the system are not precisely synchronized, the causality relation between events may not be accurately captured.

Causality in distributed systems

Causality can be leveraged in the design of distributed systems with the following two main benefits:

• Increasing concurrency
• Replacing real-time with the notion of logical time, which can be tracked with less infrastructure and costs

As we have seen so far, distributed systems are inherently asynchronous. By introducing coordination and synchronization between them, we essentially reduce the ...