Causality vs a Total Order
A total order allows any two elements to be compared (like natural numbers). Sets on the other hand are partially ordered.
In a linearizable system, we have a total order of operations. We can always say what happened before the other. Two events are ordered if they are causally related but are incomparable if they are concurrent. For some reason this means that causality defines a partial order.
Total Order Broadcast
Requires:
- Reliable delivery: No messages are lost
- Totally ordered delivery: Messages are delivered to every node in the same order This is used for:
- State machine replication
- Used for implementing a lock service for delivering Fencing Tokens This is different than linearizability because it does not have the same recency guarantee.
To actually build total order broadcast, we need Consensus Algorithms