National Aeronautics and Space Administration (NASA)
Published: 2018-05-29
Total Pages: 38
Get eBook
Embedded distributed systems have become an integral part of safety-critical computing applications, necessitating system designs that incorporate fault tolerant clock synchronization in order to achieve ultra-reliable assurance levels. Many efficient clock synchronization protocols do not, however, address Byzantine failures, and most protocols that do tolerate Byzantine failures do not self-stabilize. Of the Byzantine self-stabilizing clock synchronization algorithms that exist in the literature, they are based on either unjustifiably strong assumptions about initial synchrony of the nodes or on the existence of a common pulse at the nodes. The Byzantine self-stabilizing clock synchronization protocol presented here does not rely on any assumptions about the initial state of the clocks. Furthermore, there is neither a central clock nor an externally generated pulse system. The proposed protocol converges deterministically, is scalable, and self-stabilizes in a short amount of time. The convergence time is linear with respect to the self-stabilization period. Proofs of the correctness of the protocol as well as the results of formal verification efforts are reported.Malekpour, Mahyar R.Langley Research CenterCLOCKS; SYNCHRONISM; PROVING; FAULT TOLERANCE; CONVERGENCE; EMBEDDING; ALGORITHMS; SAFETY; PROTOCOL (COMPUTERS); PROGRAM VERIFICATION (COMPUTERS); FAILURE