Interdisciplinary research between professor Balaji Prabhakar, his team, and Google has produced a software clock synchronization system that can track time down to 100 billionths of a second.
The current, popular clock synchronization algorithm, NTP, can only achieve millisecond-level accuracy. Current solutions for achieving a synchronization accuracy of 10s-100s of nanoseconds require specially designed hardware throughout the network for combatting random network delays and component noise or to exploit clock synchronization inherent in Ethernet standards for the PHY.
The research team presents HUYGENS, named for the Dutch physicist Christiaan Huygens, who invented the pendulum clock in 1656. HUYGENS is 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. HUYGENS then 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.
The importance of technical advances in measuring time was underscored by European regulations that went into effect in January and that require financial institutions to synchronize time-stamped trades with microsecond accuracy.
Being able to trade at the nanosecond level is vital to Nasdaq. Two years ago, it debuted the Nasdaq Financial Framework, a software system that it has envisioned eventually trading everything from stocks and bonds to fish and car-sharing rides.
The new synchronization system will make it possible for Nasdaq to offer "pop-up" electronic markets on short notice anywhere in the world, Mr. Prabhakar said. He cited the World Cup as a hypothetical example of a short-term electronic marketplace.
"There are tickets needed, housing, people will need transportation," he said. "Think of an electronic market almost like a massive flea market hosted by Nasdaq software."
The HUYGENS team is Yilong Geng (EE PhD candidate), Shiyu Liu (EE PhD candidate), and Zi Yin (EE PhD candidate), Ashish Naik (Google Inc.) EE professors Balaji Prabhakar and Mendel Rosenblum, and Amin Vahdat (Google Inc.)
Related Links (excerpted from)
- The New York Times', "Time Split to the Nanosecond Is Precisely What Wall Street Wants," June 29, 2018.
- Paper presented at NSDI '18, "Exploiting a Natural Network Effect for Scalable, Fine-grained Clock Synchronization".