Causal, this means time dependant as seen in Causal Profiling and Dynamic Systems. To preserve ordering that temporally makes sense, sometimes things need to have a causal dependancy (question and answer, cause happens before effect). Things that are concurrent cannot have a causal relationship.
Linearizability implies causality
Causal Not Linearizable
You can actually make systems causal without making them linearizable which does not slow down due to network delays and this remains available. Most systems only require causality anyways.
We can do this because we only require a partial order, that is, concurrent operations may be processed in any ordered, but this needs to be the same processing order on every replica.The techniques that are used to determine causality are the same for detecting concurrent writes (check DDIA page 184, but the basic idea is to make use of version numbers in your transactions). The idea proposed in the book uses sequence numbers to impose a total order that is consistent with causality. Concurrent operations are fine to be arbitrarily ordered. This is like the replication log in single leader Replication. If there is no single leader, ways to generate sequence numbers include:
- Having each node generate its own independent set of sequence numbers (odd and even and node identifiers)
- Use time of day timestamps
- Preallocate blocks of sequence numbers However, these are not consistent with causality.
Lamport Timestamps
This is a method for generating sequence numbers that is consistent with causality. Each node has a unique ID and knows how many transactions has been processed. Therefore this is just a pair of (counter, node ID). You order operations based on the counter, if two counters are the same, then the one with the higher counter is the greater timestamp (happens later). This provides a total order. Note that the counter is a global counter shared by all nodes where the maximum is carried through all operations. However, this is not quite enough to solve common distributed problems.
Example
If two users want to sign up with the same username, one should succeed and the other should fail. The Lamport timestamp is not sufficient for this use case since we can only construct our total ordering retroactively. We need a way to broadcast our total order or to know that no other nodes are currently processing a conflicting request.
See Total Order.