On Distributions of Run-Times in Distributed Systems
Vernon J. Rego · Purdue e-Pubs (Purdue University System) · 1986
In distributed systems. the inherently variable processing times cannot, in general, be satisfactorily characterized purely by average or worst-case times. These measures are difficult to interpret when identical inputs show very different processing times, a situation typical of distributed algorithms executing on distributed systems. This is due to the nondeteIminisLic nature of communication, and factors such as network load, reliability, interference, etc. Thus it becomes important to study Lhe variance of running-times. as a function of various communication parameters. We propose a simple, yet computationally effective teclmique, to obtain the average running-time distribution of a distributed algorithm. involving a set of n processors on a local network.