Efficient Numerical Error Bounding for Replicated Network Services

Abstract

The goal of this work is to use database techniques to support replicated network services that accept updates to numerical records from multiple locations. Given the high overhead of maintaining strong consistency, many replicated services can tolerate divergence of their shared data, as long as the numerical error is bounded. Target distributed services include replicated stock quotes services, online auctions, distributed sensor systems, wide-area resource accounting and load balancing for replicated servers. While these target systems are broader than typical database applications, this work demonstrates how variants of existing database techniques can support these applications. We present two algorithms to e ciently bound absolute error using only local information. Split-Weight AE separately bounds negative and positive weights, while Compound-Weight AE bounds them together. The two algorithms can be combined to provide good performance and low space overhead. Our Inductive REbounds relative error also based on local information, taking advantage of the fact that the divergence was properly bounded prior to each invocation of the algorithm to reduce required wide-area communication. We discuss two optimizations that enable the algorithms to scale to thousands of data items and hundreds of replicas.