Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

percisely.xyz

Post reply on HN
Print view View original

11–20 of 24 posts

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

#11

Post by willis936 »

labcomputer wrote: post #9
willis936 wrote: post #7

Earlier quoted context omitted.

It probably won't be 100 ns accurate in motion, but still quite accurate. Practically speaking you won't get better than ~1 s unless you connect the PPS pin to an interrupt or PLL. 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 si…

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.

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

#14

Post by AdieuToLogic »

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

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

#16

Post by myk9001 »

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 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 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...

[^3]: https://cse.buffalo.edu/tech-reports/2014-04.pdf

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

#17

Post by myk9001 »

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.

You might also find this paper interesting. To be fair, so far I only had a chance to give it a very superficial look.

https://dl.acm.org/doi/pdf/10.1145/112600.112601

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

#18

Post by myk9001 »

econner wrote: post #5
michaelt wrote: post #4

Earlier quoted context omitted.

No way of accessing your cars' GPS receivers' 100-nanosecond-precise time signal, huh?

Yea I always liked the way Spanner solved this. Let's not bother with any of the distributed system theory and just use that Google money to build in to the system extremely precise clocks :-D. (Obv I know it's more complicated than that, but where else can you be reductionist if not the internet)

This[^1] Barbara Liskov's paper gives me an impression the distributed systems people would be glad if they didn't have to bother with all the theory :)

---

[^1]: https://dl.acm.org/doi/pdf/10.1145/112600.112601

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

#19

Post by YetAnotherNick »

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.

Is it P2P connection or something? You could easily order events using kafka, redis or any alternative in cloud if they are less than million per second range.

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

#20

Post by tincholio »

jpgvm wrote: post #12

Possibly the most important distributed systems paper to read, along with the rest of Lamport naturally.

This is the first Lamport paper I read (over 20 years ago now), and it has stuck with me since then, it's so clearly explained...
Post reply on HN