The Value of Variance

Measurements for distributed algorithms, such as performance results, are usually reported using averages, similarly to prevailing practice in other areas of computer science. We argue that including standard deviations offers additional information and that the minimal burden of providing standard deviations is outweighed by the benefits. We propose a new way of reporting run time speedup that incorporates standard deviation and demonstrate its usefulness in terms of two distributed graph algorithms.