Recently there has been an increasing demand for efficient mechanisms of carrying out computations that exhibit coarse grained parallelism. Examples of this class of problems include simulations involving Monte Carlo methods, computations where numerous, similar but independent, tasks are performed to solve a large problem or any solution which relies on ensemble averages where a simulation is run under a variety of initial conditions which are then combined to form the result. With the ever increasing complexity of such applications, large amounts of computational power are required over a long period of time. Economic constraints entail deploying specialized hardware to satisfy this ever increasing computing power. We address this issue in Dispatch, a peer-to-peer framework for sharing computational power. In contrast to grid computing and other institution-based CPU sharing systems, Dispatch targets an open environment, one that is accessible to all the users and does not require any sort of membership or accounts, i.e. any machine connected to the Internet can be the part of framework. Dispatch allows dynamic and decentralized organization of these computational resources. It empowers users to utilize heterogeneous computational resources spread across geographic and administrative boundaries to run their tasks in parallel. As a first step, we address a number of challenging issues involved in designing such distributed systems. Some of these issues are forming a decentralized and scalable network of computational resources, finding sufficient number of idle CPUs in the network for participants, allocating simulation tasks in an optimal manner so as to reduce the computation time, allowing new participants to join the system and run their task irrespective of their geographical location and facilitating users to interact with their tasks (pausing, resuming, stopping) in real time and implementing security features for preventing malicious users from compromising the network and remote machines. As a second step, we evaluate the performance of Dispatch on a large-scale network consisting of 10−130 machines. For one particular simulation, we were able to achieve up to 1500 million iterations per second as compared to 10 million iterations per second on one machine. We also test Dispatch over a wide-area network where it is deployed on machines that are geographically apart and belong to different domains.

Trust is required in file sharing peer-to-peer (P2P) systems to achieve better cooperation among peers and reduce malicious uploads. In reputation-based P2P systems, reputation is used to build trust among peers based on their past transactions and feedbacks from other peers. In these systems, reputable peers will usually be selected to upload requested files, decreasing significantly malicious uploads in the system. This thesis surveys different reputation management systems with a focus on reputation based P2P systems. We breakdown a typical reputation system into functional components. We discuss each component and present proposed solutions from the literature. Different reputation-based systems are described and analyzed. Each proposed scheme presents a particular perspective in addressing peers’ reputation. This thesis also presents a novel trust management framework and associated schemes for partially decentralized file sharing P2P systems. We address trust according to three identified dimensions: Authentic Behavior, Credibility Behavior and Contribution Behavior. Within our trust management framework, we proposed several algorithms for reputation management. In particular, we proposed algorithms to detect malicious peers that send inauthentic files, and liar peers that send wrong feedbacks. Reputable peers need to be motivated to upload authentic files by increasing the benefits received from the system. In addition, free riders need to contribute positively to the system. These peers are consuming resources without uploading to others. To provide the right incentives for peers, we develop a novel service differentiation scheme based on peers’ contribution rather than peers’ reputation. The proposed scheme protects the system against free-riders and malicious peers and reduces the service provided to them. In this thesis, we also propose a novel recommender framework for partially decentralized file sharing P2P systems. We take advantage from the partial search process used in these systems to explore the relationships between peers. The proposed recommender system does not require any additional effort from the users since implicit rating is used. The recommender system also does not suffer from the problems that affect traditional collaborative filtering schemes like the Cold start, the Data sparseness and the Popularity effect. Over all, our unified approach to trust management and recommendations allows for better system health and increased user satisfaction.

Peer-to-peer (p2p) approaches are an increasingly effective way to deploy services. Popular examples include BitTorrent, Skype, and KaZaA. These approaches are attractive because they can be highly fault-tolerant, scalable, adaptive, and less expensive than a more centralized solution. Cooperation lies at the heart of these strengths. Yet, in settings where working together is crucial, a natural question is: "What if users stop cooperating?" After all, cooperative services are typically deployed over multiple administrative domains, and thus vulnerable to Byzantine failures and users who may act selfishly. This dissertation explores how to construct p2p systems to tolerate Byzantine participants while also incentivizing selfish participants to contribute resources. We describe how to balance obedience against choice in building a robust p2p live streaming system. Imposing obedience is desirable as it leaves little room for peers to attack or cheat the system. However, providing choice is also attractive as it allows us to engineer flexible and efficient solutions. We first focus on obedience by using Nash equilibria to drive the design of BAR Gossip, the first gossip protocol that is resilient to Byzantine and selfish nodes. BAR Gossip relies on verifiable pseudo-random partner selection to eliminate non-determinism, which can be used to game the system, while maintaining the robustness and rapid convergence of traditional gossip. A novel fair enough exchange primitive entices cooperation among selfish peers on short timescales, thereby avoiding the need for distributed reputation schemes. We next focus on tempering obedience with choice by using approximate equilibria to guide the construction of a novel p2p live streaming system. These equilibria allow us to design incentives to limit selfish behavior rigorously, yet provide sufficient flexibility to build practical systems. We show the advantages of using an [element of]-Nash equilibrium, instead of an exact Nash, to design and implement FlightPath, our live streaming system that uses bandwidth efficiently, absorbs flash crowds, adapts to sudden peer departures, handles churn, and tolerates malicious activity. / text

Trust is required in file sharing peer-to-peer (P2P) systems to achieve better cooperation among peers and reduce malicious uploads. In reputation-based P2P systems, reputation is used to build trust among peers based on their past transactions and feedbacks from other peers. In these systems, reputable peers will usually be selected to upload requested files, decreasing significantly malicious uploads in the system. This thesis surveys different reputation management systems with a focus on reputation based P2P systems. We breakdown a typical reputation system into functional components. We discuss each component and present proposed solutions from the literature. Different reputation-based systems are described and analyzed. Each proposed scheme presents a particular perspective in addressing peers’ reputation. This thesis also presents a novel trust management framework and associated schemes for partially decentralized file sharing P2P systems. We address trust according to three identified dimensions: Authentic Behavior, Credibility Behavior and Contribution Behavior. Within our trust management framework, we proposed several algorithms for reputation management. In particular, we proposed algorithms to detect malicious peers that send inauthentic files, and liar peers that send wrong feedbacks. Reputable peers need to be motivated to upload authentic files by increasing the benefits received from the system. In addition, free riders need to contribute positively to the system. These peers are consuming resources without uploading to others. To provide the right incentives for peers, we develop a novel service differentiation scheme based on peers’ contribution rather than peers’ reputation. The proposed scheme protects the system against free-riders and malicious peers and reduces the service provided to them. In this thesis, we also propose a novel recommender framework for partially decentralized file sharing P2P systems. We take advantage from the partial search process used in these systems to explore the relationships between peers. The proposed recommender system does not require any additional effort from the users since implicit rating is used. The recommender system also does not suffer from the problems that affect traditional collaborative filtering schemes like the Cold start, the Data sparseness and the Popularity effect. Over all, our unified approach to trust management and recommendations allows for better system health and increased user satisfaction.

Given a set of peers with overlapping interests where each peer wishes to keep track of new documents that are relevant to their interests, we propose Shrack-a self-organizing peer-to-peer (P2P) system for document sharing and tracking. The goal of a document-tracking system is to disseminate new documents as they are published. We present a framework of Shrack and propose a gossip-like pull-only information dissemination protocol. We explore and develop mechanisms to enable a self-organizing network, based on common interest of document sets among peers. Shrack peers collaboratively share new documents of interest with other peers. Interests of peers are modeled using relevant document sets and are represented as peer profiles. There is no explicit pro file exchange between peers and no global information available. We describe how peers create their user pro files, discover the existence of other peers, locally learn about interest of other peers, and finally form a self-organizing overlay network of peers with common interests. Unlike most existing P2P file sharing systems which serve their users by finding relevant documents based on an instant query, Shrack is designed to help users that have long-term interests to keep track of relevant documents that are newly available in the system. The framework can be used as an infrastructure for any kind of documents and data, but in this thesis, we focus on research publications. We built an event-driven simulation to evaluate the performance and behaviour of Shrack. We model simulated users associated with peers after a subset of authors in the ACM digital library metadata collection. The experimental results demonstrate that the Shrack dissemination protocol is scalable as the network size increases. In addition, self-organizing overlay networks, where connections between peers are based on common interests as captured by their associated document sets, can help improve the relevance of documents received by peers in terms of F-score over random peer networks. Moreover, the resulting self-organizing networks have the characteristics of social networks.

In this paper, we consider the peer-to-peer transfer of popular files between devices in a wireless mesh network. We address the problem that occurs when multiple nodes try to access the same file simultaneously, resulting in increased contention on the shared wireless channel. To counteract this problem, we propose a cooperative file transfer protocol which splits a file into fixed-sized pieces and allows simultaneous downloads of such pieces from multiple peers. Opposed to previous approaches, the proposed protocol selects the potential download peers such that the corresponding download paths possess minimum interference among each other. In a performance study where we compare our approach with other download schemes proposed in the literature, we show that our cooperative protocol roughly halves the time required for downloading a file.

We developed a diffusive load balancing scheme that equalizes the available capacities of nodes in a peer-to-peer (P2P) system. These nodes may have different resource capacities, geographic locations, or availabilities (i.e., length of time being part of the peer-to-peer system). The services on these nodes may have different service times and arrival rates of requests. Using the diffusive scheme, the system is able to maintain similar response times for its services. Our scheme is a modification of the diffusive load balancing algorithms proposed for parallel computing systems. This scheme is able to handle services with heterogeneous resource requirements and P2P nodes with heterogeneous capacities. We also adapted the diffusive scheme to clustered peer-to-peer system, where a load balancing operation may move services or nodes between clusters. After a literature survey of this field, this thesis investigates the following issues using analytical reasoning and extensive simulation studies. The load balancing operations equalize the available capacities of the nodes in a neighborhood to their averages. As a result, the available capacities of all nodes in the P2P system converge to a global average. We found that this convergence is faster when the scheme uses neighborhoods defined by the structure of the structured P2P overlay network rather than using randomly selected neighbors. For a system with churn (i.e. nodes joining and leaving), the load balancing operations maintain the standard deviation of the available capacities of nodes within a bound. This bound depends on the amount of churn and the frequency of load balancing operations, as well as on the capacities of the nodes. However, the sizes of the services have little impact on this bound. In a clustered peer-to-peer system, the size of the bound largely depends on the average cluster size. When nodes are moved among clusters for load balancing, the numbers of cluster splits and merges are reduced. This may reduce the maintenance cost of the overlay network.

We developed a diffusive load balancing scheme that equalizes the available capacities of nodes in a peer-to-peer (P2P) system. These nodes may have different resource capacities, geographic locations, or availabilities (i.e., length of time being part of the peer-to-peer system). The services on these nodes may have different service times and arrival rates of requests. Using the diffusive scheme, the system is able to maintain similar response times for its services. Our scheme is a modification of the diffusive load balancing algorithms proposed for parallel computing systems. This scheme is able to handle services with heterogeneous resource requirements and P2P nodes with heterogeneous capacities. We also adapted the diffusive scheme to clustered peer-to-peer system, where a load balancing operation may move services or nodes between clusters. After a literature survey of this field, this thesis investigates the following issues using analytical reasoning and extensive simulation studies. The load balancing operations equalize the available capacities of the nodes in a neighborhood to their averages. As a result, the available capacities of all nodes in the P2P system converge to a global average. We found that this convergence is faster when the scheme uses neighborhoods defined by the structure of the structured P2P overlay network rather than using randomly selected neighbors. For a system with churn (i.e. nodes joining and leaving), the load balancing operations maintain the standard deviation of the available capacities of nodes within a bound. This bound depends on the amount of churn and the frequency of load balancing operations, as well as on the capacities of the nodes. However, the sizes of the services have little impact on this bound. In a clustered peer-to-peer system, the size of the bound largely depends on the average cluster size. When nodes are moved among clusters for load balancing, the numbers of cluster splits and merges are reduced. This may reduce the maintenance cost of the overlay network.

We developed a diffusive load balancing scheme that equalizes the available capacities of nodes in a peer-to-peer (P2P) system. These nodes may have different resource capacities, geographic locations, or availabilities (i.e., length of time being part of the peer-to-peer system). The services on these nodes may have different service times and arrival rates of requests. Using the diffusive scheme, the system is able to maintain similar response times for its services. Our scheme is a modification of the diffusive load balancing algorithms proposed for parallel computing systems. This scheme is able to handle services with heterogeneous resource requirements and P2P nodes with heterogeneous capacities. We also adapted the diffusive scheme to clustered peer-to-peer system, where a load balancing operation may move services or nodes between clusters. After a literature survey of this field, this thesis investigates the following issues using analytical reasoning and extensive simulation studies. The load balancing operations equalize the available capacities of the nodes in a neighborhood to their averages. As a result, the available capacities of all nodes in the P2P system converge to a global average. We found that this convergence is faster when the scheme uses neighborhoods defined by the structure of the structured P2P overlay network rather than using randomly selected neighbors. For a system with churn (i.e. nodes joining and leaving), the load balancing operations maintain the standard deviation of the available capacities of nodes within a bound. This bound depends on the amount of churn and the frequency of load balancing operations, as well as on the capacities of the nodes. However, the sizes of the services have little impact on this bound. In a clustered peer-to-peer system, the size of the bound largely depends on the average cluster size. When nodes are moved among clusters for load balancing, the numbers of cluster splits and merges are reduced. This may reduce the maintenance cost of the overlay network.

Cette thèse s'inscrit dans le domaine de l'expérimentation sur les systèmes distribués, et en particulier de leur test ou de leur validation. À côté des méthodes d'évaluation classiques (modélisation, simulation, plates-formes d'expérimentation comme PlanetLab ou Grid'5000) les méthodes basées sur l'émulation et la virtualisation proposent une alternative prometteuse. Elles permettent d'exécuter l'application réelle à étudier, en lui présentant un environnement synthétique, correspondant aux conditions d'expérience souhaitées : il est ainsi possible, à moindre coût, de réaliser des expériences dans des conditions expérimentales différentes, éventuellement impossibles à reproduire dans un environnement réel. Mais l'utilisation de tels outils d'émulation ne peut se faire sans répondre à des questions sur leur réalisme et leur passage à l'échelle. Dans ce travail, nous utilisons une démarche incrémentale pour construire une plate-forme d'émulation destinée à l'étude des systèmes pair-à-pair à grande échelle. Nous commençons par comparer les différentes solutions d'émulation logicielle de liens réseaux, puis illustrons leur utilisation, notamment en étudiant une application réseau complexe : TUNS, un tunnel IP sur DNS. Nous construisons ensuite notre plate-forme d'émulation, P2PLab, en utilisant l'un des émulateurs réseaux précédemment étudiés, ainsi qu'un modèle de topologies réseaux adapté à l'étude des systèmes pair-à-pair. Nous y proposons une solution légère de virtualisation, permettant un bon rapport de repliement (grand nombre de noeuds émulés sur chaque machine physique). Après avoir validé cette plate-forme, nous l'utilisons pour étudier le protocole de diffusion de fichiers pair-à-pair BitTorrent à l'aide d'expériences mettant en jeu près de 15000 noeuds participants.