An Improved Analysis of the Lossy Difference Aggregator

Hilary Finucane and Michael Mitzenmacher
Appears in: 
CCR April 2010

We provide a detailed analysis of the Lossy Difference Aggregator, a recently developed data structure for measuring latency in a router environment where packet losses can occur. Our analysis provides stronger performance bounds than those given originally, and leads us to a model for how to optimize the parameters for the data structure when the loss rate is not known in advance by using competitive analysis.

Public Review By: 
Dmitri Krioukov

The authors perform an improved mathematical analysis of the recently introduced Lossy Difference Aggregator (LDA) data structure, filling a number of missing pieces in the original LDA analysis. While all the reviewers agree that the paper is incremental, they all find these increments interesting and important.
The specific contributions include an improved estimate for the number of LDA samples, an analysis of the effect of rounding, and a framework to optimize the LDA performance with multiple banks. Besides these LDA-specific contributions, the paper contains some high-level messages, such as that pairwise independent hash functions are often as efficient in practice as perfectly random hash functions (a reminder of authors' past results), and that competitive analysis can be generally used to tune several copies of a networked algorithm or data structure to different regimes of an unknown parameter, e.g., the loss rate in the LDA case. The authors and some reviewers believe that the latter high-level idea may find more applications in the future.