Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19The EigenTrust Algorithm for Reputation Management in P2P Networks Sepandar D.Kamvar Mario T.Schlosser Hector Garcia-MolinaP2P Networks and Reputation Systems•P2P Networks–open and anonymous•Problem–Malicious peers–Inauthentic files•Reputation Systems–Centralized system (eBay)–Distributed System•Local Trust ValueijijtrsjiHow to Aggregate Local Trust Values?•Aggregates the ratings of only a few peers–Can’t get a wide view about a peer’s reputation •Aggregates the ratings of all the peers–Congesting the network with system messages asking for each peer’s local trust values at every query•Global Trust Value–The overall estimation of , for each peer j–How to calculate these global trust values?ijsAggregating Local Trust Values•Normalizing Local Trust Values Why normalizing?•Aggregating Local Trust Values (transitive trust)A Probabilistic Interpretationjijijijssc)0,max()0,max(jjkijikcctijkijcjkc?ikcAggregating Local Trust Values (2) The global trust vector; also, the Eigenvector of C The global trust value of peer j (quantify how much trust the system as a whole places peer j)iTicCt ][ijcC inTcCt )(:t:jtBasic EigenTrust•Assumption: including server at this stage–A server stores all the values and performs the computationijcmei/1Practical Issues•A priori notions of trust–Can we assign any profit to newcomers?–Only the first few peers to join the network are known to be trustworthy– if , and otherwise–Use instead of ppi/1Pi 0ippePractical Issues(2)•Inactive Peers–What happens if peer i doesn't download from anybody else?–Choose to trust the pre-trusted peersPractical Issues(3)•Malicious Collectives–a group of malicious peers who know each other–How to prevent them from subverting the system?–The modified algorithm:patCatkTk )()1()1(Distributed EigenTrust•Assumption: Everyone is honest• Each peer compute its own global trust value: iknnikikiaptctcat )...)(1()()(11)1(Algorithm Complexity•The algorithm converges fast–A network of 100 peers after 100 query cyclesAlgorithm Complexity(2)•Specifically limit the number of local trust values that a peer reportsSecure Eigentrust•Malicious peers can report false trust values, subverting the system•Have a different peer compute the trust value of a peer•The trust value of one peer will be computed by more than one other peer•How to assign score mangers?Assign Score Managers•DHT (Distributed Hash Table)The AlgorithmUsing Global Trust Values•Have each peer download from the most highly trusted peer who responds to its query•Two problems–The most highly trusted peers be overloadedUsing Global Trust Values(2)–Does not allow newcomers to build reputation•Probabilistically based on the trust values–With a probability of 10%, select a peer j that has a zero trust value– cdtdtpersonal)1( Isolating Malicious PeersConclusion•Goal: minimize the impact of malicious peers on the P2P system•Using global trust value•Compute in a distributed
View Full Document
Unlocking...