The reliability problem in distributed database systems
Min-Sheng Lin, Deng-Jyi Chen · 2002
The reliability of a distributed database systems is the probability that a program which runs on multiple processing elements and needs to communicate with other processing elements for remote database will be executed successfully. This reliability varies according to (1) the topology of the distributed database system, (2) the reliability of the communication links, (3) the databases and program distribution among processing elements, and (4) the databases required to execute a program. This paper shows that solving this reliability problem is NP-hard even when the distributed database system is restricted to a series-parallel, a 2-tree, a tree, or a star structure. Two polynomial-time algorithms are proposed for computing the reliability of a distributed program which runs on a linear and a ring distributed database system, respectively.