Currently, our trust in the accessibility of information over the Internet and the Web depends on benign and unbiased administration of centralized search engines. Unfortunately, a centralized search engine can be modified to filter, conceal, or censor information. We present a decentralized search and retrieval system, named iTrust, to address these problems.

First, we address the design and implementation of iTrust. Source nodes distribute metadata for information along with the address of the information to randomly chosen nodes. Similarly, requesting nodes distribute requests that contain keywords to randomly chosen nodes. Nodes that receive a request compare the keywords with the metadata they hold, and return the URL of the information to the requesting node if they have a match. For appropriate values of the parameters, the probability of a match is very high.

Next, we present statistical algorithms for detecting and defending against malicious attacks. Our statistical detection algorithm compares the empirical and analytical probabilities of a match to estimate the proportion of non-operational nodes in the membership. The defensive adaptation algorithm then increases the number of nodes to which the requests are distributed to maintain the same probability of a match when some of the nodes are non operational as when all of the nodes are operational.

Then, we consider an environment in which nodes join or leave the membership rapidly. Our adaptive membership protocol allows nodes to discover changes in the membership using the iTrust messages and responses that it normally receives. A node then dynamically adjusts its requesting rate, and sends more request messages to compensate for nodes from which it did not receive a response. The protocol exploits messages already being sent to distribute metadata or requests, thus reducing the need for additional messages.

Finally, we combine our adaptive membership protocol with our algorithms for detecting and defending against malicious nodes. The combined adaptation algorithm estimates changes in the membership to improve the behavior of iTrust. We demonstrate that the combined adaptive algorithm is effective and robust when the membership churn is high and when there are malicious nodes in the membership.