Alan J. Demers
With Ken Birman, Robert van Renesse, Johannes Gehrke, and others, I am studying randomized “gossip protocols.” Such protocols are highly fault-tolerant and, when properly designed, extremely
scalable as well. We are studying convergence properties of several flat and hierarchical versions of the basic protocols tailored to specific application requirements.
My particular focus is approximate evaluation of aggregate queries in such a system. We are studying age distributions of gossiped data in order to prove probabilistic bounds on the quality of aggregate query results. Alternatively, we can use this approach to bound the latency required to probabilistically guarantee a client-specified degree of consistency.
We are also considering classes of problems for which results of site-specific queries can be computed using hierarchically summarized data. Using this approach, each site can autonomously compute query results with a bounded precision or competitive ratio, while the system remains scalable in the usual sense that the per site cost of replicating the data grows less than linearly in the total amount of data.
The above is related to my previous work on the Clearinghouse and Bayou projects at Xerox PARC. I am also doing work supported by Oracle on asynchronous update-anywhere replication in a more traditional database setting. This involves algorithms for scheduling/reordering update propagation between sites to improve throughput while preserving eventual consistency and bounded inconsistency during propagation.
Reviewer: IEEE; National Academies.
Recent Patents Space-efficient method of verifying electronic payments. United States Patent 6,021,399, Feb. 1, 2000 (with D. Greene, B. Spitznagel, and R. Want).
Database index selection using minimum leaf spanning tree. United States Patent 6,105,018, Aug. 15, 2000 (with A. Downing).