Fast, but Approximate, Workflow-Runtime Estimation Using the Bell-Curve Calculus

In this paper we describe the development of a Bell-Curve Calculus, analogous to interval arithmetic, in which normal distributions can be combined with arithmetic operations, such as addition, maximum, minimum, etc. We apply this Bell-Curve Calculus to the propagation of Quality of Service properties within e-Science workflows. In particular, we apply it to the problem of estimating the overall runtime of a workflow from estimates of the runtimes of its component services. We evaluate both the accuracy and efficiency of this Bell-Curve Calculus approach compared to alternative approaches. In particular, we show that it is much faster than piecewise approximation approaches, but trades this off against a loss of accuracy, which nevertheless is sufficient for certain applications.