Schedule-oblivious data management
Jeffrey Considine, John W. Byers · 2005
Traditional data management in distributed environments is a carefully orchestrated affair. Whether computing a function or distributing data, classic results are often based on models with closely connected processors and well-understood costs for accessing local and remote storage. In these idealized models, there exist many well-known solutions for managing data and aggregating results which are optimal with respect to the number of rounds, messaging costs, and total computation. However, these solutions break down when the system is challenged by any of the following: message losses, variable latencies, or network reconfigurations. Such conditions are becoming increasingly common in mobile, sensor, and peer-to-peer networks. When faced by these conditions, it may be impossible to guarantee complete reliability—approximate answers or the possibility of failure may be unavoidable, and so the tradeoff between quality and cost must be addressed. These circumstances motivate the development of protocols which are resilient or even oblivious to changes in the communications schedule describing when and with whom parties communicate. Instead of attempting to trace the global flow and duplication of data, a schedule-oblivious protocol uses only local information. Schedule-obliviousness does not provide reliability by itself, but has the flexibility of allowing any transmission policy to be employed. The cost of this approach is significant transmission overhead to account for all possible schedules. The bulk of this thesis develops the theory behind various sketching techniques which are necessary to employ a schedule-oblivious approach in practice. The feasibility of these theoretical techniques is demonstrated for two practical applications: aggregation in sensor networks and content delivery over dynamic overlay networks. The high loss and failure rates of sensor networks often necessitate the use of various multipath routing techniques; building on the sketches of Flajolet and Martin prevents redundant data from distorting query results. Content delivery networks face varying network conditions and overlay reconfigurations; our methods for approximate set reconciliation quickly identify useful information for any connection. For both applications, the schedule-oblivious approach provides an elegant answer to challenges in the network.