Multi-Trust-Incentives: Difference between revisions

From
Jump to navigation Jump to search
 
(17 intermediate revisions by 2 users not shown)
Line 2: Line 2:


The major problem of private history based incentive systems like Tit-for-Tat 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 19: Line 19:
====Two-Step-Matrix====
====Two-Step-Matrix====


{| style="float:left; background:transparent; padding:0px; margin:0px;"
{| style="float:center; background:transparent; padding:0px; margin:0px;"
|[[Image:M_Quadrat.jpg|thumb|center|200px]]
|[[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 ===
{| style="float:left; background:transparent; padding:0px; margin:0px;"


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


|====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.
This process is repeated iteratively until i can not get any more matrices from j.


|==== Data Costs within the Maze ====
==== 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.
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.
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.
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 ====
==== 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 ==

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