Einstein said you can't absolutely order events -- and with widely enough distributed systems and small enough time quanta, sooner or later you're going to run into relativistic implications.
Probably not a problem for most applications we currently have to deal with, but one day -- soon enough that we're already giving new protocols names like "Interplanetary File System" -- our databases will spread out among the stars, and how will we handle time and event ordering then?
(I work at Cockroach Labs and gave an internal talk on this paper some time ago).
If you're planning to run on VMware, be prepared to handle rather dramatic system clock shifts. I've seen shifts of up to 5 minutes during heavy backup windows. Not all customers might be willing to have their nodes go down due to system clock / NTP issues.
Yep, we've also had our share of troubles with noisy clock on cloud environments, so that's something we're very aware of. Further down the road, we're considering a "clockless" mode, which of course isn't clockless, but depends less on the offset threshold: https://github.com/cockroachdb/cockroach/issues/14093
That said, even today, configuring a cluster with a fairly high maximum clock offset is feasible for many workloads.
Dead Comment
Dead Comment
Thank you for the analysis of my post but it seems that you didn't get it correctly. Even to read a value you have to execute the full cycle (prepare, accept) of consensus (in the case of the stable leader we can skip prepare), so when you read the nil value the state of the system will be:
A: (value=foo ballot=1 promised=2) B: (value=nil ballot=2 promised=2) C: (value=nil ballot=2 promised=2)
Not the one you mentioned in the post:
A: (value=foo ballot=1 promised=2) B: (value=nil ballot=0 promised=2) C: (value=nil ballot=0 promised=2)
So the counter example is incorrect.
I proved the algorithm mathematically by hand and used very aggressive property based testing with fault injections so I'm pretty confident in its correctness.