lian maze iptps06

Robust Incentives via Multi-level Tit-for-tat : Robust Incentives via Multi-level Tit-for-tat Qiao Lian, Zheng Zhang (MSRA) Yu Peng, Mao Yang, Yafei Dai, Xiaoming Li (PKU) IPTPS, Feb. 2006


P2P file-sharing needs incentives to work : P2P file-sharing needs incentives to work genuine incentives: must collaborate/share to benefit E.g. block exchange in BT Problems: only works within a large session Nearly 80% sessions contain 2 peers only, i.e. there is only one downloader No one else to collaborate with!


A simple breakdown of the spectrum : A simple breakdown of the spectrum Artificial incentive: Produce/record evidence of collaboration for future reference Incentives Private history Shared history subjective Non-subjective genuine incentives Artificial incentives The sum of contribution from the perspective of other peers, weighted by their reputation (e.g. EigenTrust) Absolute contribution (e.g. Maze) Brittle to collusion and other problems


Talk organization : Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion


Maze:architecture : Maze: architecture A sends query server responses with file / replica info A sends download requests B and C response with file data B and C upload traffic log A B C centralize maintained index / membership user cloud Our work starts from these logs


Vital statistics : Vital statistics Popular Population: 1.4 million registered accounts; 30,000+ online users More than 200 million files More than 13TB (!) transfer everyday Completely developed, operated and deployed by an academic team Logs added since the collaboration w/ MSRA in 2004 Enable detailed study at all angles


Maze：Incentive Policies : Maze：Incentive Policies New users: points == 4096 Point change: Uploads: +1.5 points per/MB Downloads: at most -1.0 point/MB Gives user more motivation to contribute Benefit of high point Climbing ladder  social status Service differentiation: Order download requests by T = Now – 3log(Point) Users with P < 512 have a download bandwidth of 200Kb/s Available in Maze5.0.3; extensively discussed in Maze forum before implemented


Talk organization : Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion


What is collusion : What is collusion Definition (Webster dictionary): secret agreement or cooperation especially for an illegal or deceitful purpose And in the Maze context: Multiple peers collude to defeat the incentive system What makes the study hard: Even with all the traffic logs, we will never know for sure But we can identify suspicious colluding patterns See our technical report for more details


the collusion workingset : the collusion workingset Repeat traffic detector Hint: colluders are lazy for peer pair link: duplication degree = total traffic / unique data 221,000 pairs whose duplication degree > 1 the top 100 pairs with most redundant traffic


A closer look… : A closer look… (David, Alice, Quincy) e.g. Alice uploads MSDN DVD image (~3GB) for 29 times (Fred, Gary) (Olga, Pam) (Harry, Cindy) Pair-wise collusion Ted: 3.8TB Ingrid: 78GB Sam: 47GB Mary: 73GB Star-shape collusion (spam account): colluding + whitewashing account


Talk organization : Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion


What about EigenTrust? : What about EigenTrust? EigenTrust: clone of PageRank Basic idea: Consider recommender’s reputation Trust matrix M: mi,j: trust of peer i to peer j (e.g download quantity) normalize each row of M: EigenTrust vector: The left principal eigenvector T The rank of peer i is Ti


What about EigenTrust? : What about EigenTrust? EigenTrust: clone of PageRank Basic idea: Consider recommender’s reputation Trust matrix M: mi,j: trust of peer i to peer j (e.g download quantity) normalize each row of M: EigenTrust vector: The left principal eigenvector T The rank of peer i is Ti 9GB 9GB 1GB 10GB 1GB 10GB B C A 30GB


False negative of EigenTrust : False negative of EigenTrust Does the 734KB upload to Ted really matter? No, Ted is an irrational user It downloads only 124MB, but uploads 3.8TB. How the leg-hugger has high score: leg-hugger Larry


False positive of EigenTrust(local distributor Wayne) : False positive of EigenTrust (local distributor Wayne) Wayne is in a satellite cluster Wayne uploads 290GB. Its EigenRank equals to a peer in majority community with 10GB upload Is it fair? At least, Wayne should have high rank inside the satellite cluster. We need personalized rank for each peer, e.g. Tit-for-Tat Local distributor Wayne 5600GB


Talk organization : Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion


Private history: Tit-for-Tat : Idea: trust peers (friends) who has helped me before Used in eMule and BitTorrent (the 2 popular P2P filesharing system) Private history: Tit-for-Tat


Private history: Tit-for-Tat : Idea: trust peers (friends) who has helped me before Used in eMule and BitTorrent (the 2 popular P2P filesharing system) Problem: extremely small coverage Private history: Tit-for-Tat Limited coverage even with longer history


Talk organization : Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion


Multi-trust incentive algorithm : Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list Idea: we need more than one tier of trust!


Multi-trust incentive algorithm : Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list Idea: we need more than one tier of trust


Multi-trust incentive algorithm : Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list Idea: we need more than one tier of trust


Multi-trust incentive algorithm : Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list Idea: we need more than one tier of trust


Multi-trust incentive algorithm : Multi-trust incentive algorithm Idea: needs more than one tier of trust get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list …… A C D E F B A C D E F B 1-hop friends 2-hop friends 3-hop friends other peers


Multi-trust incentive algorithm : Multi-trust incentive algorithm get friends’ 1-hop friends build friends’ friend list, i.e., 2-hop friend list get friends’ 2-hop friends build 3-hop friend list M M2 M3 Mathematically answer: use full spectrum { M, M2, … M∞ } Idea: needs more than one tier of trust


Multi-trust incentive algorithm : Multi-trust incentive algorithm Evaluation: Coverage: real trace driven simulation of one month Effectiveness: statically evaluate the next 2 weeks traffic Metric: colluder’s queue position at the data source peer multi-trust: the full spectrum incentive algorithm Tit-for-Tat M∞T: EigenTrust Coverage { M, M2, … M∞ } Personalization


Talk organization : Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion


Multi-trust incentive algorithmCoverage experiment : Multi-trust incentive algorithm Coverage experiment The coverage of {M, M2} is already good enough We can choose using {M, M2, M∞ }


Multi-trust incentive algorithm: Effectiveness expr. methodology : Multi-trust incentive algorithm: Effectiveness expr. methodology Setup Generating rank based on one months history Evaluate the next two weeks Metric: We don’t have a global rank … Queue Position at each source peer: Source peers: who holds interested resource to me


Multi-trust incentive algorithm: dealing with colluders : Multi-trust incentive algorithm: dealing with colluders Spam account colluder 5/7 punish Ingrid equally Peer 7 punishes more in multi-trust Peer 4 punishes less in multi-trust since it downs from Ingrid Pair-wise colluder 7/9 punish Cindy equally 2/9 punish more in multi-trust Friends get ahead! Desirable: as good as EigenTrust


Multi-trust incentive algorithm:solve problems in EigenTrust : Multi-trust incentive algorithm: solve problems in EigenTrust Leg-hugger 78% peers rank Larry lower 22% are still affect by super peers Ted. Local distributor Inside: 2/3 peers promote Wayne’s rank 1/3 is too young to know Wayne’s good Outside: another friend False-negative False-positive


Talk organization : Talk organization The Maze p2p file sharing system Existing collusion behaviors Why simple algorithms do not work EigenTrust and Tit-for-Tat Multi-trust algorithm Evaluation Summary and Related work Conclusion


Summary and Related Work : Summary and Related Work


Conclusion : Conclusion EigenTrust and Tit-for-tat each have their own pitfall Multi-trust as a hybrid achieves better balance


Thank you : Thank you Q&A