Algorithms for performance and trust in peer-to-peer systems

Peer-to-Peer (P2P) computing defines a class of systems and applications where autonomous hosts (peers) pool their resources and collaborate to perform a special task. The performance of a P2P system is governed by the combined efforts in its design at three layers: efficient distributed algorithms in overlay routing layer, effective techniques to exploit the characteristics on underlying network layer, and robust mechanisms for providing peers with incentives to cooperate at application layer.; This thesis studies several problems in P2P system design at the three layers, and presents algorithmic techniques to address them.; At the overlay routing layer we are concerned with the design of distributed algorithms for information storage and retrieval. We use the Freenet anonymous publishing system as a case study to show how the small-world model can be applied to it for optimized content dissemination, and enable an unstructured system to give the same asymptotic routing performance as structured P2P systems like Chord.; At the underlying network layer, the impact of physical network characteristics on the asymptotic performance of P2P systems is studied. We discuss how the underlying network's latency expansion affects overlay routing latency stretch, and empirically determine the latency expansion characteristic of the Internet. Further, a simple random sampling scheme is proposed for exploiting the underlying network proximity. It incurs little network overhead and obtains optimal latency stretch in a large class of P2P systems.; At the application layer peer autonomy may cause free-riders and malicious users. We advocate the use of reputation systems to build social trust as a countermeasure. Two distributed rating schemes are presented in keeping with the design philosophy of many of P2P systems. Using intuitions from PageRank's random walk model, we further propose and evaluate a collusion-robust ranking scheme for a class of eigenvector-based reputation systems.; This thesis presents a set of incrementally deployable solutions for existing P2P systems to address the above design issues. These algorithms further form the base of a P2P information sharing infrastructure the design goal of which is to unify dynamic virtual communities on the Internet.