Documents

9 pages
13 views

When can an autonomous reputation scheme discourage free-riding in a peer-to-peer system?

of 9
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
When can an autonomous reputation scheme discourage free-riding in a peer-to-peer system?
Transcript
  When Can an Autonomous Reputation Scheme Discourage Free-riding in aPeer-to-Peer System? Nazareno Andrade 1 , Miranda Mowbray 2 , Walfredo Cirne 1 , Francisco Brasileiro 1 1 Universidade Federal de Campina Grande { nazareno,walfredo,fubica } @dsc.ufcg.edu.br  2  HP Laboratories Bristolmiranda mowbray@hp.com Abstract We investigate the circumstances under which it is pos-sible to discourage free-riding in a peer-to-peer system for resource-sharing by prioritizing resource allocation to peers with higher reputation. We use a model to predict conditions necessary for any reputation scheme to succeed in discouraging free-riding by this method. We show withsimulations that for representative cases, a very simple au-tonomous reputation scheme works nearly as well at dis-couraging free-riding as an ideal reputation scheme. Fi-nally, we investigate the expected dynamic behavior of thesystem. 1 Introduction Peer-to-peer systems can be an effective and robust wayof sharing resources. However, the effectiveness of severalexisting peer-to-peer systems is diminished by widespreadfree-riding [1, 15, 16]. A peer that is a free-rider consumesresources donated by others but does not donate any re-sources itself. If there is a nonzero cost of donation, andthe system does not discriminate between free-riders andother peers, then peers have an economic incentive to be-come free-riders, thus reducing the resources available fordonation in the community, and diminishing the utility of the system as a whole.One potential solution is to introduce a reputationscheme to the system. The interactions between peers af-fect their reputation in a way designed so that free-ridersare unlikely or unable to build up a high reputation. When apeer has a resource to donate, and there are several peers re-questing this resource, the peers with higher reputation aregiven priority. The idea is that the advantage that this givesto peers who donate resources may be enough to overcomethe disadvantage given by the cost of donation.This use of reputation differs from the classic use of rep-utation [14] to enhance the quality of transactions in peer-to-peer systems such as eBay [6], or to marginalize untrust-worthypeersasinthesystemssurveyedbyOoietal.[12]. If reputation is used to discourage free-riding then the choiceto interact with a peer with high reputation is made in orderto reward the peer for its previous behaviour, rather than toenhance the expected quality of the immediate transaction.We are particularly interested in the circumstances underwhich it is possible to discourage free-riders using an au-tonomous reputation scheme. In an autonomous reputationscheme, peers use only local information to prioritize otherpeers. As such, they can only access reputation informa-tion involving peer-to-peer interactions in which they them-selves have participated. The reputation of a given peer willin general be different in the eyes of different peers, andthere is no attempt to reconcile these local reputations tocreate a global assessment. As a result, autonomous reputa-tion schemes are relatively simple to implement, and do notrequire a cryptographic infrastructure or centralized storageto guarantee integrity of data retrieved from other peers, asis the case for some other reputation schemes that assign asingle global reputation value to a peer. Autonomous rep-utation schemes are used in several peer-to-peer resource-sharing networks [2, 4, 7, 8].An alternative way of using a reputation scheme to dis-courage free-riders would be not to give peers with lowreputation low priority access to donated resources, but torefuse to donate resources altogether to peers with reputa-tion below some chosen limit: if a peer had resources todonate but only peers with low reputation requested them,then the resources would remain undonated. However, thisalternative would cause bootstrapping problems for an au-  tonomous reputation scheme, because a new collaboratorentering a system with autonomous reputation can onlyshow that it is not a free-rider by donating resources, andcan only detect that another peer is not a free-rider by be-ing donated resources by that peer. Hence in this paper weconsider the effect when the reputation scheme is used toprioritize donations rather than to ban certain kinds of do-nation completely.In this paper we explore the design space for a peer-to-peer system in which it is possible to discourage free-ridingby prioritizing resource donations using an autonomousreputation scheme.In [2] we described an extremely lightweight au-tonomous reputation scheme. This was designed to pro-mote equitable resource sharing in OurGrid, a peer-to-peersystemthatwearecurrentlydevelopingforsharingCPUcy-cles for bag-of-tasks applications [3]. For this autonomousreputation scheme, the reputation of peer P  1 in the eyes of peer P  2 is equal to the total value of resources that P  2 hasdonated P  1 , minus the total value of resources that P  1 hasdonated P  2 – or is zero if this value is negative. Throughsimulations of representative cases, we will demonstrate theeffectivenessofthis reputationschemeindiscouragingfree-riders when the system does not exhibit eager consumption,that is, when peers in consuming state have a limit on theamount of resources that they can use with positive utility.Non-eagerness is realistic if the resource being shared is forexample CPU time for applications that are not easily par-allelizable, or is access to a particular software application.We define a free-rider as a peer that does not contributeresources to the system, and a collaborator  as a peer thatdoes contribute resources. We say that the system works attime t if at that time there is a disincentive for collabora-tors to change their strategy to free-riding: in other words,if the expected utility for a collaborator is greater than theexpected utility the collaborator would have if it changedstrategy. Free-riders always have an expected utility at leastas great as the expected utility that they would have outsidethe system, and so if the system works then the expectedutility for collaborators in the system is greater than theirexpected utility if they left the system.In this paper we assume that peers in consuming statecan be donated resources by any collaborator in donatingstate. This implies that the resources are interchangeable,which can be the case if the system shares generic CPUtime, or bandwidth, or storage. However the analysis of this paper may not extend to peer-to-peer systems sharingless generic resources, such as data files, because a peer re-questing a specific file will not in general be able to receiveit from any peer currently donating resources, only fromthose peers currently donating resources that have a copy of the file. However, measurements of large scale peer-to-peerfile-sharing systems [11, 16] have found that a large per-centage of all requests are for a relatively small number of files. For each one of these popular files, we can considerthe peer-to-peer virtual subsystems consisting of requestsfor and donations of the file. Within each of these sub-systems the resources are interchangeable. It is intuitivelyreasonable that if each of these virtual subsystems satisfiesconditions that allow a particular reputation system to driveout free-riding, then by using the reputation system for theprioritization of donations in the file-sharing system as awhole it should be possible to discourage peers with typi-cal resource requirements from free-riding. A more preciseanalysis of the circumstances in which a reputation schemecan be used to discourage free-riding in a file-sharing sys-tem is beyond the scope of this paper.The rest of this paper is structured as follows. Aftera brief discussion of related work, we describe our au-tonomous reputation scheme and the design parameters forour system. Next we analyze the conditions on these pa-rameters for the system to work at a fixed time, and usethis analysis to predict system behaviour for some repre-sentative scenarios. We then simulate these scenarios forour reputation scheme to check that the predictions are met,and compare the performance of our scheme with that of anideal reputation scheme in the simulated scenarios. Finally,we investigate the dynamic behaviour of the system if peerschange their strategies according to their own economic in-terest. 2 Related Work Thererecentlyhasbeenanincreasingamountofresearchin the area of reputation schemes for peer-to-peer networks,particularlyforfile-sharingnetworks. However, mostofthisresearch is on schemes that are not autonomous. For anal-yses of the effect on free-riding of various non-autonomousreputation schemes, see for example [5, 9, 13].The file-distribution system BitTorrent [4] uses an au-tonomous tit-for-tat mechanism to decide to whom to up-load, at what bandwidth. However BitTorrent does notuse long-term reputation records, because the communityit serves is very dynamic and long-term peer relationshipsare unlikely.Autonomous reputation schemes are used in the peer-to-peer file-sharing networks eMule [7] and GNUnet [8], butwe are not aware of any analytical studies of the effect of these schemes on the amount of free-riding in these net-works.One previous paper, by Lai et al., [10], analyses the ef-fect on free-riding of an autonomous reputation scheme. Inthe scheme analysed, if peer A receives a request from peerB, peer A has made r > 0 requests to B in the past, and Bhas cooperated with c of these, then A cooperates with B’scurrent request with probability c/r . If resource contention  is possible, Lai et al’s scheme may result in some avail-able resources being wasted. For example, suppose that anavailable resource is requested by just one peer, but somepast requests from the resource owner were rejected by thatpeer because they were for contended resources. Then theavailable resource may not be donated. 3 System description In this section we describe our autonomous reputationscheme, and the design parameters for the peer-to-peerresource-sharing system that uses it. 3.1 The autonomous reputation scheme In our autonomous reputation scheme, which was in-troduced in [2], each peer P  1 keeps a local record of  V  ( P  1 ,P  2) and V  ( P  2 ,P  1) for each peer P  2 with whichit has interacted, where V  ( P  1 ,P  2) is the total value of resources that have been donated from P  1 to P  2 in thepast. Each time it makes or receives a donation from P  2 , P  1 updates this record, and recalculates its local reputationscore for P  2 , which which is equal to max { V  ( P  2 ,P  1) − V  ( P  1 ,P  2) , 0 } . We write r P  1 ( P  2) to denote this score.When peer P  1 has spare resources that are requested bymore than one other peer, it uses its local reputation scoresto prioritize its donations of these resources, giving highestpriority to satisfying the requests of the requesters P  forwhich r P  1 ( P  ) is largest.As an illustration, suppose that peers P  1 , P  2 , P  2 havenot interacted before. We have r P  1 ( P  2) = r P  1 ( P  3) =0 . If  P  2 donates a resource with value R to P  1 , r P  1 ( P  2) will increase to R (whereas r P  1 ( P  3) will remain zero). If then P  1 has a spare resource and has to choose between arequest for that resource from P  2 and a request from P  3 , P  1 will choose to donate the resource to P  2 . P  1 wouldmake the same decision if  P  3 had interacted with P  1 beforebut r P  1 ( P  3) was smaller than R . 3.2 System model We consider a peer-to-peer system comprised of a set of collaborators and free-riders. At a fixed time t , a peer canbe either in consuming or in non-consuming state. When innon-consuming state, collaborators donate their resources,while free-riders go idle. The design parameters that weconsider for the peer-to-peer system are: • Eagerness. We assume that for each peer there is amaximum value C > 0 of the utility of resources thatcan be consumed during a unit time interval when thepeer is in consuming state. Thus, C  limits the amountof resources that can be useful for a peer. The valueof  C  is fixed for a given peer, but may vary betweenpeers, with average value C  . • The probability ρ of a peer being in consuming state.We assume that at a given time each peer has an inde-pendent probability ρ of being in consuming state. • Cost of donation. The utility lost to the donator asa result of donation is a constant v times the utilitygained by the recipient as a result of the donation, with 0 < v < 1 . If resources are available for donation butare not donated, no utility cost associated with theseresources is incurred by the resource owner. • Value of donation. When a collaborator is not in con-suming state, it has resources of value D available todonate to the system. Note that D models performanceas well as theoretical capacity. For example, if a peerhas 1000 spare CPU cycles to donate, but its perfor-mance is bad and in practice the value it delivers whendonating 1000 cycles is only as good as if it had noperformance problems and donated 800 cycles, then D for the peer will be 800, not 1000. We assume thatthe value of  D is fixed for a given peer, but can varybetween different peers, with average value D . • The proportion f  t of peers that are free-riders at time t . The value f  t lies between 0 and 1. At time t , N.f  t peers will be free-riders and N. (1 − f  t ) collaborators,where N  is the total number of peers in the system.For our analysis and simulations we will assume that allthe values of the variables other than f  t are fixed over time.The protocol for donation of resources is that collabora-tors that are not in consuming state donate all the resourcesthat they have available as long as there are peers in con-suming state prepared to consume them. Peers with highreputation are given priority in donations. We assume thatthe granularity of resources is low enough that a donatingpeer with at least as many spare resources as a consumingpeer requests is able to give exactly the amount of resourcesrequested, if the donating peer wishes to do so. Any re-sources left over, after all peers in consuming state havebeen donated the maximum amount of resources that theyare prepared to accept, are not donated. Collaborators withresources to donate at a particular time do not have to do-nate them all to the same peer: they can donate resources toseveral different requesting peers. Free-riders that are not inconsuming state stay idle. 4 Analysis In this section we calculate the values of design param-eters for which an ideal reputation system succeeds in dis-couraging free-riding, and use approximations to give pre-dictions for the behaviour of sample scenarios.  Recall that we say that the system works at time t if atthat time there is a disincentive to collaborators to changetheir strategy to free-riding. Define the advantage to col-laborators at time t as the expected utility gain to a collab-orator as a result of being in the system minus the expectedutility gain to a free-rider. This is a measure of how muchfree-riding is discouraged at time t . It will in general be afunction of  f  t . The system works at time t with f  t = f  if and only if either f  ∈ (0 , 1) and the advantage to collabo-rators is positive at f  t = f  , or f  = 0 and the limit of theadvantage to collaborators as f  t → 0 is positive.Initially we pick a fixed time t , and calculate whether thesystem works at that time. Later on (in Section 6) we willdiscuss the dynamic behaviour of the system. 4.1 Analysis for fixed time For this subsection we will assume that the system usesan ideal reputation scheme that is able to identify free-ridersperfectly, that is, any free-rider always has a lower reputa-tion than any collaborator.Suppose at a fixed time t the total value of resources of-fered for donation is x d (and that this is greater than zero),the total value of resources requested by collaborators inconsuming state is x c , and the total value of resources re-quested by free-riders in consuming state is x f  . We distin-guish three cases, a famine of donations, a glut  of donations,and the middle case.The condition for famine is x d ≤ x c . If this holds, thenfree-riders receive no donations, so gain utility zero by be-ing in the system, whereas the set of collaborators gains atotal utility (1 − v ) .x d > 0 by being in the system. There-fore the advantage to collaborators is positive, and the sys-tem works at time t .The condition for glut is x d ≥ x c + x f  . If this holds,then all peers who make a request at time t will be donatedall the resources they request. The expected utility gain fora peer resulting from the resources it is donated depends on C  , but does not depend on whether the peer is a collaboratoror a free-rider. On the other hand, a collaborator has anexpected utility cost resulting from the resources it donates.So a collaborator can increase its overall expected utility bychangingitsstrategytofree-riding. Thereforetheadvantageto collaborators is negative, and the system does not work at time t .The condition for the middle case is that there is neitherfamine nor glut, ie. x c < x d < x c + x f  . In this case thetotal utility gain by the set of collaborators is x c − v.x d , andthe total utility gain by the set of free-riders is x d − x c . If  x c ≤ v.x d , then clearly the advantage to collaborators isnon-positive and the system does not work at time t . Sup-pose x c − v.x d is positive and f  t ∈ (0 , 1) . Then the advan-tage to collaborators is ( x c − v.x d )(1 − f  t ) .N  − ( x d − x c ) f  t .N  (1)which is a monotonically increasing function of  f  t thattends to minus infinity as f  t → 0 . So the system does notwork at time t for f  t = 0 , and works for f  t ∈ (0 , 1) if andonly if the value of this function is positive.Sofarwehaveassumedthatthereisnon-eagerconsump-tion. But a similar argument can be used if there is ea-ger consumption. Eager consumption can be modeled byputting x c = ∞ . This implies that the condition for famineholds, whatever the values of the other variables, and hencethe system works if there is eager consumption.In this subsection we have not assumed that the alloca-tion of resources to requesting collaborators favours thosecollaborators who have donated more. However, supposingit does, if there is famine and a collaborator acquires somenew spare resources additional to its srcinal resources of value D , then the collaborator has an incentive to donatethese new resources to the community, provided that doingso will not move the system out of the famine condition.We now use the results of this analysis to pick some rep-resentative scenarios for the system parameters, and makepredictions for the behaviour of the system for these scenar-ios. 4.2 Predictions for sample scenarios The mean values of  x d , x c and x f  can be expressed interms of the design parameters as (1 − ρ ) .D. (1 − f  t ) .N  , ρ.C. (1 − f  t ) .N  , and ρ.C.f  t .N  respectively. We can esti-mate whether the system will work or not at a fixed timefor a given set of parameter values, by determining whetherthe system will work for the mean values of  x d , x c and x f  .This is only an estimate, because the actual values fluctu-ate statistically about these values, but this is a reasonableapproximation to make because small changes in these val-ues will result in small changes in the utilities we calculate.(The approximation is less accurate if  D varies widely be-tween peers.)The scenarios we choose are the ones where the pa-rameter values satisfy D = 10 , C  = 9 D for each peer, C  = D for each peer, or C  = D/ 10 for each peer (recallthat D may vary from peer to peer); ρ ∈ { 0 . 1 , 0 . 5 , 0 . 9 } ; f  t ∈ { 0 . 25 , 0 . 5 , 0 . 75 } ; and v ∈ { 0 . 1 , 0 . 4 } . This makes atotal of 3 x 3 x 3 x 2 = 54 sets of parameter values.We have chosen these values to be realistic, to includeboth low and high realistic values, and to include some sce-narios where the mean values of  x d , x c and x f  are on theborderline between different cases.Our prediction, using the estimate given by taking themean values and applying the analysis of the previous sub-section, is that among these 54 sets of parameter values, as-  suming perfect identification of free-riders, the system willwork just for the 36 sets of parameter values that satisfy C  = 9 D , or C  = D and ρ = 0 . 9 , or C  = D and ρ = 0 . 5 ,or C  = D/ 10 and ρ = 0 . 9 . For the scenarios satisfying oneof the first three alternatives there is famine for the meanvalues, and the scenarios satisfying C  = D/ 10 and ρ = 0 . 9 the mean values are in the middle case with positive advan-tage to collaborators.Clearly, if the system will not work for an ideal reputa-tion system that has perfect identification of free-riders, itshould not work for a weaker reputation scheme. Our au-tonomous reputation scheme does not in general give per-fect identification of free riders, so for this scheme we pre-dict that the system will work for a subset of the 36 sets of parameter values identified above. 5 Simulations We now turn to simulations for the design parametersabove. The simulator simulates some aspects of a realimplementation (specifically, the fluctuations over time of amounts donated and requested) that are ignored by the an-alytical model. However it is not a total P2P system simula-tor, since for example it does not deal with topology issues.We aim to investigate the effectiveness of our autonomousreputation scheme in providing a positive advantage to col-laborators in the scenarios for which the analysis of the lastsection predicts that it is possible for a reputation schemeto do so. In order to provide a reference system, we simu-lated an ideal reputation scheme that perfectly identifies allfree-riders.In our simulations, the timeline is in turns, and at eachturn each peer has an independent probability ρ of being inconsuming state. We ran the scenarios described in Subsec-tion 4.2 with the value of donation D = 10 for all peers,using our autonomous scheme and using the ideal reputa-tion scheme.For both reputation schemes the advantage to collabora-tors in the simulations was positive for 35 of the 36 scenar-ios the analysis had predicted it would be positive. Also, for29 of these 35 scenarios the behavior of the the autonomoussceme in the simulations was close to the behavior of theideal reputation scheme. Figure 1 illustrates the comparisonof the advantage for collaborators between a system usingthe autonomous reputation sceme and the ideal reputationscheme for some of these scenarios, where the eagernesslevel C  = D and the cost of donation v = 0 . 4 .The scenarios where the difference between our au-tonomous reputation scheme and the ideal reputationscheme was significant were all the scenarios in which C  = 9 D and ρ = 0 . 1 . This difference is illustrated inFigure 2. The scenarios in which C  = 9 D and ρ = 0 . 1 are on the border between the famine and the middle case,so the statistical fluctuations in x d have a greater impact onthem. Indeed, it was in these scenarios that the advantage tocollaborators found in the simulation using the ideal reputa-tion scheme differed most from the the values predicted byour analysis, and also differed most from the values foundin the simulation of our autonomous reputation scheme.The sole scenario in which the system did not work usingour autonomous reputation scheme when the analysis pre-dicted that it would using a perfect reputation scheme wasthe one with C  = 9 D , ρ = 0 . 1 , f  = 0 . 25 and v = 0 . 4 . Thisscenario is also in the border between the famine and themiddle case, and setting f  = 0 . 25 and v = 0 . 4 is enoughto give a negative advantage to collaborators under our au-tonomous scheme. Note that these two parameter values de-fineascenariowherethereisarelativelylargecostofdonat-ingresources, andfewfree-riderstosharetheresourcestheymanage to get. The ideal reputation scheme, however, didnot perform much better in the simulation of this scenario:its advantage for collaborators stays fluctuating around zerowhen the system reaches steady state. So, according to ourdefinition, even when using a reputation scheme that per-fectly identifies free-riders, the system did not work all thetime in this scenario.As a second step, we introduced some new scenarioswhere peers do not have the same D (and, hence, not thesame C  ) or the same ρ . We investigated the cases whereeither D or ρ is given by the uniform distributions U  (1 , 19) or U  (0 . 1 , 0 . 9) , respectively.When D was given by a uniform distribution with mean 10 there was the same overall behavior as when D was setequal to 10 for all peers, and making ρ different for differ-ent peers had only a slightly greater impact. Although themean value of  ρ was equal to 0 . 5 in all our scenarios, thedifference between the performance of the system in pro-viding incentives for collaborations using our autonomousreputationschemeandusinganidealreputationschemewasgreater in the scenarios where different peers had differentvalues of  ρ . More specifically, the statistical fluctuations in x d made the difference in performance greater for the sce-narios where C  = D and f  = 0 . 25 and made the systemnot work when using our autonomous reputation scheme inthe two scenarios where C  = D , v = 0 . 4 , ρ = U  (0 . 1 , 0 . 9) and f  ∈ { 0 . 25 , 0 . 5 } . Once again, these scenarios are onthe border between the famine and middle cases. The sta-tistical fluctuations in x d arising from the differing valuesof  ρ regularly pushed the system into the middle case, inwhich our autonomous reputation scheme is less efficientat rewarding collaborators. When combined with the highcost of donation v = 0 . 4 , the effect was that the advantagetocollaborators wasnegativeforourautonomous reputationscheme in these scenarios.Still, the system using our autonomous reputationscheme performed similarly to one using an ideal reputation
Related Documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks