| To fully utilize the power of the World Wide Web, users must be able to find the information they want. However, the current dominant search engine model is that of a centralized search engine. The centralized model has a number of potential problems, such as a single point of vulnerability to attack or disruption. An alternative model is a distributed, decentralized search engine. This model avoids the problems of a centralized engine, but it has a different set of challenges in coordination of the components, managing the overhead of its own structure, and being robust to failures. This dissertation presents the Information Discovery Graph (IDG), a framework for a distributed search engine that is based on this decentralized approach. The IDG design addresses the challenges of the distributed model with a self-configuring, adaptive structure based on a hierarchical taxonomy. Multicast is used to coordinate components in the IDG, and the overhead of these messages is controlled by tight multicast scoping and efficient message protocols. The IDG provides robustness by automatic detection of node failures and automatic configuration of on-demand backup nodes. Estimates and initial simulation results are used to demonstrate these features and to show the scalability and performance of this design. |
