Multi-Trust-Incentives: Difference between revisions

From
Jump to navigation Jump to search
 
(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====

The Evaluation of Trust between peers is measured in a Matrix M. This N * N matrix defines a one-step rank among peers.
{| style="float:right; background:transparent; padding:0px; margin:0px;"
|[[Image:matrix.jpg|thumb|center|200px]]

|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.
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===

===Lag-Hugger Experiment===
{| style="float:center; background:transparent; padding:0px; margin:0px;"
|[[Image:Cindy.jpg|thumb|center|300px]]
|[[Image:Ingrid.jpg|thumb|center|300px]]
|}

===Leg-Hugger Experiment===

{| 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

Matrix.jpg
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

M Quadrat.jpg

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

Cindy.jpg
Ingrid.jpg

Leg-Hugger Experiment

Larry.jpg

Satellite Cluster Experiment

Wayne.jpg

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