A measure of fault-tolerance for distributed networks

The authors consider probabilistic networks having links that are perfectly reliable but nodes that fail randomly and independently with known probabilities. They define a fault-tolerance measure of such network that is directly affected by the choice of its underlying graph and the location of its node-components. A state of the network is tolerant if the currently operating nodes comprise a connected subnetwork. The probability of the network being in a tolerant state is the fault-tolerance (FT) measure of the network. The authors are concerned with the design of globally-best tolerant networks, that maximize FT for any given set of node-operating probabilities. They study this measure of fault-tolerance by developing combinatorial tools and by determining the optimal networks in both `sparse´ and `dense´ classes