← Back to team overview

p2psp team mailing list archive

Re: CIS of rules (GSoC)

 

Hello!,

Sorry for the some delay.

Regarding math predictions about buffer correctness and avg. number of
rounds to expel all the malicious peers:
a) Buffer correctness
I don't know how to evaluate the buffer correctness in team with trusted
peers, but without them it's an easy task:
BC = 1 - M / (N - 1 + 1) = 1 - M / N, where M - number of malicious peers
and N - team size. I've confirmed this model with some experiments (using
my script, I've run the team without trusted peers).
b) Average Number of rounds
I've made some assumptions in this problem:
*1. The trusted peer checks every X-th chunk* (in current implementation X
is a random value)
2. *The probability to check chunk from malicious peer is P = M / (N - 1)
where M is number of malicious peer and N is a teamsize* (for one trusted
peer).

Let's calculate probability to check chunk from malicious peer for T (>1)
trusted peers. It will be:

​

> P(A) = T * (\frac{M}{N - 1} * (1 - \frac{M}{N - 1})^{T - 1})
>

Now we can use this formula:

This formula calculates probability to get one success from n experiments.
So, q = 1 - P(A), and we can assign P smth like 0.95 and calculate n -
required number of checks to discover malicious peer with prob. 0.95
Then, the required number of rounds to expel one malicious peer equals R =
n * X / N, where N is teamsize.

Now, I am performing tests with STrPe and STrPe-DS mechanisms, I will
provide some results asap.

Thanks!


2015-08-05 1:41 GMT+06:00 Juan Álvaro Muñoz Naranjo <juanalvaro83@xxxxxxxxx>
:

>
>
>
>
> One remarkable result here is the fact that having a second trusted peer
>> does not have a real impact on malicious peer expulsion. I realize now that
>> this is due to how the Str technique is designed. Not for GSoC, but maybe
>> we should think of a evolution of the protocol that reflected the
>> aggregation of trusted peers. Cristóbal, that might be intersting if it has
>> not been researched yet.
>>
>
> But adding second trusted peer accelerates the expulsion of attackers, you
> can see it in the last graphs (-m 50 -t 1 and -m 50 -t 2) : in the case of
> one trusted there not all attackers were expelled from the team for given
> time, and in the second case - all attackers were expelled by ~100 round.
>
>
> Ok let me rephrase like this: the addition of a second trusted peer has
> little impact. The speed at which expulsions are done is comparable, and
> for the 1 trusted peer case the remaining malicious peers are 1 or 2 at
> most. But you're right, having 2 peers eliminates all malicious peers in
> all cases, which is already a remarkable result ;)
>
> Can't wait to see what happens with 4 and 8!
>
> Juan
>

GIF image

GIF image


Follow ups

References