4 ms·
> Luckily, global orders are rarely needed and are easy to impose yourself (outside distributed cases): just let all involved parties synchronize with a common
by westurner 6y ago
> Luckily, global orders are rarely needed and are easy to impose yourself (outside distributed cases): just let all involved parties synchronize with a common process.
When there are multiple agents/actors in a distributed system, and the timestamp resolution is datetime64, and clock synchronization and network latency are variable, and non-centralized resilience is necessary to eliminate single points of failure, global ordering is impractical to impossible because there is no natural unique key with which to impose a [partial] preorder [1][2]: there are key collisions when you try and merge the streams.
Just don't cross the streams.
[1] https://en.wikipedia.org/wiki/Preorder_(disambiguation) https://en.wikipedia.org/wiki/Preorder_(disambiguation)
[2] https://en.wikipedia.org/wiki/Partially_ordered_set https://en.wikipedia.org/wiki/Partially_ordered_set
The C in CAP theorem is for Consistency [3][4]. Sequential consistency is elusive because something probably has to block/lock somewhere unless you've optimally distributed the components of the CFG control flow graph.
[3] https://en.wikipedia.org/wiki/Consistency_model https://en.wikipedia.org/wiki/Consistency_model
[4] https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem
FWIU, TLA+ can help find such issues. [5]
[5] https://en.wikipedia.org/wiki/TLA%2B https://en.wikipedia.org/wiki/TLA%2B
- codebje 6y agoWouldn't a partial order be possible using logical clocks? Vector clocks probably don't satisfy "practical" but a hybrid logical clock is practical if you can assume clock synchronisation is within some modest delta.
- toast0 6y ago> if you can assume clock synchronisation is within some modest delta. From experience with clocks, you should really be actively testing the delta, and not just assuming it.
- codebje 6y agoThe assumption would be the limit you actively test for.
- westurner 6y agoThe Lamport timestamp: https://en.wikipedia.org/wiki/Lamport_timestamp https://en.wikipedia.org/wiki/Lamport_timestamp : > The Lamport timestamp algorithm is a simple logical clock algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting point for the more advanced vector clock method.