Distributed systems that allow any user to enroll his node as a participant must resolve two main challenges to achieve reliability: selecting trustworthy participants, and detecting and containing the damage of deviant nodes. This research addresses these challenges by (a) presenting a new system architecture, F2F, that incorporates decentralized trust relationships among users in determining trustworthy nodes and (b) devising new techniques to detect and contain faults of misbehaving nodes in the context of concrete applications using this new architecture. This research demonstrates the usefulness of F2F through the design and implementation of two case-study systems: cooperative backup and censorship circumvention. Friendstore provides inexpensive and reliable backup by storing each user's data on a subset of trusted neighbors. Such an architecture allows Friendstore to use less expensive technical means to detect and recover from faults but makes it harder to fully utilize storage resources. This project addresses this challenge using coding techniques that allow a node to efficiently provide data redundancy for multiple neighbors simultaneously. The second case study system, Kaleidoscope, helps users inside censored domains access blocked websites by relaying traffic via a network of proxies. Kaleidoscope uses a novel protocol to disseminate proxy identities over the F2F trust graph so that each node can only collect limited information about others' identities. A few malicious nodes, then, cannot discover a significant fraction of proxies. This project will produce systems that, if successfully deployed, provide inexpensive online storage to home users and help circumvent censorship for millions of affected users.
CAREER: Decentralizing Trust in Open Distributed Systems