Project Abstract:
We propose a balanced tree structure overlay on a peer-to-peer
network capable of supporting both exact queries and range queries
efficiently. In spite of the tree structure causing distinctions to be
made between nodes at different levels in the tree, we show that
the load at each node is approximately equal. In spite of the tree
structure providing precisely one path between any pair of nodes,
we show that sideways routing tables maintained at each node
provide sufficient fault tolerance to permit efficient repair.
Specifically, in a network with N nodes, we guarantee that both
exact queries and range queries can be answered in O(logN) steps
and also that update operations (to both data and network) have
an amortized cost of O(logN). An experimental assessment validates
the practicality of our proposal. |