Thursday, September 12, 2013

Beatmatching the Internet

The primary skill of a DJ is 'beatmatching'; playing two songs together so their beats perfectly overlap and it sounds like one song. (Do it wrong, and the whole room groans from the cacophony.)

The next issue that I have to solve is how to keep a network of thousands of browsers running my peer-to-peer app synchronized with a single network clock. If they don't share common time, then peers can't swap physics state, because positions, velocities, and accelerations are all time-related quantities.

So the paper I've been implementing this week is:
Gossip Based Clock Synchronization for Large Decentralized Systems

The basic principle is stolen from Fireflies. They blink in synchrony with each other in swarms of thousands, or even millions of the little bugs. They clearly don't have a central network-accessible timeserver, so how do they do it? Well, it's also the same way a crowd 'locks on' to synchronized clapping at basketball games. We all have our own 'clapping rate' and we adjust that rate to bring it into perceived synchrony with what we can hear - which is your neighborly 'subset' of people within audio range.



When that principle is in operation (defined as "taking the alpha-trimmed mean of all known peers". "alpha-trimming" is just ranking the list, and throwing away the top and bottom quarters, or some other fixed percentage. In essence, "going with the majority".) crowds that started with pure chaos have order spontaneously emerge, and within seconds the entire ensemble is in perfect lock-step.

Now that's all well and good, but I have also learned the secret pain of all true timekeepers: General Relativity.

Special relativity is enough trouble on it's own, but the concept of speed-of-light delays is entirely tractable and is built into the internet at a fundamental level. Instantaneous communication would really help the problem of keeping remote clocks synchronized, but isn't strictly necessary. So long as the flight-time to and fro are equal, we can cancel them out with some math.

General Relativity explains that there is no such thing as a single reference timeframe. And frankly, we've tended to ignore that as not relevant to our daily lives, but it's no longer the case. If you like having a GPS that gives better than 30 metres of accuracy, then you're invoking full General Relativity, because they have to 'slow down' the clock ticks that the GPS satellites send out because they are higher in the gravity well than us, and therefore time passes slightly faster for the satellites than us.

If you remember your Popular Science, this is the Twins Paradox. We have a situation where the atomic clocks in orbit seem to go faster because, literally, time is faster up there. Send two clocks along different spacetime paths with different time dilations, and they will perfectly record the time they individually experienced getting there, and will legitimately disagree. So we can't do the classical trick of starting a clock in Greenwich and then moving it to Mars, because the path we take will change the result.

If they did not account for that effect, your GPS system would not be accurate to the city block.

But then how does this affect the concept of internet timekeeping? Well, the internet is expanding out into the solar system, catching a ride with the various probes we send. All our protocols are based on an Earth-Greenwich-centric concept of universal linear time, which is fundamentally not true. That's an issue for the JPL planners right now.

And as our clocks get better, we'll begin to notice the same effect across the surface of the globe. If you live on a tall mountain, or in one of those gravitational anomalies, then clocks in your area are going at a different rate. At some point we'll have to add corrections to our internet routers to account for the warp, or packet times will be wrong. Your mobile phone will need know the local rate of time in order to get sub-millimetre GPS accuracy.

As for our Legal System? I'm waiting for someone to divorce an astronaut, and for the lawyers to explain whether the change in marital status propagates at light-speed, or faster. (Is it like a neutrino?) Or more importantly, what 'before' and 'after' actually mean for high-frequency nanosecond trades in the global financial system.

At least for me, at the moment, the accuracy of browser timers isn't sufficient to really show up this problem. Thermal noise will have a bigger effect, so I can get away with purely classical ideas of time. At least, in this version. Call it an open problem.

But now I know why internet timekeepers have such a crazy look in their eyes. For them, the wibbly-wobbly nature of time is a physical presence who comes into their labs and beats up their fragile human conceptions of one-thing-happening-after-another. On a daily basis.

Be kind to them.

Oh, and I got a message from PayPal explaining the new way in which they are being stupid from next month (upgrading from HTTP 1.0 to 1.1 on your servers shouldn't require the entire internet to upgrade their software simultaneously.) in ways which I expect will seriously damage the credibility of the company when thousands of small internet stores suddenly break on Oct 9, and then have to dig through their spam archives to figure out why. But frankly I'm bored of that entire kettle of stupid. My forehead can't take the face-palming anymore.

No comments:

Post a Comment