Efficient Reliability Modeling of the Heterogeneous Autonomous Decentralized Systems

Yinong CHEN  Zhongshi HE  Yufang TIAN  

IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.10   pp.1360-1367
Publication Date: 2001/10/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (IEICE/IEEE Joint Special Issue on Autonomous Decentralized Systems and Systems' Assurance)
Category: Issues
autonomous decentralized system (ADS),  networking,  distributed computing,  residual connectedness reliability,  graph theory,  bounding,  

Full Text: PDF>>
Buy this Article

The heterogeneous autonomous decentralized system technology offers a way to integrate different types of context-related autonomous decentralized (sub) systems into a coherent system. The aim of this research is to model and evaluate the communication capacity among the subsystems connected by communication gateways of a heterogeneous autonomous decentralized system. Failures of subsystems and communication gateways in the system are taken into account. We use graphs to represent the topologies of heterogeneous autonomous decentralized systems and use the residual connectedness reliability (RCR) to characterize the communication capacity among its subsystems connected by its gateways. This model enables us to share research results obtained in residual connectedness reliability study in graph theory. Not to our surprise, we learnt soon that computing RCR of general graphs is NP-hard. But to our surprise, there exist no efficient approximation algorithms that can give a good estimation of RCR for an arbitrary graph when both vertices and edges may fail. We proposed in this paper a simulation scheme that gave us good results for small to large graphs but failed for very large graphs. Then we applied a theoretical bounding approach. We obtained expressions for upper and lower bounds of RCR for arbitrary graphs. Both upper and lower bound expressions can be computed in polynomial time. We applied these expressions to several typical graphs and showed that the differences between the upper and lower bounds tend to zero as the sizes of graphs tend to infinite. The contributions of this research are twofold, we find an efficient way to model and evaluate the communication capacity of heterogeneous autonomous decentralized systems; we contribute an efficient algorithm to estimate RCR in general graph theory.