Computing Seminar

Scalable Data Access in Peer-to-Peer Systems

Karl Aberer, EPFL, Distributed Information Systems Laboratory

Abstract

With the appearance of Peer-to-Peer information systems the interest in scalable and decentralized data access structures is attracting increasingly interest. We propose to that end P-Grid, a scalable data access structure resulting from the distribution of a binary prefix tree. When adapting the P-Grid structure to skewed data distributions one obtains unbalanced search trees. We show that unbalanced trees do not harm as long as communication is considered as the critical cost and the access structures are constructed properly. We propose the necessary distributed, randomized algorithms that allow to construct the P-Grid in a self-organized manner such that the tree structure dynamically adapts to the data distribution and the aforementioned result is applicable. We compare our approach to other distributed indexing schemes that have been proposed in research and practice.