Reputation systems are essential to establish trust and to provide incentives for cooperation among users in decentralized networks. In these systems, the most widely used algorithms for computing reputations are based on random walks. However, in decentralized networks where nodes have only a partial view of the system, random walk-based algorithms can be easily exploited by uncooperative and malicious nodes. Traditionally, a random walk only uses information about the adjacency of nodes, and ignores their structural and temporal properties. Nevertheless, the properties of nodes indicate their reliability, and so, random walks using much richer information about the nodes than simple adjacency may achieve higher robustness against malicious exploitations. In this paper, we introduce the properties of nodes that are indicative of their reliability, and we propose a scheme to integrate these properties into the traditional random walks. Particularly, we consider two common malicious exploitations of random walks in decentralized networks, uncooperative nodes and Sybil attacks, and we show that integrating node properties into random walks results in much more robust reputation systems. Our experimental evaluation in synthetic graphs and graphs derived from real-world networks covering a significant number of users, shows the effectiveness of the resulting biased random walks.

Many peer-to-peer communities, including private BitTorrent communities that serve hundreds of thousands of users, utilize credit-based or sharing ratio enforcement schemes to incentivize their members to contribute. In this paper, we analyze the performance of such communities from both the system-level and the user-level perspectives. We show that both credit-based and sharing ratio enforcement policies can lead to system-wide "crunches" or "crashes," where the system seizes completely due to too little or too much credit, respectively. We present a theoretical model that identifies the conditions that lead to these system pathologies and we design an adaptive credit system that automatically adjusts credit policies to maintain sustainability. Given private communities that are sustainable, it has been demonstrated that they are greatly oversupplied in terms of excessively high seeder-to-leecher ratios. We further analyze the user-level performance by studying the effects of oversupply. We show that although achieving an increase in the average downloading speed, the phenomenon of oversupply has three undesired effects: long seeding times, low upload capacity utilizations, and an unfair playing field for late entrants into swarms. To alleviate these problems, we propose four different strategies, which have been inspired by ideas in social sciences and economics. We evaluate these strategies through simulations and demonstrate their positive effects.

A considerable body of research shows that Bit-Torrent provides very efficient resource allocation inside single swarms. Many BitTorrent clients also allow users to participate in multiple swarms simultaneously, and implement inter-swarm resource-allocation mechanisms that are used by millions of people. However, resource allocation across multiple swarms in BitTorrent has received much less attention. In this paper, we investigate whether currently prevalent inter-swarm resource allocation mechanisms perform acceptably or call for improvements. We use data from two BitTorrent communities and present results from trace-based simulations. Two use-cases for allocation mechanisms drive our evaluation: (1) file-sharing communities, whose objective is maximizing throughput, and (2) video-streaming communities, whose objective is maximizing the number of users receiving sufficient resources for uninterrupted streaming. To put the results from the analyzed mechanisms into perspective, we devise theoretical efficiency bounds for inter-swarm resource allocation, for which we map the resource allocation problem to a graph-theoretical flow network problem. In this formalism, the goal of the file-sharing use-case, throughput maximization, is equivalent to maximizing the flow in the network. The goal of the video-streaming use-case translates into finding a max-min fair allocation for BitTorrent downloading sessions, a problem for which we devise a new algorithm.

The efficiency of BitTorrent in content distribution has inspired a number of peer-to-peer (P2P) protocols for on-demand video (VoD) streaming systems (henceforth BitTorrent-like VoD systems). However, the fundamental quality-of-service (QoS) requirements of VoD (i.e. providing peers with a smooth playback continuity and a short startup delay) make the design of these systems more challenging than normal file-sharing systems. In particular, the bandwidth allocation strategy is an important aspect in the design of BitTorrent-like VoD systems, which becomes even more crucial in a scenario where a large number of peers joins in a short period of time, a phenomenon known as flashcrowd. In fact, the new joining peers all demand for content while having few or no pieces of content to offer in return yet. An unwise allocation of the limited bandwidth actually available during this phase may cause peers to experience poor QoS. In this work, we analyze the effects of a flashcrowd on the scalability of a BitTorrent-like VoD system and propose a number of mechanisms to make the bandwidth allocation in this phase more effective. In particular, we derive an upper bound for the number of peers that can be admitted in the system over time and we find that there is a trade-off between having the seeders minimize the upload of pieces already injected recently and high peer QoS. Based on the insights gained from our analysis, we devise some flashcrowd-handling algorithms for the allocation of peer bandwidth to improve peer QoS during flashcrowd. We validate the effectiveness of our proposals by means of extensive simulations.

Many private BitTorrent communities employ Sharing Ratio Enforcement (SRE) schemes to incentivize users to contribute their upload resources. It has been demonstrated that communities that use SRE are greatly oversupplied, i.e., they have much higher seeder-to-leecher ratios than communities in which SRE is not employed. The first order effect of oversupply under SRE is a positive increase in the average downloading speed. However, users are forced to seed for extremely long times to maintain adequate sharing ratios to be able to start new downloads. In this paper, we propose a fluid model to study the effects of oversupply under SRE, which predicts the average downloading speed, the average seeding time, and the average upload capacity utilization for users in communities that employ SRE. We notice that the phenomenon of oversupply has two undesired negative effects: a) Peers are forced to seed for long times, even though their seeding efforts are often not very productive (in terms of low upload capacity utilization); and b) SRE discriminates against peers with low bandwidth capacities and forces them to seed for longer durations than peers with high capacities. To alleviate these problems, we propose four different strategies for SRE, which have been inspired by ideas in social sciences and economics. We evaluate these strategies through simulations. Our results indicate that these new strategies release users from needlessly long seeding durations, while also being fair towards peers with low capacities and maintaining high system-wide downloading speeds.

In a typical BitTorrent swarm, a large proportion of the peers are behind firewalls or NATs. These peers are called unconnectable. When developing P2P applications, a main requirement is to handle unconnectable peers appropriately. One important aspect of this problem, which has not been emphasized so far, is understanding the difference between the attributes of unconnectable peers and peers in the open Internet. For example, if unconnectable peers spend much less time online, or if they download significantly more, exploiting these facts helps to optimize the implementation, and ignoring these facts can even lead to severe performance problems. Comparing open and unconnectable peers is not easy because most traces contain no information about connect ability. Here we study two large traces collected in two private BitTorrent communities: FileList.org and BitSoup.org, both of which contain the connect ability attribute. From these traces we extract several attributes of individual online sessions, swarms, and users. We compare the distributions of these attributes over unconnectable and open peers. We find that there are some potentially important differences, e.g., unconnectable users tend to have a lot more sessions, and they tend to spend slightly more time online. Some of our findings are in contradiction with previous results that were based on a different trace collection methodology.

Distributed systems without a central authority, such as peer-to-peer (P2P) systems, employ incentives to encourage nodes to follow the prescribed protocol. Game theoretic analysis is often used to evaluate incentives in such systems. However, most game-theoretic analyses of distributed systems do not adequately model the repeated interactions of nodes inherent in such systems. We present a game-theoretic analysis of a popular P2P protocol, Bit-Torrent, that models the repeated interactions in such protocols. We also note that an analytical approach for modeling incentives is often infeasible given the complicated nature of most deployed protocols. In order to comprehensively model incentives in complex protocols, we propose a simulation-based method, which we call Design Space Analysis (DSA). DSA provides a tractable analysis of competing protocol variants within a detailed design space. We apply DSA to P2P file swarming systems. With extensive simulations we analyze a wide-range of protocol variants and gain insights into their robustness and performance. To validate these results and to demonstrate the efficacy of DSA, we modify an instrumented BitTorrent client and evaluate protocols discovered using DSA. We show that they yield higher system performance and robustness relative to the reference implementation.

The efficiency of BitTorrent for file sharing has inspired a number of BitTorrent-based P2P protocols for Video-on-Demand (VoD). It has been shown that these systems are scalable in steady-state: the service quality provided to the users does not depend on the number of users in the system. However, it is not well understood how these systems scale under flash-crowds. In this work, we model a general BitTorrent-like VoD system and we find that under a flash-crowd the quality-of-service (QoS) degrades with the number of users. Also, our analysis shows that, at the very beginning of a flash-crowd, the maximum number of simultaneous users that can obtain a given service level is intrinsically related to two fundamental system parameters, namely the initial service capacity and the efficiency of piece exchange of the underlying P2P protocol. Finally, we illustrate the impact of peers turning into seeders (i.e peers that have finished downloading and remain in the system to upload) on the system scale.

This paper presents new, simple arguments improving the lower bounds for the total energy and the minimal inter-particle distance in minimal energy atom cluster problems with interactions given by a Morse potential, where the atom separation problem is difficult due to the finite energy at zero atom separation. Apart from being sharper than previously known bounds, they also apply for a wider range ρ ≥ 4.967 of the parameter in the Morse potential. Most results also hold for more general pair potentials.

Characterization of trajectory structure of fitness landscapes is a major problem of evolutionary computation theory. In this paper a hardness measure of fitness landscapes is introduced which is based on statistical properties of trajectories. These properties are approximated with the help of a heuristic based on the transition probabilities between the elements of the search space. This makes it possible to compute the measure for some well-known functions: a ridge function, a long path function, a fully deceptive function and a combinatorial problem: the subset sum problem. Using the same transition probabilities the expected number of evaluations needed to reach the global optimum from any point in the space are approximated and examined for the above problems.