DiST: Fully Decentralized Indexing for Querying Distributed Multidimensional Datasets
Beomseok Nam, Alan Sussman · 2008
Grid computing and Peer-to-peer (P2P) systems are emerging as new paradigms for managing large scale distributed resources across wide area networks. While Grid computing focuses on managing heterogeneous resources and relies on centralized managers for resource and data discovery, P2P systems target scalable, decentralized methods for publishing and searching for data. In large distributed systems, a centralized resource manager is a potential performance bottleneck. Decentralization can help avoid this bottleneck, as is done in P2P systems. However, the query functionality provided by most existing P2P systems is very rudimentary, and is not directly applicable to Grid resource management. In this paper, we propose a fully decentralized multidimensional indexing structure, called DiST, that operates in a fully distributed environment with no centralized control. DiST can be applied to large distributed datasets, whether stored in a Grid or in a P2P system. We believe DiST is the first fully decentralized multidimensional indexing scheme for large distributed datasets in unstructured peer-to-peer systems. We describe the server join, query routing, and failure recovery algorithms and evaluate the performance of the scheme against a more structured hierarchical indexing scheme that we have previously shown to perform well in distributed environments. 1