Alexandria Digital Research Library

Trustworthy Distributed Search and Retrieval over the Internet

Chuang, Yung-Ting
Degree Grantor:
University of California, Santa Barbara. Electrical & Computer Engineering
Degree Supervisor:
P. Michael Melliar-Smith
Place of Publication:
[Santa Barbara, Calif.]
University of California, Santa Barbara
Creation Date:
Issued Date:
Engineering, Electronics and Electrical, Computer Science, and Engineering, Computer
Membership Churn
Information Networks
Performance Evaluation
Distributed Systems
Information Search and Retrieval
Malicious Attacks
Dissertations, Academic and Online resources
Ph.D.--University of California, Santa Barbara, 2013

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.

Physical Description:
1 online resource (214 pages)
UCSB electronic theses and dissertations
Catalog System Number:
Inc.icon only.dark In Copyright
Copyright Holder:
Yung-Ting Chuang
Access: This item is restricted to on-campus access only. Please check our FAQs or contact UCSB Library staff if you need additional assistance.