NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
A Self-Stabilizing Hybrid Fault-Tolerant Synchronization ProtocolThis paper presents a strategy for solving the Byzantine general problem for self-stabilizing a fully connected network from an arbitrary state and in the presence of any number of faults with various severities including any number of arbitrary (Byzantine) faulty nodes. The strategy consists of two parts: first, converting Byzantine faults into symmetric faults, and second, using a proven symmetric-fault tolerant algorithm to solve the general case of the problem. A protocol (algorithm) is also present that tolerates symmetric faults, provided that there are more good nodes than faulty ones. The solution applies to realizable systems, while allowing for differences in the network elements, provided that the number of arbitrary faults is not more than a third of the network size. The only constraint on the behavior of a node is that the interactions with other nodes are restricted to defined links and interfaces. The solution does not rely on assumptions about the initial state of the system and no central clock nor centrally generated signal, pulse, or message is used. Nodes are anonymous, i.e., they do not have unique identities. A mechanical verification of a proposed protocol is also present. A bounded model of the protocol is verified using the Symbolic Model Verifier (SMV). The model checking effort is focused on verifying correctness of the bounded model of the protocol as well as confirming claims of determinism and linear convergence with respect to the self-stabilization period.
Document ID
20150009471
Document Type
Conference Paper
Authors
Malekpour, Mahyar R. (NASA Langley Research Center Hampton, VA, United States)
Date Acquired
June 3, 2015
Publication Date
March 7, 2015
Subject Category
Computer Programming and Software
Report/Patent Number
NF1676L-19862
Meeting Information
2015 IEEE Aerospace Conference(Big Sky, MT)
Funding Number(s)
WBS: WBS 534723.02.02.07.30
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Available Downloads

NameType 20150009471.pdf STI