Time, Clocks, and the Ordering of Events in a Distributed System

Re: Time, Clocks, and the Ordering of Events in a Distributed System – Paper Review

#21

Post by Phelinofist » Tue, Jul 25, 2023, 12:31 PM UTC

myk9001 wrote: post #16

Phelinofist wrote: post #3

Thanks for the link, really interesting! 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.

Disclaimer: I'm not a distributed systems expert by any stretch of the imagination. Just picked up an interest in the subject some time ago. So, the things I'm about to say may sound silly. 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 s…

Thanks for your comment, very interesting and great links.

Broadcasts are always done via the Cloud, not P2P. We plan to use a hybrid clock, should have mentioned that.

Re: Time, Clocks, and the Ordering of Events in a Distributed System – Paper Review

#22

Post by Phelinofist » Tue, Jul 25, 2023, 12:32 PM UTC

AdieuToLogic wrote: post #14

Phelinofist wrote: post #3

Thanks for the link, really interesting! 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.

> We have a distributed system (clouds & cars) that message events which need to be processed in order. Just out of curiosity, would a vector clock[0] be applicable for your problem domain? 0 - https://en.wikipedia.org/wiki/Vector_clock

AFAIU Vector clocks are hybrid clocks and we plan to use a hybrid one, should've mentioned that from the start.

Re: Time, Clocks, and the Ordering of Events in a Distributed System – Paper Review

#23

Post by myk9001 » Tue, Jul 25, 2023, 5:54 PM UTC

Phelinofist wrote: post #21

myk9001 wrote: post #16

Earlier quoted context omitted.

Disclaimer: I'm not a distributed systems expert by any stretch of the imagination. Just picked up an interest in the subject some time ago. So, the things I'm about to say may sound silly. 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 s…

Thanks for your comment, very interesting and great links. Broadcasts are always done via the Cloud, not P2P. We plan to use a hybrid clock, should have mentioned that.

Looks like you have a truly exciting task ahead. Hybrid clocks are a very interesting technology. Good luck!

Re: Time, Clocks, and the Ordering of Events in a Distributed System – Paper Review

#24

Post by labcomputer » Fri, Jul 28, 2023, 5:23 PM UTC

willis936 wrote: post #11

labcomputer wrote: post #9

Earlier quoted context omitted.

Urban canyons aside, the GNSS receiver itself should almost always have better than 100 ns accuracy, even when moving. After all, 100 ns at the speed of light is ~30 meters. At 200 ns you're on the wrong city block. As for bringing that into a computer, I'm having a hard time imagining a hardware setup where a software PLL won't give you millisecond-level accuracy (assuming you have an internal clock with at least th…

Yes I am referring to NMEA string usage because that's as good as you'll get if the PPS output is not connected. You don't strictly need a hardware disciplined oscillator solution, which is why I mentioned connecting to an interrupt pin. This has worked pretty well for me when making raspberry pis into stratum 0 NTP servers.

> Yes I am referring to NMEA string usage because that's as good as you'll get if the PPS output is not connected.

1. That's only true with a super, super naive approach. You can easily estimate the average latency as part of your prototyping, and subtract that (while "live") from when you receive the full NEMA string. That will knock down the (in)accuracy by at least an order of magnitude, probably two, depending on latency variance. NEMA messages are (almost[1]) always sent synchronously with the PPS.

2. Again I'm having trouble imagining this naive hardware setup where you don't have a better timestamp than 1 second. NEMA usually comes over a UART, so just timestamping the first byte of the NEMA string will give you ~millisecond accuracy. Even a cheap USB 1.1 UART dongle that only polls at 125Hz should give you ~10 millisecond accuracy. As above, you can estimate average latency during development to improve accuracy during usage.

You'll need to do a little bit of software filtering to remove outliers, of course, but that requires no extra hardware.

The point is: The technical bar to getting 10ms accuracy with no special hardware and no PPS is basically zero.

[1] I'm hedging with almost, but I've never seen a counterexample.