Efficient Algorithms for Residual Connectedness Reliability of 
the Distributed Systems

Zhongshi He   and    Yinong Chen
Highly Dependable Systems Research Programme
University of the Witwatersrand , Johannesburg, South Africa
{zhe, yinong }@cs.wits.ac.za
http://www.cs.wits.ac.za/research/programme.html

 Full Paper in Postscript File

Abstract

This paper discusses the reliability of a distributed system in 
which the links are considered reliable while the computing nodes 
may fail with certain probability. We need to find a subset of 
nodes in the system to run replicas of a critical task so that 
the task can survive as long as possible. The system configuration 
can be changed due to nodes' failures and task reallocation (system 
reconfiguration) has to be performed after a number of nodes become 
faulty. The task reallocation problem is converted into a well-known 
graph theory problem and the reliability of a task is modelled by 
the residual connectedness reliability R(G) of a graph G. To perform 
optimal task reallocation, we need to calculate R(G) after a number 
of nodes become faulty. This paper proposes a new approach with 
efficient algorithms for evaluating R(G). Numerical and graphic 
results are presented.

Key words. network reliability, bounds, connectedness, distributed 
system, hypercube.