Multi-Trust-Incentives: Difference between revisions
| (37 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
= Multi-Trust-Incentives = |
= Multi-Trust-Incentives = |
||
The major problem of private history based incentive systems is their coverage. Resolving it requires leveraging other reputable |
The major problem of private history based incentive systems like Tit-for-Tat is their coverage. Resolving it requires leveraging other reputable |
||
peers’ history which leads directly to the EigenTrust mechanism. Multi-Trust-Incentives try to mix both mechanisms. |
peers’ history which leads directly to the [[EigenTrust]] mechanism. Multi-Trust-Incentives try to mix both mechanisms. |
||
== Design of Multi-Trust-Incentives == |
== Design of Multi-Trust-Incentives == |
||
| Line 9: | Line 9: | ||
====One-Step-Matrix==== |
====One-Step-Matrix==== |
||
| ⚫ | |||
{| style="float:right; background:transparent; padding:0px; margin:0px;" |
|||
|[[Image:matrix.jpg|thumb|center|200px]] |
|||
| ⚫ | |||
All values are measured as the normalized download volume that a peer i has received from a peer j during a period of time. |
All values are measured as the normalized download volume that a peer i has received from a peer j during a period of time. |
||
|} |
|||
====Two-Step-Matrix==== |
====Two-Step-Matrix==== |
||
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
|||
|[[Image:M_Quadrat.jpg|thumb|center|200px]] |
|||
|- |
|||
|} |
|||
A two-step-matrix <math>M^2</math> describes the relation in 3 levels. |
A two-step-matrix <math>M^2</math> describes the relation in 3 levels. |
||
===Implementation === |
===Implementation === |
||
====Idea==== |
|||
For a duration of t, a peer i computes his own matrix by normalizing all the downloads it received from a peer j. Periodically i will ask j for j's immediate friends so j computes its own matrix. |
|||
This process is repeated iteratively until i can not get any more matrices from j. |
|||
==== Data Costs within the Maze ==== |
|||
Within the [[The Maze Peer-To-Peer System|Maze]] Network a peer i has about 36 friends for one day in average. Gathering Information about one-level friends needs 32KB data space in total. Even with level two, it becomes about 1MB for information about peers. Furthermore a daily update does not produce any significant overhead. |
|||
But moving to higher levels costs for peer information are progressively growing. |
|||
In the end this Multi-Trust Incentive was developed just for level two because it already covers more than 60% of total traffic. |
|||
==== Implementation in the Maze ==== |
|||
== Performance == |
== Performance == |
||
===Coverage Experiment=== |
===Coverage Experiment=== |
||
| ⚫ | |||
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
|||
|[[Image:Cindy.jpg|thumb|center|300px]] |
|||
|[[Image:Ingrid.jpg|thumb|center|300px]] |
|||
|} |
|||
| ⚫ | |||
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
|||
|[[Image:Larry.jpg|thumb|center|300px]] |
|||
|- |
|||
|} |
|||
===Satellite Cluster Experiment=== |
===Satellite Cluster Experiment=== |
||
{| style="float:center; background:transparent; padding:0px; margin:0px;" |
|||
|[[Image:Wayne.jpg|thumb|center|300px]] |
|||
|- |
|||
|} |
|||
== Evaluation == |
== Evaluation == |
||
In general private history based incentives like Tit-for-Tat and shared-history based algorithms like EigenTrust have weaknesses. |
|||
Based on the experiments within the Maze networkt it is considered to mix both incentive systems into the proposed Multi-Trust Algorithm. |
|||
Such hybrid algorithms achieve the best performance in a P2P network. |
|||
== External Links == |
== External Links == |
||
*[http://iptps06.cs.ucsb.edu/papers/Lian-maze06.pdf Developer Homepage] |
|||
*[http://www.stanford.edu/~sdkamvar/papers/eigentrust.pdf Eigentrust] |
|||
Latest revision as of 16:00, 5 August 2007
Multi-Trust-Incentives
The major problem of private history based incentive systems like Tit-for-Tat is their coverage. Resolving it requires leveraging other reputable peers’ history which leads directly to the EigenTrust mechanism. Multi-Trust-Incentives try to mix both mechanisms.
Design of Multi-Trust-Incentives
Mathematical View
One-Step-Matrix
| The Evaluation of Trust between peers is measured in a Matrix M. This N * N matrix defines a one-step rank among peers.
All values are measured as the normalized download volume that a peer i has received from a peer j during a period of time. |
Two-Step-Matrix
A two-step-matrix describes the relation in 3 levels.
Implementation
Idea
For a duration of t, a peer i computes his own matrix by normalizing all the downloads it received from a peer j. Periodically i will ask j for j's immediate friends so j computes its own matrix. This process is repeated iteratively until i can not get any more matrices from j.
Data Costs within the Maze
Within the Maze Network a peer i has about 36 friends for one day in average. Gathering Information about one-level friends needs 32KB data space in total. Even with level two, it becomes about 1MB for information about peers. Furthermore a daily update does not produce any significant overhead. But moving to higher levels costs for peer information are progressively growing. In the end this Multi-Trust Incentive was developed just for level two because it already covers more than 60% of total traffic.
Implementation in the Maze
Performance
Coverage Experiment
Leg-Hugger Experiment
Satellite Cluster Experiment
Evaluation
In general private history based incentives like Tit-for-Tat and shared-history based algorithms like EigenTrust have weaknesses. Based on the experiments within the Maze networkt it is considered to mix both incentive systems into the proposed Multi-Trust Algorithm. Such hybrid algorithms achieve the best performance in a P2P network.