Accession Number : ADA118111

Title :   The Implications of Interactive Consistency for Fault-Tolerant Computations.

Descriptive Note : Final rept.,


Personal Author(s) : Pease,Marshall C

PDF Url : ADA118111

Report Date : Jul 1982

Pagination or Media Count : 19

Abstract : The program examined the significance of interactive consistency for battlefield communications. This environment is different from those considered in the original work on interactive consistency in three ways: the network is apt to be very large; it is incomplete in the sense that a particular node will not be able to communicate directly with every other one; and it is variable in unpredictable ways as links fade out or become useful. Recent work on interactive consistency is reviewed for its relevance to an environment with these characteristics. Recent work has demonstrated that, in incomplete networks, the network connectivity is critical. Specifically, in a network with N nodes of which not more than N may be faulty, interactive consistency can be assured if N is greater than 3M and the network connectivity is greater than 2M. Given the variability of the networks being considered, this makes it vital that we have a way for determining network connectivity. Two distributed algorithms for determining network connectivity have been developed.

Descriptors :   *Fault tolerant computing, *Communication and radio systems, *Battlefields, *Consistency, *Interactions, Algorithms, Nodes, Variables, Radio links, Network flows, Cryptography

Subject Categories : Theoretical Mathematics
      Military Operations, Strategy and Tactics
      Non-radio Communications

Distribution Statement : APPROVED FOR PUBLIC RELEASE