The Network Time Protocol (NTP) is allegedly the longest running, continuously operating, distributed application in the Internet. The first packet flew in 1979 and the protocol itself hasn't changed much since then. However, the algorithms have evolved in dramatic ways and reflect the chaotic place the Internet has become. With over 100,000 servers and clients ticking in the Internet of today, NTP is not only a good timekeeper, but also a highly useful watchtower to gauge the robustness, stability and utility of the Internet itself.

This talk will focus on lessons learned (and relearned) in the analysis, design, implementation and operation of the various algorithms evolved for NTP. These include those which cryptographically authenticate valid servers, sift the messages from possibly many of them to find the most reliable clique and the best time, and nudge the client clock as close to true tick as possible. With modern workstations and fast local networks, NTP can usually nudge the clock closer than a few tens of microseconds.

There are three specific issues to be explored in the workshop context:

• Robustness of the synchronization algorithms to many and varied kinds of failure, Byzantine, malicious and otherwise. Our approach is based on diverse network paths, redundant servers and a suite of intricately crafted algorithms.
• Autonomous configuration, that is, the ability to automatically and with minimal manual intervention configure the (large) timekeeping network with respect to quality metric and overhead constraints, and to reconfigure as required due to failure or network congestion. Our approach is based on Internet multicasting, anycasting and manycasting, together with engineered drop-add heuristics which manage the load on the servers and network.
• Authentication, that is, the ability for clients to independently authenticate the servers using both public-key and private-key cryptography. Our approach uses automatically generated and managed keys with controlled lifetimes and engineered algorithms designed to avoid loss of accuracy due to encryption jitter.