Can someone please explain the concept of causality in distributed computing?

Question

I'm reading up on consistency models but can't seem to understand the concept of causality in distributed systems. I've googled quite a lot but don't find a good explanation of the concept. People usually explain why causality is a good thing, but what is the basic concept?

Answer 1

Taken from https://jepsen.io/consistency/models/causal

Causal consistency captures the notion that causally-related operations should appear in the same order on all processes—though processes may disagree about the order of causally independent operations.

For example, consider a chat between three people, where Attiya asks “shall we have lunch?”, and Barbarella & Cyrus respond with “yes”, and “no”, respectively. Causal consistency allows Attiya to observe “lunch?”, “yes”, “no”; and Barbarella to observe “lunch?”, “no”, “yes”. However, no participant ever observes “yes” or “no” prior to the question “lunch?”.

Answer 2

Assuming you are asking about the basic notion of causal relationships among events in distributed systems, the following may help get you on the right track.

In the absence of perfectly synchronised clocks shared by all processes of a distributed system, Leslie Lamport introduced the notion of Logical Clocks. A Logical Clock affords the establishment of a partial order over the events occurring in a distributed system via the so-called happened-before relationship, a causal relationship.

To illustrate a bit further, events on the same machine can be ordered by relying on the local clock. However, this is not generally an option for events that cross process-boundaries. In particular, we use the following insight to establish a causal relationship over message passing events in the system: send(m) at process p occurs before receive(m) at process q. This enables us to establish a causal relationship among these events.

I am not sure how helpful my explanation is, but, if you have not already done so, Leslie Lamport's original paper Time, Clocks, and the Ordering of Events in a Distributed System should help clear things up for you. Next, you may want to look at Spanner: Google's Globally Distributed Database for a creative way to deal with the issue of time in a distributed system (TrueTime).

Hope this helps.