NTRS - NASA Technical Reports Server

Back to Results
A Self-Stabilizing Synchronization Protocol for Arbitrary DigraphsThis 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.
Document ID
Document Type
Conference Paper
Malekpour, Mahyar R. (NASA Langley Research Center Hampton, VA, United States)
Date Acquired
August 25, 2013
Publication Date
December 12, 2011
Subject Category
Mathematical and Computer Sciences (General)
Report/Patent Number
Meeting Information
17th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC 2011)(Pasadena, CA)
Funding Number(s)
WBS: WBS 534723.
Distribution Limits
Work of the US Gov. Public Use Permitted.

Available Downloads

NameType 20120000054.pdf STI