Accession Number : ADA118111
Title : The Implications of Interactive Consistency for Fault-Tolerant Computations.
Descriptive Note : Final rept.,
Corporate Author : SRI INTERNATIONAL MENLO PARK CA
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
Distribution Statement : APPROVED FOR PUBLIC RELEASE