Game Theory In Peer To Peer Systems Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Peer-to-Peer Systems are distributed resource sharing computer systems. Unlike client-server systems there is no central authority in managing the system. No participant, or peer, in a P2P network either contributes or consumes. Instead each peer acts like both the client and the server at the same time. While each peer consumes resources he needs he also contributes some resources to the system that he already has. This allows P2P systems scale without crippling the network, unlike client-server systems where the increased number of users will induce heavy load on the server. Although with each user that joins the network the load on the network increases, the fact that the user also contributes to the system allows the network to scale without crippling itself. And unlike client-server systems where a server going down might mean the entire network crashing, in a P2P system problems in a single node does not affect the rest of the network. Hence P2P systems are very robust. Because P2P networks are made of many autonomous computers the creation and maintenance of one can be done at a very low cost. Which is another reason why P2P systems are so popular.

\section{Problem Definition}

Since P2P networks have no central authority to manage it, there is nothing preventing peers from consuming resources without contributing. This behaviour is known as free-riding and is one of the biggest potential drawbacks of the system. If peers consume without contributing the availability of shared resources might be weak, unpredictable or even completely unavailable. It has been found in \cite{eabh2000} that almost 70\% of the Gnutella file sharing network are consumers without contributing anything to the system. This is the main problem that prevents widespread deployment of P2P networks in more applications.

\section{Introduction to Game Theory}

Game theory is a branch of applied mathematics that's used in a wide array of fields including social science, economics, evolutionary biology, political science and computer science. It attempts to mathematically capture strategic situations (game) where two or more parties (players) are involved. The components of a strategic game are a set of players, a set of actions for each player, and for each player the set of actions he would prefer the other players to take when he takes a certain action. The final outcome of the game is decided by the decisions taken by all the players. A representation of a two player strategy game is shown in the following table. The actions player 1 can take are T and B while the actions player 2 can take are L and R. The numbers in each box are the utility of player 1 and player 2 in each set of actions.

\item (T,L) In this set of actions both players' utility is 2. But if the other player does not change his/her decision each player can increase his/her utility by choosing the other action.

\item (T,R) In this set of actions player 1 has a utility of 0 and player 2 has a utility of 3. Given player 2 does not change their action player 1 can increase his/her utility by changing his action.

\item (B,L) In this set of actions player 1 has a utility of 3 and player 2 has a utility of 0. Given player 1 does not change their action player 2 can increase his/her utility by changing his action.

\item (B,R) In this set of actions both players have a utility of 1. Given that one player does not change his/her action the other player cannot increase their utility by changing their choice. Hence this set of actions consists of the Nash equilibrium for this situation.

\section{Game Theory as A Tool to Strategize as well as Predict Nodes� Behaviour in Peer-to-Peer Networks}

In \cite{rgas2005} the authors treat each peer in the P2P system as a rational and strategic player who selfishly wants to maximize his/her own profit at minimal cost. They model the interaction of peers in a P2P system as an infinitely repeated game and compute the Nash equilibrium strategies (i.e. the participation level) of nodes in such a game. Peers use game theory principles to determine when they should or should not serve others.

The paper discusses the possibility of a basic reputation based incentive scheme to prevent free riding in the system. In their solution, when a user requests for service, the probability for obtaining it is directly proportional to the user�s reputation. Reputation increases when the user accepts a service request and decreases when it denies one. The authors use different weights for how much past and current actions affect reputation. \cite{ttgtp2p}

One important finding is that the Nash equilibrium strategy for the users is to serve with a probability that is greater than zero in each time period. In such a case free riding ceases to be a problem because it�s simply bad strategy. Another finding is that if the utility that can be gained from the network is much greater than contribution costs, optimal strategy can never be to share with a probability higher than 50 percent. It is noted that this leads to reduced system efficiency, since more than 50 percent of all service requests are denied. The authors also show that the more weight is given to past actions, the better the system performs since users have to regularly provide services to keep their reputation high enough. \cite{ttgtp2p}

In conclusion the authors note that there are several advantages to the proposed solution including fairness, simple implementation and the ease of calculating optimal strategies. Also it is assumed in the creation of this model that the cost and utility attached with serving and obtaining services are the same for all users and all types of services. It is mentioned that a more elaborate model considering the heterogeneity of all types of services and users will be created in the future.

\section{Free-Riding and Whitewashing in Peer-to-Peer Systems}

In \cite{mf2004} the authors develop a model to examine free-riding in P2P systems. In a system where the cost of contributing or sharing resources is low some users will continue to share out of their inherent generosity. The contribution cost is inversely proportional to the number of current users in the system. When the amount of free riders is high the authors discuss various penalizing mechanisms to discourage free riding.

When the number of free riders is high, the cost of contribution increases and therefore discourages contributors. This can lead to slow or zero performance of the system. The authors study penalizing mechanisms that can be used upon the free riders, reducing the overall contribution cost and keeping a stable level of performance within the system. The penalties can range from reducing the service the free riders get to completely being excluded from the system. The authors conclude that if the penalty of free riding is high enough and the probability of identifying the free riders is high a stable level of system performance can be attained.

The paper also discusses white washing that can occur on a P2P system. If the cost of creating a new identity on the system is very low some free riders will only create a new identity when penalized and continue consuming resources. To overcome this problem the authors suggest imposing a penalty on the newcomers to the system. Although this discourages white washers it reduces the performance of the system because this penalty is unavoidable and it will be imposed upon new contributors as well as the white washers. However the authors also point out this hit on performance is significant only if there is a high rate of new users joining the system. Another alternative is to increase the cost of a new identity to infinite levels. In that case white washing is impossible and the need for a penalty is non-existent.\cite{ttgtp2p}

In future work the authors plan to relax or modify some of the assumptions they have made in creating this model and plan to extend the model in several directions. These include additional incentive schemes, additional penalty forms, consideration of system dynamics such as arrival rates and departure rates, a non zero or non infinite positive identity cost and additional performance metrics.

\section{A Game Theoretic Framework for Incentives in P2P Systems}

In \cite{chira04} the authors consider the participants in a peer to peer system as a set of players in a strategy game. They study the interactions of the strategic and rational peers with the help of game theory and propose an incentive scheme based on differential service in order to eliminate free riding, improve the performance and availability of resources of the P2P system. In the beginning they consider the system as a homogeneous system where all users benefit equally from everybody else. They prove that there exists two Nash equilibria for contribution levels of the system and the one resulting in the optimal performance is realized.

Next the authors use a simulation to study the Nash equilibrium in a heterogeneous system. They show that these also converge on the desirable equilibrium independent on the number of users in the system. However, the bigger the system is, the more robust it is against loss of performance caused by peers leaving the system. It is also mentioned that the effect of non-cooperative peers on the system is to bias the equilibrium towards their contribution value, but that the effect is generally insignificant.

Finally, the authors suggest how to implement the proposed incentive model to existing peer to peer systems. They suggest that each peer accepts requests from other peers with a probability which is a function of the requesting peer's contribution level. To prevent rapid fire requests from the same peer trying to circumvent the system, it will be necessary to keep record of a request for a short period of time. The probability function could be a part of the system's architecture and thus same for all users and not modifiable by them. The contribution level of a peer could be calculated from the peer's uptime and its shared disk space and then it could be attached as an additional header in file request messages. New users can be given an initial contribution level so they could start using the system right away. To prevent peers from reporting their contribution levels falsely, the authors suggest implementing a neighbour audit scheme in which peers monitor the disk spaces and uptimes of their neighbour peers.\cite{ttgtp2p}

Although most of the above mentioned studies regard peers in the P2P network behave selfishly, it is not always accurate. In the Gnutella network and some BitTorrent trackers there is no incentive to share resources yet there are millions of files being shared. In \cite{pkil2001} the authors have discovered two incentives that could account for the users' willingness to contribute. One is the free-of-charge services and online chat rooms and newsgroups provided by the service may be sufficient to foster a sense of altruism in users. The other reason is files downloaded through the P2P service like BitTorrent are automatically shared unless the user specifically prohibits it from doing so. In such situations the cost of sharing is so cheap the users simply do not bother to opt out.

\section{Micro Payment Schemes}

In this section the authors of \cite{pkil2001} propose a micro payment scheme to encourage users to balance what they take from the system and what they contribute to the system. A natural way to do this is to charge every user for the resources they consume while rewarding the user for what they contribute. This method also requires a server to keep track of what users share and consume whilst not actively participating in the sharing process. The authors also propose several payment methods and analyze their effects on user behaviour in P2P networks by using a formal game theoretic model of the system. Although the incentives of such a system are obviously strong the implementation and practice of such systems are very difficult due to the fact that they require infrastructure for accounting and managing payments.

\section{Point Based Mechanisms}

In this section mechanisms that make use of an internal currency which are called �points� are considered. Peers are allowed to buy points either with money or with contributions to the network, but agents are not allowed to convert points back into money. \cite{pkil2001} Since agents cannot �cash out� their points, the mechanism must allow them to maintain a balance from one time period to the next. These kinds of mechanisms are used in the BitTorrent network by private torrent trackers. By implementing a passkey system the tracker can keep track of each user's resource usage and contributions and free riders can be blacklisted. \cite{bttrac} Since these trackers mostly use invitation only method for joining new users the possibility of white washing is also very low.

\section{Reciprocity Based Systems}

There are two kinds of reciprocity based schemes.


\item[Direct Reciprocity]: In these kinds of schemes the decision a user makes

about how to serve another user is based on the quality of service he previously received from that user. For example BitTorrent uses an incentive scheme of a variation of this scheme.\cite{bitto, ttgtp2p} Also the eMule file sharing network uses a credit based system where the more a user A uploads to user B, the less user A has to wait in queue when requesting a file from user B. Since the credits are not global and are between two specific users this is a direct reciprocity scheme.

\item[Indirect Reciprocity]: In such schemes the reputation of the users is tracked in order to provide better service for users with better reputation. \cite{ttgtp2p} In simple terms the more the user contributes the higher his reputation and vice versa. The main difference from a direct reciprocity scheme is that a user does not need to serve a certain user to get good service, he only needs to have a good reputation. This is more beneficial when a user does not have something another user directly wants. Indirect reciprocity schemes allow for greater scalability in the sense that in a large network it is unlikely two users will repeatedly interact.

In this survey we focused on studying the state of research into how game theory can be used in P2P systems. Most of the considered research was focused on P2P systems with low contribution costs such as file sharing networks. Game theory was applied into P2P systems in order to predict the strategies the participants of the P2P system will use to maximize their own utility. Most importantly it is used to overcome the biggest challenge of such systems; free riding behaviour. At the same time the performance of the network was monitored as the network would be useless if preventing free riding behaviour reduced the performance of the system.

Most of the research concentrates on incentive models based on reciprocation schemes to discourage or completely remove free riders from the P2P system. In most of these schemes some sort of punishment imposed on the peers that contribute too little to the system. There are also some researches done on complex monetary based incentive methods rewarding those who contribute to the system.

In P2P networks like BitTorrent even though the currently implemented schemes are not enough to completely discourage free riding these networks still perform because of altruism and the cost of sharing is low enough for users not to look for methods to cheat. But, since there are far more advanced uses for P2P networks other than file sharing such as grid computing, that are most costly to the contributors, relying on altruism is not enough. Because as the cost of sharing increases so does the users' tendency to try to get the maximum benefit at minimum cost selfishly. In such cases it is necessary to implement robust game theoretic solutions which offer no opportunities for free riding.