Distributed randomized algorithms for probabilistic performance analysis

Randomized algorithms are a useful tool for analyzing the performance of complex uncertain systems. Their implementation requires the generation of a large number N of random samples representing the uncertainty scenarios, and the corresponding evaluation of system performance. When N is very large and/or performance evaluation is costly or time consuming, it can be necessary to distribute the computational burden of such algorithms among many cooperating computing units. This paper studies distributed versions of randomized algorithms for expected value, probability and extrema estimation over a network of computing nodes with possibly time-varying communication links. Explicit a priori bounds are provided for the sample and communication complexity of these algorithms in terms of number of local samples, number of computing nodes and communication iterations.