We present a Scalable Distributed Information Management System
(SDIMS) that aggregates information about large-scale networked
systems and that can serve as a basic building block for a broad range
of large-scale distributed applications providing detailed views of
nearby information and summary views of global information. To serve
as a basic building block, a SDIMS should have four properties:
scalability to many nodes and attributes, flexibility to accommodate a
broad range of applications, support administrative autonomy and
isolation, and robustness to node failures and disconnections. We
design, implement and evaluate a SDIMS that (1) uses techniques from
Distributed Hash Table (DHT) literature to create scalable aggregation
trees, (2) provides flexibility through a simple API that lets
applications control propagation of reads and writes, (3) provides
autonomy and isolation through simple augmentations of current DHT
algorithms, and (4) is robust to node and network reconfigurations
through lazy reaggregation, on-demand reaggregation, and tunable
spatial replication. Through extensive simulations and micro-benchmark
experiments, we observe that our system is an order of magnitude more
scalable than existing approaches, achieves autonomy and isolation
properties at the cost of modestly increased read latency in
comparison to flat DHTs, and gracefully handles failures.