Jorge E. Pezoa, Sagar Dhakal and Majeed M. Hayat
IEEE TRANSACTIONS PARALLEL AND DISTRIBUTED SYSTEMS 21, 10 (2010)
In distributed computing systems (DCSs) where server nodes can fail permanently with non-zero probability, the system
performance can be assessed by means of the service reliability, defined as the probability of serving all the tasks queued in the DCS before all the nodes fail. This paper presents a rigorous probabilistic framework to analytically characterize the service reliability of a DCS in the presence of communication uncertainties and stochastic topological changes due to node deletions. The framework
considers a system composed of heterogeneous nodes with stochastic service and failure times and a communication network
imposing random tangible delays. The framework also permits arbitrarily specified, distributed load-balancing actions to be taken
by the individual nodes in order to improve the service reliability. The presented analysis is based upon a novel use of the concept of stochastic regeneration, which is exploited to derive a system of difference-differential equations characterizing the service reliability. The theory is further utilized to optimize certain load-balancing policies for maximal service reliability; the optimization is carried out by means of an algorithm that scales linearly with the number of nodes in the system. The analytical model is validated using both Monte-Carlo simulations and experimental data collected from a DCS testbed.