EigenTrust

Information about EigenTrust

Published on December 18, 2007

Author: Miguel

Source: authorstream.com

Content

The EigenTrust Algorithm for Reputation Management in P2P Networks:  The EigenTrust Algorithm for Reputation Management in P2P Networks Sepandar D. Kamvar Mario T. Schlosser Hector Garcia-Molina Stanford University Problem:  Problem: Reduce inauthentic files distributed by malicious peers on a P2P network. Motivation: Problem “Major record labels have launched an aggressive new guerrilla assault on the underground music networks, flooding online swapping services with bogus copies of popular songs.” -Silicon Valley Weekly Problem:  Problem Goal: To identify sources of inauthentic files and bias peers against downloading from them. Method: Give each peer a trust value based on its previous behavior. Some approaches:  Some approaches Past History Friends of Friends EigenTrust Terminology:  Terminology Local trust value: cij. The opinion that peer i has of peer j, based on past experience. Global trust value: ti. The trust that the entire system places in peer i. Peer 1 Peer 3 Peer 2 Peer 4 Local Trust Values:  Local Trust Values Each time peer i downloads an authentic file from peer j, cij increases. Each time peer i downloads an inauthentic file from peer j, cij decreases. Peer i Peer j Cij= Normalizing Local Trust Values:  Normalizing Local Trust Values All cij non-negative ci1 + ci2 + . . . + cin = 1 Local Trust Vector:  Local Trust Vector Local trust vector ci: contains all local trust values cij that peer i has of other peers j. Some approaches:  Some approaches Past History Friends of Friends EigenTrust Past history:  Past history Each peer biases its choice of downloads using its own opinion vector ci. If it has had good past experience with peer j, it will be more likely to download from that peer. Problem: Each peer has limited past experience. Knows few other peers. Friends of Friends:  Friends of Friends Ask for the opinions of the people who you trust. Friends of Friends:  Friends of Friends Weight their opinions by your trust in them. The Math:  The Math Problem with Friends:  Problem with Friends Either you know a lot of friends, in which case, you have to compute and store many values. Or, you have few friends, in which case you won’t know many peers, even after asking your friends. Dual Goal:  Dual Goal We want each peer to: Know all peers. Perform minimal computation (and storage). Knowing All Peers:  Knowing All Peers Ask your friends: t=CTci. Ask their friends: t=(CT)2ci. Keep asking until the cows come home: t=(CT)nci. Minimal Computation:  Minimal Computation Luckily, the trust vector t, if computed in this manner, converges to the same thing for every peer! Therefore, each peer doesn’t have to store and compute its own trust vector. The whole network can cooperate to store and compute t. Non-distributed Algorithm:  Non-distributed Algorithm Initialize: Repeat until convergence: Distributed Algorithm:  Distributed Algorithm No central authority to store and compute t. Each peer i holds its own opinions ci. For now, let’s ignore questions of lying, and let each peer store and compute its own trust value. Distributed Algorithm:  Distributed Algorithm For each peer i { -First, ask peers who know you for their opinions of you. -Repeat until convergence { -Compute current trust value: ti(k+1) = c1j t1(k) +…+ cnj tn(k) -Send your opinion cij and trust value ti(k) to your acquaintances. -Wait for the peers who know you to send you their trust values and opinions. } } Probabilistic Interpretation:  Probabilistic Interpretation Malicious Collectives:  Malicious Collectives Pre-trusted Peers:  Pre-trusted Peers Battling Malicious Collectives Inactive Peers Incorporating heuristic notions of trust Convergence Rate Pre-trusted Peers:  Pre-trusted Peers Battling Malicious Collectives Inactive Peers Incorporating heuristic notions of trust Convergence Rate Secure Score Management:  Secure Score Management Two basic ideas: Instead of having a peer compute and store its own score, have another peer compute and store its score. Have multiple score managers who vote on a peer’s score. Score Manager Score Managers Distributed Hash Table How to use the trust values ti:  How to use the trust values ti When you get responses from multiple peers: Deterministic: Choose the one with highest trust value. Probabilistic: Choose a peer with probability proportional to its trust value. Load Distribution:  Load Distribution Deterministic Download Choice Probabilistic Download Choice Threat Scenarios:  Threat Scenarios Malicious Individuals Always provide inauthentic files. Malicious Collective Always provide inauthentic files. Know each other. Give each other good opinions, and give other peers bad opinions. More Threat Scenarios:  More Threat Scenarios Camouflaged Collective Provide authentic files some of the time to trick good peers into giving them good opinions. Malicious Spies Some members of the collective give good files all the time, but give good opinions to malicious peers. Malicious Individuals:  Malicious Individuals Malicious Collective:  Malicious Collective Camouflaged Collective:  Camouflaged Collective Malicious Spies:  Malicious Spies Simulations:  Simulations Conclusion:  Conclusion Eigentrust Dramatically reduces number of inauthentic files on the network. Robust to malicious peers. Low overhead. The End:  The End Paper available at http://www.stanford.edu/~sdkamvar/research.html Revised Non-distributed Algorithm:  Revised Non-distributed Algorithm Initialize: Repeat until convergence: Simulator:  Simulator Query-Cycle Simulator Models Peer Behavior. Query Behavior, Uptime, Activity, Authenticity Interests (Content Categories) Models Peer Content Assigns files to each peer based on interests, volume. Schlosser, Condie, and Kamvar, “Simulating a File-Sharing P2P Network” 1st SemPGRID Workshop, 2003 (http://dbpubs.stanford.edu/pub/2003-28) Computation:  Computation How long does it take for the cows to come home? Haveliwala and Kamvar, “The Second Eigenvalue of the Google Matrix” (http://dbpubs.stanford.edu/pub/2003-20)

Related presentations


Other presentations created by Miguel

Att5 India
27. 03. 2008
0 views

Att5 India

FAPRI Biofuels addendum 2
04. 10. 2007
0 views

FAPRI Biofuels addendum 2

agroterrorism
24. 10. 2007
0 views

agroterrorism

991112 price grid
24. 10. 2007
0 views

991112 price grid

56157
29. 10. 2007
0 views

56157

PMA URS31 IACSDUBAI VANCOUVER
08. 11. 2007
0 views

PMA URS31 IACSDUBAI VANCOUVER

jaipur
28. 11. 2007
0 views

jaipur

MH1
28. 11. 2007
0 views

MH1

ES 832 Lect 4
06. 12. 2007
0 views

ES 832 Lect 4

01guber
25. 10. 2007
0 views

01guber

Moore 16Mar05 Digits vs RDOs
01. 11. 2007
0 views

Moore 16Mar05 Digits vs RDOs

2007FLawards
02. 11. 2007
0 views

2007FLawards

ESD Wood preservatives BH
12. 11. 2007
0 views

ESD Wood preservatives BH

kotlerkeller chapter 14
15. 11. 2007
0 views

kotlerkeller chapter 14

ICATforWCC 002
16. 11. 2007
0 views

ICATforWCC 002

jaguar
20. 11. 2007
0 views

jaguar

Uganda
24. 10. 2007
0 views

Uganda

Predation07
30. 12. 2007
0 views

Predation07

Selim hydropower
22. 11. 2007
0 views

Selim hydropower

InstantMessaging
30. 12. 2007
0 views

InstantMessaging

2005 skin ppt
03. 01. 2008
0 views

2005 skin ppt

Crypto durant la 2nd guerre
04. 01. 2008
0 views

Crypto durant la 2nd guerre

absorption
04. 01. 2008
0 views

absorption

Tech Preso
07. 01. 2008
0 views

Tech Preso

Andhra Pradesh
07. 01. 2008
0 views

Andhra Pradesh

Pumpkins Squash
05. 11. 2007
0 views

Pumpkins Squash

Target System Design Update
07. 11. 2007
0 views

Target System Design Update

SgrA Reid
15. 11. 2007
0 views

SgrA Reid

The Next Great Generation
02. 10. 2007
0 views

The Next Great Generation

Carlstrom
14. 11. 2007
0 views

Carlstrom

MTTppsb
05. 11. 2007
0 views

MTTppsb

installingvaporrecov ery
06. 11. 2007
0 views

installingvaporrecov ery

ShiftShare
20. 02. 2008
0 views

ShiftShare

ch5FamilyCharacteris tics
24. 02. 2008
0 views

ch5FamilyCharacteris tics

zuccaarl08
27. 02. 2008
0 views

zuccaarl08

Bill Presentation
05. 03. 2008
0 views

Bill Presentation

1 HGIS011006
25. 10. 2007
0 views

1 HGIS011006

matmata
12. 12. 2007
0 views

matmata

SKADS MCCT Controllers 22032007
14. 03. 2008
0 views

SKADS MCCT Controllers 22032007

WSISRO Openinghbn110702
30. 03. 2008
0 views

WSISRO Openinghbn110702

cert microsoft 03
28. 11. 2007
0 views

cert microsoft 03

g rime
06. 11. 2007
0 views

g rime

MalaysiaMar2206
13. 04. 2008
0 views

MalaysiaMar2206

Buildup Activities
22. 11. 2007
0 views

Buildup Activities

Unit 5 1 2004
01. 01. 2008
0 views

Unit 5 1 2004

rm1910
30. 10. 2007
0 views

rm1910

TRIMS InvClimate Eng
26. 10. 2007
0 views

TRIMS InvClimate Eng

02 06 chistov
27. 09. 2007
0 views

02 06 chistov

BioBank SheilaCasserly
28. 09. 2007
0 views

BioBank SheilaCasserly

atividadefisicaeobes idade
28. 12. 2007
0 views

atividadefisicaeobes idade

code invaders
06. 11. 2007
0 views

code invaders

saghala Cedric Patin
28. 11. 2007
0 views

saghala Cedric Patin