Yes, but what does the synchronisation? That's the essence of these algorithms - how to effectively create a single clock that is (acceptably) synchronised between nodes. Here's some lecture notes on the problem (and solutions):-
Back from my time at Amazon, one of my favourite technical videos on the internal educational/YouTube thing was from a service team explaining how hard accurate clock sync in distributed systems was. One of those problems
I’ve just taken for granted over the years. But just layers and layers of complexity where naive assumptions at any point get you the wrong result, but it’s not at all obvious you have the wrong result.
I really wish they made more of that stuff publicly available.
Actually software developers have long been aware that different clocks can run at different speeds and tryto compare apples to apples.
Does anyone remember the name of that article that describes various clock synchronization techniques? I think it went something like "more than you ever wanted to know about computer time" and was based on an earlier similar title about another subject.
System clock synchronization is a really hard problem but especially important for things like live video stream encoding where the frame timestamps need to correspond to the real wall-clock (within milliseconds) for things like sub-second play-by-play synchronization.
Could you explain it like I'm five (or really like I'm a software geek and don't know this stuff) how the signals in the multiple lanes are synchronized? Is there some centralized clock that everyone is using?
That's an interesting link, it leads to a this 1991 Liskov paper, which might seem out-of-date, but apparently was very foundational to the whole concept. A little searching turned up this modern discussion of it:
Seems the bottom line is: "Since clock synchronization can fail occasionally, it is most desirable for algorithms to depend on synchronization for performance but not for correctness."
I think the problem here is not that the clocks are out of sync, but rather that the actual clock frequencies are voltage-controlled.
With the firefly analogy, it's like having one firefly flashing at 1.73513x (random number) faster than it's neighbor - can't easily have them persistently synchronized.
> If nothing else, LCR contains probably the most elegant and surprising application of vector clocks I've seen (they are used to establish a total order on messages, rather than the usual partial order, with no sequencer required!).
Very interesting! I'll definitely have to check this out. Thanks for the references/links.
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.
Do you have a good source on how clocks work in modern designs? From the high level down to the actual circuits?
I've always wondered why you can't generate clocks locally, but in a synchronized way. So basically like clock regions, but without having to add extra logic for data that goes between regions.
> If there is an internal hardware clock that isn't synced to real time, just count relative to that clock.
There is. All modern operating systems, including iOS, have one. Without it, commonly used features like animations and media playback would misbehave during network time synchronization.
If you move the clocks together physically, and synchronize them, this removes a large degree of the concern about instantaneous communication (this probably makes communication faster than your tolerances)
> In this paper, we present HUYGENS, a software clock synchronization system that uses a synchronization network and leverages three key ideas. First, coded probes identify and reject impure probe data—data captured by probes which suffer queuing delays, random jitter, and NIC timestamp noise. Next, HUYGENS processes the purified data with Support Vector Machines, a widely-used and powerful classifier, to accurately estimate one-way propagation times and achieve clock synchronization to within 100 nanoseconds. Finally, HUYGENS exploits a natural network effect—the idea that a group of pair-wise synchronized clocks must be transitively synchronized— to detect and correct synchronization errors even further.
Not an expert, but this seems quite a complex system. Since HF traders have huge incentive to game the system, my fear is that the next headline about Huygens will be about a new exploit found in the wild.
reply