Search NASA⌕ Search

SEARCH · Search NASA

Results for “Clock distribution”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS2011

A Self-Stabilizing Distributed Clock Synchronization Protocol for Arbitrary Digraphs

This report presents a self-stabilizing distributed clock synchronization protocol in the absence of faults in the system. It is focused on the distributed clock synchronization of an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected networks of nodes while allowing for differences in the network elements. This protocol does not rely on assumptions about the initial state of the system, other than the presence of at least one node, and no central clock or a centrally generated signal, pulse, or message is used. Nodes are anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links and interfaces. We present an outline of a deductive proof of the correctness of the protocol. A model of the protocol was mechanically verified using the Symbolic Model Verifier (SMV) for a variety of topologies. Results of the mechanical proof of the correctness of the protocol are provided. The model checking results have verified the correctness of the protocol as they apply to the networks with unidirectional and bidirectional links. In addition, the results confirm the claims of determinism and linear convergence. As a result, we conjecture that the protocol solves the general case of this problem. We also present several variations of the protocol and discuss that this synchronization protocol is indeed an emergent system.

Malekpour, Mahyar R.↗
NASA NTRS2011

Correctness Proof of a Self-Stabilizing Distributed Clock Synchronization Protocol for Arbitrary Digraphs

This report presents a deductive proof of a self-stabilizing distributed clock synchronization protocol. It is focused on the distributed clock synchronization of an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected networks of nodes while allowing for differences in the network elements. This protocol does not rely on assumptions about the initial state of the system, and no central clock or a centrally generated signal, pulse, or message is used. Nodes are anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links and interfaces. We present a deductive proof of the correctness of the protocol as it applies to the networks with unidirectional and bidirectional links. We also confirm the claims of determinism and linear convergence.

Malekpour, Mahyar R.↗
NASA NTRS2006

A Byzantine-Fault Tolerant Self-Stabilizing Protocol for Distributed Clock Synchronization Systems

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.↗
NASA NTRS2006

A Byzantine-Fault Tolerant Self-Stabilizing Protocol for Distributed Clock Synchronization Systems

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.↗
NASA NTRS2011

Model Checking a Self-Stabilizing Distributed Clock Synchronization Protocol for Arbitrary Digraphs

This report presents the mechanical verification of a self-stabilizing distributed clock synchronization protocol for arbitrary digraphs in the absence of faults. This protocol does not rely on assumptions about the initial state of the system, other than the presence of at least one node, and no central clock or a centrally generated signal, pulse, or message is used. The system under study is an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected networks of nodes while allowing for differences in the network elements. Nodes are anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links and interfaces. This protocol deterministically converges within a time bound that is a linear function of the self-stabilization period.

Malekpour, Mahyar R.↗
NASA NTRS2007

Model Checking a Byzantine-Fault-Tolerant Self-Stabilizing Protocol for Distributed Clock Synchronization Systems

This report presents the mechanical verification of a simplified model of a rapid Byzantine-fault-tolerant self-stabilizing protocol for distributed clock synchronization systems. This protocol does not rely on any assumptions about the initial state of the system. This protocol tolerates bursts of transient failures, and deterministically converges within a time bound that is a linear function of the self-stabilization period. A simplified model of the protocol is verified using the Symbolic Model Verifier (SMV) [SMV]. The system under study consists of 4 nodes, where at most one of the nodes is assumed to be Byzantine faulty. The model checking effort is focused on verifying correctness of the simplified model of the protocol in the presence of a permanent Byzantine fault as well as confirmation of claims of determinism and linear convergence with respect to the self-stabilization period. Although model checking results of the simplified model of the protocol confirm the theoretical predictions, these results do not necessarily confirm that the protocol solves the general case of this problem. Modeling challenges of the protocol and the system are addressed. A number of abstractions are utilized in order to reduce the state space. Also, additional innovative state space reduction techniques are introduced that can be used in future verification efforts applied to this and other protocols.

Malekpour, Mahyar R.↗
NASA NTRS2010

Byzantine-fault tolerant self-stabilizing protocol for distributed clock synchronization systems

A rapid Byzantine self-stabilizing clock synchronization protocol that self-stabilizes from any state, tolerates bursts of transient failures, and deterministically converges within a linear convergence time with respect to the self-stabilization period. Upon self-stabilization, all good clocks proceed synchronously. The Byzantine self-stabilizing clock synchronization protocol 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 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.

Malekpour, Mahyar R.↗
NASA NTRS2014

Fault-Tolerant Self-Stabilizing Distributed Clock Synchronization Protocol for Arbitrary Digraphs

A self-stabilizing network in the form of an arbitrary, non-partitioned digraph includes K nodes having a synchronizer executing a protocol. K-1 monitors of each node may receive a Sync message transmitted from a directly connected node. When the Sync message is received, the logical clock value for the receiving node is set to between 0 and a communication latency value (gamma) if the clock value is less than a minimum event-response delay (D). A new Sync message is also transmitted to any directly connected nodes if the clock value is greater than or equal to both D and a graph threshold (T(sub S)). When the Sync message is not received the synchronizer increments the clock value if the clock value is less than a resynchronization period (P), and resets the clock value and transmits a new Sync message to all directly connected nodes when the clock value equals or exceeds P.

Malekpour, Mahyar R.↗
NASA NTRS2011

A Self-Stabilizing Synchronization Protocol for Arbitrary Digraphs

This paper presents a self-stabilizing distributed clock synchronization protocol in the absence of faults in the system. It is focused on the distributed clock synchronization of an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected networks of nodes while allowing for differences in the network elements. This protocol does not rely on assumptions about the initial state of the system, other than the presence of at least one node, and no central clock or a centrally generated signal, pulse, or message is used. Nodes are anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links and interfaces. This protocol deterministically converges within a time bound that is a linear function of the self-stabilization period. We present an outline of a deductive proof of the correctness of the protocol. A bounded model of the protocol was mechanically verified for a variety of topologies. Results of the mechanical proof of the correctness of the protocol are provided. The model checking results have verified the correctness of the protocol as they apply to the networks with unidirectional and bidirectional links. In addition, the results confirm the claims of determinism and linear convergence. As a result, we conjecture that the protocol solves the general case of this problem. We also present several variations of the protocol and discuss that this synchronization protocol is indeed an emergent system.

Malekpour, Mahyar R.↗
NASA NTRS1997

An Adaptive Method for Reducing Clock Skew in an Accumulative Z-Axis Interconnect System

This paper will present several methods for adjusting clock skew variations that occur in a n accumulative z-axis interconnect system. In such a system, delay between modules in a function of their distance from one another. Clock distribution in a high-speed system, where clock skew must be kept to a minimum, becomes more challenging when module order is variable before design.

Bolotin, Gary↗
NASA NTRS1990

Hardware-assisted software clock synchronization for homogeneous distributed systems

A clock synchronization scheme that strikes a balance between hardware and software solutions is proposed. The proposed is a software algorithm that uses minimal additional hardware to achieve reasonably tight synchronization. Unlike other software solutions, the guaranteed worst-case skews can be made insensitive to the maximum variation of message transit delay in the system. The scheme is particularly suitable for large partially connected distributed systems with topologies that support simple point-to-point broadcast algorithms. Examples of such topologies include the hypercube and the mesh interconnection structures.

Ramanathan, P.↗
NASA NTRS1990

Fault-tolerant clock synchronization in distributed systems

Existing fault-tolerant clock synchronization algorithms are compared and contrasted. These include the following: software synchronization algorithms, such as convergence-averaging, convergence-nonaveraging, and consistency algorithms, as well as probabilistic synchronization; hardware synchronization algorithms; and hybrid synchronization. The worst-case clock skews guaranteed by representative algorithms are compared, along with other important aspects such as time, message, and cost overhead imposed by the algorithms. More recent developments such as hardware-assisted software synchronization and algorithms for synchronizing large, partially connected distributed systems are especially emphasized.

Ramanathan, Parameswaran↗
NASA NTRS2008

Verification of a Byzantine-Fault-Tolerant Self-stabilizing Protocol for Clock Synchronization

This paper presents the mechanical verification of a simplified model of a rapid Byzantine-fault-tolerant self-stabilizing protocol for distributed clock synchronization systems. This protocol does not rely on any assumptions about the initial state of the system except for the presence of sufficient good nodes, thus making the weakest possible assumptions and producing the strongest results. This protocol tolerates bursts of transient failures, and deterministically converges within a time bound that is a linear function of the self-stabilization period. A simplified model of the protocol is verified using the Symbolic Model Verifier (SMV). The system under study consists of 4 nodes, where at most one of the nodes is assumed to be Byzantine faulty. The model checking effort is focused on verifying correctness of the simplified model of the protocol in the presence of a permanent Byzantine fault as well as confirmation of claims of determinism and linear convergence with respect to the self-stabilization period. Although model checking results of the simplified model of the protocol confirm the theoretical predictions, these results do not necessarily confirm that the protocol solves the general case of this problem. Modeling challenges of the protocol and the system are addressed. A number of abstractions are utilized in order to reduce the state space.

Malekpour, Mahyar R.↗
NASA NTRS2010

Using Integer Clocks to Verify the Timing-Sync Sensor Network Protocol

We use the UPPAAL model checker for Timed Automata to verify the Timing-Sync time-synchronization protocol for sensor networks (TPSN). The TPSN protocol seeks to provide network-wide synchronization of the distributed clocks in a sensor network. Clock-synchronization algorithms for sensor networks such as TPSN must be able to perform arithmetic on clock values to calculate clock drift and network propagation delays. They must be able to read the value of a local clock and assign it to another local clock. Such operations are not directly supported by the theory of Timed Automata. To overcome this formal-modeling obstacle, we augment the UPPAAL specification language with the integer clock derived type. Integer clocks, which are essentially integer variables that are periodically incremented by a global pulse generator, greatly facilitate the encoding of the operations required to synchronize clocks as in the TPSN protocol. With this integer-clock-based model of TPSN in hand, we use UPPAAL to verify that the protocol achieves network-wide time synchronization and is devoid of deadlock. We also use the UPPAAL Tracer tool to illustrate how integer clocks can be used to capture clock drift and resynchronization during protocol execution

Huang, Xiaowan↗
NASA NTRS1990

Optical interconnections and networks; Proceedings of the Meeting, The Hague, Netherlands, Mar. 14, 15, 1990

The conference presents papers on interconnections, clock distribution, neural networks, and components and materials. Particular attention is given to a comparison of optical and electrical data interconnections at the board and backplane levels, a wafer-level optical interconnection network layout, an analysis and simulation of photonic switch networks, and the integration of picosecond GaAs photoconductive devices with silicon circuits for optical clocking and interconnects. Consideration is also given to the optical implementation of neural networks, invariance in an optoelectronic implementation of neural networks, and the recording of reversible patterns in polymer lightguides.

Bartelt, Hartmut↗
NASA NTRS1981

Timing signal propagates without phase shift

Continous monitoring of transmission delay corrects for phase shift. Nodes in Master/Slave Returnable Timing System (MSRTS) are arranged in hierarchy, with each node serving as master to several slave nodes. As signal at each slave is synchronized with original master, it serves as master to synchronize following slave nodes. System improves performance of phased microwave antenna arrays in solar-powered satellites and clock distribution systems in avionics and computers.

Kantak, A. V.↗
NASA NTRS1979

Demonstration of remote clock monitoring by VLBI with three baseline closures

The capability of very long baseline interferometry (VLBI) to monitor the stability of remotely located hydrogen maser frequency standards has been demonstrated by a series of experiments conducted between Deep Space Stations in Australia, Spain, and California. The measured stabilities of the clock systems, over approximately 10 day intervals, were 1 to 3 parts in 10 to the 13th power, with the instabilities due to the oscillators, the clock distribution systems, the receiving system delays, and the VLBI measurement error. Experiments were conducted independently using two different systems (BLOCK 0 and WBDAS). Later comparison shows agreement on the order of 1 part in 10 to the 13th power. Closure was demonstrated on three separate occasions to 33, 10, and 13 ns with an error uncertainty of + or - 42 ns. The results represent an important consistency check on VLBI measurements.

Cheetham, C. M.↗
NASA NTRS1979

Time and frequency transfer by the Master-Slave Returnable Timing System technique - Application to solar power transmission

The concept of the Master Slave Returnable Timing System (MSRTS) is presented which combines the advantages of the master slave (MS) and the Returnable Timing System (RTS) for time and frequency transfer. The basic idea of MSRTS is to send the time-frequency signal received at a particular node back to the sending node. The delay accumulated by this return signal is used to advance the phase of the master (sending) node thereby canceling the effect of the delay introduced by the path. The method can be used in highly accurate clock distribution systems required in avionics, computer communications, and large retrodirective phased arrays such as the Solar Power Satellite.

Lindsey, W. C.↗