Title: P2P and Geometry: Novel Architectures for DHT's and Dynamic Quorum Systems

Moni Naor

Weizmann Institute

We consider an approach for constructing P2P networks based on a dynamic decomposition of a continuous space into cells corresponding to processors. Using this approach we suggest two new architectures, one for DHT (Distributed Hash Table) and the other for dynamic quorum systems. The DHT network which we call Distance Halving allows logarithmic routing and load, while preserving constant degrees. The dynamic quorum system allows maintaining such a system where it is very easy to add and delete processors to the systems while maintaining low load and high availability. Another scheme in this framework constructs a dynamic expander network which is useful for online job balancing. The resulting topologies are simple to maintain and implement. We see in them great potential for addressing issues such as heterogeneity, relieving hotspots and fault tolerance.

Joint work with Udi Wieder

Gates 4B (opposite 490), Wednesday 8/28/02, 4:00 PM