Efficient algorithms in selfish peer-to-peer networks: design and implementation
Jiang Guo · TSpace (University of Toronto) · 2007
Peer-to-peer networks are constructed in the application layer by peer nodes at the edge of wide-area networks, using the underlying IP network topology to forward application-layer messages. A fundamental fact is that participating nodes in peer-to-peer networks are noncooperative or selfish. This challenges the existing design paradigm for developing distributed algorithms, often assuming that participating nodes are cooperative. Consequently, the following question arises: How do we design and implement algorithms that can effectively and efficiently execute in selfish peer-to-peer networks? In this thesis, we resort to microeconomic theory as our tool to investigate node behavior and strategies, identifying specific issues that need to be addressed. Our goal is to design and implement "selfishness-aware" algorithms that function in selfish peer-to-peer networks. Particularly, we focus on three problems: (1) Why cannot we simply execute "selfishness-unaware" distributed algorithms in selfish peer-to-peer networks? (2) How do we provide proper incentives to selfish peer nodes so that the desired system output can be achieved? (3) How do we implement prototypes of decentralized protocols in a quick and efficient way? In light of the above problems, we have done extensive theoretical analysis and experiments towards the design of effective algorithms in non-cooperative overlay networks. Our main contributions are the following. First, using techniques in microeconomics theory, we have proposed and analyzed algorithms to mitigate information asymmetries in peer-to-peer networks, using peer-to-peer queries as a case study. Second, with the theory of mechanism design, we have designed incentives in peer-to-peer streaming applications, so that each node's utility maximizing efforts lead to the maximization of system-wide output, with respect to end-to-end throughput. Finally, we have designed and implemented iOverlay, an application development framework for peer-to-peer applications over the Internet. We have effectively used the iOverlay framework to streamline implementation efforts when we evaluate our peer-to-peer protocol design.