NASA’s Langley Research Center has developed a portfolio of technologies regarding clock synchronization in distributed systems. Distributed synchronous systems that need to provide globally coordinated operations require each component (node) in the system to be precisely synchronized. Such systems could include electronic components within an aircraft or automobile, or large-scale networks of components that communicate with each other (e.g. multiple aircraft or automobiles). NASA’s technologies provide for very quick synchronization while tolerating various faults. These protocols provide distributed autonomous synchronization (i.e. no master clock signal required) and do not rely on any assumptions regarding the initial state of the system or internal status of the nodes.
The portfolio includes Byzantine-fault-tolerant self-stabilizing protocols for distributed clock synchronization. A fundamental criterion in the design of a robust distributed system is to provide the capability of tolerating and potentially recovering from unpredictable failures. Over coming such failures requires incorporating tolerances to various faults. The patented protocols ensure that all nodes reach the same decisions regardless of faulty components. The systems do not rely on any assumptions about the initial state of the system and do not require a central clock or externally generated pulse. The systems also tolerate bursts of transient failures, converge deterministically, and self-stabilize in a short amount of time.
The portfolio also includes a self-stabilizing distributed clock synchronization protocol for arbitrary digraphs. The protocol, or algorithm, allows for self-stabilization of nodes within a distributed system. It is focused on the clock synchronization of arbitrary, non-partitioned digraphs representing connected networks of nodes that allow for differences in the network elements. The protocol is very fast, with the ability to process within three synchronization cycles instead of the typical 150 cycles or more. Moreover, only one bit is needed for communication and no central master clock is required (such as a GPS signal).
Currently the inventions have been developed for wired applications, but could be applied to wireless applications. Potential applications include embedded systems, distributed process control, synchronization applications, inherent fault tolerance, Internet and enterprise networking, Internet-based applications, security applications, safety applications, automotive applications, aviation control systems, space exploration control systems, autonomous systems, and voter and election applications.