Available Technology

A Fault-Tolerant Synchronization Protocol for Wireless Networks

An algorithm to achieve and maintain synchrony of local clocks in a distributed system after it experiences system-wide disruptions in the presence of network element imperfections
NASA solves this synchronization problem by first employing distributed clock synchronization protocols to achieve the theoretical synchrony of one-clock tick across the distributed system of nodes and, consequently, determine the geometry of the network, and then use trilateration to accurately determine the current location of the intended object. Achieving fine synchrony is in turn a two-step process using two complementary protocols. First, we use a primary distributed clock synchronization protocol to establish coarse synchrony across the distributed system of nodes. Second, we use a secondary protocol to achieve fine synchrony, which is a theoretical limit bounded to one clock tick across the system. Based on fault-tolerance requirements, we employ one of the two mechanically verified distributed clock synchronization algorithms to establish coarse synchrony across the nodes, namely, the Digraph Protocol that handles detectable faults and is versatile, in terms of the variety of topologies it is applicable to, and the Symmetric-Fault-Tolerant Protocol which, as its name implies, tolerates symmetric faults. A fault is symmetric when all good nodes observe consistent error manifestations, but do not know that it is bad. These protocols guarantee synchrony, with an initial precision of f(), where is the maximum communication delay between any two nodes, across a distributed system of nodes, from a random start and in the presence of their representative fault types. Since can be greater than one clock tick, this achieves coarse synchrony. Once coarse synchrony is achieved, a secondary algorithm subsequently attains the theoretical precision of one clock tick. Once the fine synchrony among the nodes is achieved, geometry of the network is determined, and location of the object is estimated, at the object and/or at the nodes, using trilateration.
Abstract: 
Distributed systems have become an integral part of safety-critical computing applications, necessitating system designs that incorporate complex fault-tolerant resource management functions to provide globally coordinated operations with ultra-reliability. As a result, robust clock synchronization has become a required fundamental component of fault-tolerant safety-critical distributed systems. Local clocks of nodes of a distributed system do not keep perfect time and can drift with respect to real time and one another. Thus, the local clocks of the nodes must periodically be re-synchronized. As a result, a fault-tolerant system needs a clock synchronization algorithm that tolerates imprecise local clocks and faulty behavior by some processes.
Benefits: 

Proven technology, formally and mechanically verified using the Symbolic Model Verifier (SMV)

applications: 

Communication networks

Unmanned Aircraft Systems navigation

Satellite constellations

Reps: 
Patent Number: 
10,025,344
Internal Laboratory Ref #: 
LAR-TOPS-291
Patent Status: 
Patent Issue Date: 
October 27, 2018
Agency
NASA
State: 
Virginia
Lab Representatives
Share to Facebook Share to Twitter Share to Google Plus Share to Linkedin