Efficient Algorithms For Distributed Program Reliability Analysis

Abstract

In this paper, we investigated the problem of distributed program reliability in various classes of distributed computing systems. We showed that this problem is computationally intractable for arbitrary distributed computing systems, even when it is restricted to the class of star distributed computing systems. One particular solvable case for star distributed computing systems is identified, in which data files are distributed with respective to a consecutive property, and a polynomial-time algorithm is developed for this case. We also proposed a linear-time algorithm to test whether or not an arbitrary star distributed computing system has this consecutive file distribution property.