Fault-Tolerant Time Synchronization


from pogo, Walt Kelly

Researchers involved: David Mills, Kenneth Monington
Funding: US Navy Surface Weapons Center

Briefing Slides

Importance of the Problem

Accurate, reliable time synchronization among the computers sharing a data network is vital for such things as file archive systems, cryptographic key management and real-time applications such as videoconferencing systems. Computers that are synchronized to primary servers over the Internet can experience large time errors due to asymmetric network delay paths to the primary server. This can happen in hybrid satellite/terrestrial networks and network provider configurations. This project has developed architectures, protocols and distributed algorithms designed to detect these asymmetries and calibrate appropriate corrections.

Brief Description of Work and Results

The approach to this work involves a distributed algorithm which collects measured time offsets between the host clocks of a distributed network, distributes these measurements to all hosts involved and runs a distributed algorithm which searches for inconsistencies. The algorithm detects two-faced clocks (those that display inconsistent information to their neighbors, either accidently or on purpose) using a set of cyclic consistency checks on subgraphs of the network. A distributed algorithm called the Group Method constructs subgraphs and combines them to form larger subgraphs containing only consistent measurements.

Dr. Monington's dissertation summarizing the research results has been completed. It includes a description of the approach, analysis, simulation and evaluation of the methodology.

Future Plans

As Dr. Monington has assumed a postdoctoral position with NIST Boulder, future work will be reported by him. The other activities of this project have been folded in the other projects reported on these pages.