We have a distributed system (clouds & cars) that message events which need to be processed in order. However, the clock of some system participants (cars) are drifting quite often. We plan to use a logical clock for the ordering instead soon.
Just out of curiosity, would a vector clock[0] be applicable for your problem domain?
(Obv I know it's more complicated than that, but where else can you be reductionist if not the internet)
With a bare minimum implementation you should be able to get the GPS time from the NMEA strings. You just need to guarantee you'll have GPS lock at least intermittently, which is probably true for a fleet of monitored cars in nearly all situations.
Do the cars participating in the system broadcast/multicast messages to each other? If so, logical clocks like Lamport clocks or vector clocks can be of great use. Logical clocks help capture the order of events in a distributed system (sending or receiving a message is one kind of event, but not the only).
To give an example, let's say we have cars A, B, and C, they broadcast messages with Lamport timestamps. B broadcasts (lts: 33, msg: y), A broadcasts (lts: 18, msg: x). No matter in what order C receives the two messages, it knows A could not have sent "x" in response to "y", as 18 < 33. However, the converse isn't true -- i.e., 18 < 33 doesn't imply B sent "y" in response to "x", the two messages could've been broadcasted concurrently.
If you do want to be able to tell if one event might've caused another based on their logical timestamps, a vector clock is a great choice.
All that said, if this isn't as much about cars broadcasting messages to each other, as it's about cars sending messages to the server, pure logical clocks are not a tool meant for this job. This scenario calls for real-time ordering -- i.e., an imaginary omnipotent observer who could assigns a timestamp based on their own watch to each message could solve this. In the unfortunate absence of such an observer, the approaches to deal with this I'm aware of are:
- A central timestamp server. While this comes with all the obvious downsides, it's also a relatively simple and straightforward solution.
- Keeping the drift as small as possible and establishing an upper bound on it. Then waiting out the uncertainty interval before acquiring a timestamp. Basically, something akin to what Spanner is doing with their atomic clocks. A caveat here is if the cars are competing for offers with these messages, they might not be exactly happy with this strategy.
- Similar to the previous point, but without atomic clocks? Maybe you can adapt some ideas from CockroachDB[^1]?
- Using hybrid logical/physical clocks might be an option[^2][^3]
---
[^1]: https://www.cockroachlabs.com/blog/living-without-atomic-clo...
[^2]: http://users.ece.utexas.edu/~garg/pdslab/david/hybrid-time-t...
Broadcasts are always done via the Cloud, not P2P. We plan to use a hybrid clock, should have mentioned that.
I wrote something I think is highly relevant about a distributed L1 for time, that you might enjoy, OP?
[oc] https://www.seanmcdonald.xyz/p/the-clockchain-protocol-the-l...
