p2psp team mailing list archive

[Ilshat Shakirov <im.shakirov@xxxxxxxxx>]

Hello!,

Thanks for your feedback =)

I couldnt generalize my formula for different values of trusted peers and
attackers. But I generalized it for different number of trusted peers in
the team.
Here it is:

​where n is size of the team without splitter and T is number of trusted
peers.
The main idea is that the attacker will be detected when he will send
poisoned chunk to trusted peer. The time when he will send poisoned chunk
to trusted peer depends on position of trusted peer in his peer list.
So the denominator of fraction is just all the possible combinations of
trusted peers in peer list.
And the numerator is all possible combinations of T-1 trusted peers in peer
list. In more detail:
The attacker is able to send *#i* poisoned chunks when he has trusted peer
exactly in* #i* position in his peer list. In [1, #i) he can't have trusted
peers. So we have T-1 peers and we should place them in remaining positions
((#i, n-1)) of peer list.


Tomorrow I will perform experiments on simulator in order to confirm that
formula.
Now I don't know how to generalize the formula to different number of
attackers, because we expel attacker after we detect him and team size
become lower. I think I need help with that problem =)
Thanks in advance for your feedback =)

ps Python impl is OK =)

2015-03-31 21:19 GMT+06:00 Cristóbal Medina López <
cristobalmedinalopez@xxxxxxxxx>:

> Hi,
>
> It's clear now :)
>
> Thanks!
>
> El mar., 31 de marzo de 2015 a las 16:22, Vicente Gonzalez (<
> vicente.gonzalez.ruiz@xxxxxxxxx>) escribió:
>
>> Thanks!
>>
>> On Tue, Mar 31, 2015 at 2:17 PM Ilshat Shakirov <im.shakirov@xxxxxxxxx>
>> wrote:
>>
>>> ok, n = 4.
>>> Formula is for exactly 2 trusted peer. It shows the number of
>>> permutations of 2 trusted peers in node's peer list.
>>> So the size of peer list is n - 1 = 3;
>>> So the permutations will be
>>> p, T, T
>>> T, p, T
>>> T, T, p
>>>
>>>
>>> 2015-03-31 16:46 GMT+05:00 Cristóbal Medina López <
>>> cristobalmedinalopez@xxxxxxxxx>:
>>>
>>>> Hi,
>>>>
>>>> Yes, I mean the first one (N = (n - 1) * (n - 2) / 2 ). I still don't
>>>> get why N is the number of possible permutations in the attacker's peer
>>>> list. For a simple example where the team size is 4 (n=4). Could you write
>>>> down the 3 possible permutations?
>>>>
>>>> Thank you very much,
>>>> You're doing a great work.
>>>>
>>>> Regards.
>>>>
>>>> PS: We prefer work with pull requests on github ;)
>>>>
>>>> El mar., 31 de marzo de 2015 a las 12:10, Ilshat Shakirov (<
>>>> im.shakirov@xxxxxxxxx>) escribió:
>>>>
>>>>> Could you explain at length the previous formula? (anyway we think
>>>>>> that it also works perfectly)
>>>>>
>>>>> Sorry, I didn't understand your question. Do you mean
>>>>>
>>>>>> *N = (n - 1) * (n - 2) / 2*
>>>>>>
>>>>> or
>>>>>
>>>>>> http://p2psp.org/en/p2psp-protocol?cap=indexsu11.xht#x20-160004.11
>>>>>>
>>>>>  ?
>>>>>
>>>>> If you mean *N = (n - 1) * (n - 2) / 2* so it's a simply combination
>>>>> (n-1, 2).
>>>>> Btw, n is size of the team without splitter.
>>>>>
>>>>> 2015-03-31 14:33 GMT+05:00 Cristóbal Medina López <
>>>>> cristobalmedinalopez@xxxxxxxxx>:
>>>>>
>>>>>> Hi Ilshat,
>>>>>>
>>>>>> We think that the formula is fine. Only one question (see bellow):
>>>>>>
>>>>>> El lun., 30 de marzo de 2015 a las 14:58, Ilshat Shakirov (<
>>>>>> im.shakirov@xxxxxxxxx>) escribió:
>>>>>>
>>>>>>> Hello!,
>>>>>>>
>>>>>>> I got a new results from experiments with new parameters (2 trusted
>>>>>>> and one attacker), and it doesn't match with expected results from
>>>>>>> http://p2psp.org/en/p2psp-protocol?cap=indexsu11.xht#x20-160004.11
>>>>>>> (formula 11)
>>>>>>> But I deduced new formula (only for these params for now (T=2, A=1)):
>>>>>>>
>>>>>>> ​
>>>>>>> , where n is team size.
>>>>>>> ​Let me explain it:
>>>>>>> It just a formula for expected value for discrete random variable.
>>>>>>> So let describe our discrete variable:
>>>>>>> We have n peers, 2 trusted peers and one attacker. Size of each
>>>>>>> node's peer list is* n - 1*. Number of possible permutations for 2
>>>>>>> trusted peers in attacker's peer list is *N = (n - 1) * (n - 2) /
>>>>>>> 2.*
>>>>>>>
>>>>>>
>>>>>> Could you explain at length the previous formula? (anyway we think
>>>>>> that it also works perfectly)
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> The probability for getting only one poisoned chunk in the netowrk
>>>>>>> is *P(1) = (n - 2) / N*; (because we're getting only one poisoned
>>>>>>> chunk when trusted peer is the first in attacker's peer list, so there is
>>>>>>> n-2 variants of this situation).
>>>>>>> Next, *P(2) = (n - 3) / N*, P(x) =* (n - x - 1) / N*
>>>>>>> The max possible number of poisoned chunks in network with 2 trusted
>>>>>>> peer and one attacker is n - 2 (n - attacker - trusted);
>>>>>>> So, we must only to compute expected value as sum of *P(x)*x*.
>>>>>>>
>>>>>>> Formula can be easily generalized to different numbers of attackers
>>>>>>> and trusted peers, but first I want to know your opinion about it.
>>>>>>> What do you think? =)
>>>>>>> <https://en.wikipedia.org/wiki/Discrete_random_variable>
>>>>>>>
>>>>>>>
>>>>>> Please, check that the following python code implements your formula:
>>>>>>
>>>>>> x = 0.0
>>>>>> n = 10
>>>>>> for i in range(1,n-2):
>>>>>>     y=2.0*i*(n-i-1)/((n-1)*(n-2))
>>>>>>     print y, i
>>>>>>     x+=y
>>>>>> print x
>>>>>>
>>>>>> Thanks,
>>>>>> Regards.
>>>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> 2015-03-29 1:43 GMT+05:00 Ilshat Shakirov <im.shakirov@xxxxxxxxx>:
>>>>>>>
>>>>>>>> Hello!,
>>>>>>>>
>>>>>>>> Sorry for the delay in the response.
>>>>>>>> I have just improved the Peersim impl of P2PSP:
>>>>>>>> - malicious peer connects to the team after some delay (magic
>>>>>>>> constant :))
>>>>>>>> - *CHUNK *message have 4 times more delay than other messages
>>>>>>>> (hello, goodbye, etc.)
>>>>>>>> - trusted and malicious peers are chosen randomly at the begin of
>>>>>>>> simulation
>>>>>>>>
>>>>>>>> I have performed new experiments with these improvements, it can be
>>>>>>>> accessed at the same doc - https://docs.google.com/spreadsheets/d/
>>>>>>>> 1pc6yb87xJy8gNkWSWvvCvjAjR6WBFdOzCbPvO-zEooU/edit#gid=0 - it has 2
>>>>>>>> new tabs - raw2 and result2.
>>>>>>>> *raw2 *tab have 2 sets of data - the first one was performed
>>>>>>>> without different latencies, and the second one was performed with
>>>>>>>> different latencies.
>>>>>>>> Could you please evaluate results? What the next steps you want to
>>>>>>>> see with peersim impl of p2psp? =) I want to perform experiments with
>>>>>>>> different numbers of trusted peers and attackers, in order to confirm
>>>>>>>> theroretical analysis given in paper.
>>>>>>>>
>>>>>>>> Also, I want to store all the logs from each experiment in the same
>>>>>>>> place. I want to use dropbox for this (shared dir). What do you think? =)
>>>>>>>>
>>>>>>>> Currently, Im preparing scripts (bash and bat) to run simulation,
>>>>>>>> so there will be possible to perform experiments without setting up IDE.
>>>>>>>>
>>>>>>>> ps Could you please include me to sim project on github? Or we will
>>>>>>>> work with pull requests? =)
>>>>>>>>
>>>>>>>> Thanks in advance!
>>>>>>>>
>>>>>>>>
>>>>>>>> 2015-03-20 18:48 GMT+06:00 Vicente Gonzalez <
>>>>>>>> vicente.gonzalez.ruiz@xxxxxxxxx>:
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> 2015-03-20 9:59 GMT+01:00 Ilshat Shakirov <im.shakirov@xxxxxxxxx>:
>>>>>>>>>
>>>>>>>>> I don't know the procedure you are using to add peers to a team
>>>>>>>>>>> (how the peers contact the splitter, receives the list of peers of the
>>>>>>>>>>> splitter and send the [hello] message to the peers that are in the list),
>>>>>>>>>>> but I suppose that this procedure is similar to one used in a real team.
>>>>>>>>>>
>>>>>>>>>> Yes, the peers are added to team as it described in DBS of rules
>>>>>>>>>> (new peer sends HELLO to splitter, splitter sends list of peers, peer sends
>>>>>>>>>> HELLO to rest of team).
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> OK.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> I have new hypothesis - how much time is spent for sending
>>>>>>>>>> chunks? and for sending simple messages, like HELLO/GOODBYE. In peersim
>>>>>>>>>> implementation there is no difference in times between these two types of
>>>>>>>>>> message. If it's able to send 2 or more simple messages while one chunk is
>>>>>>>>>> sending, then simulation results will match with expected results.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> When a peer is introducing himself to the rest of the team only
>>>>>>>>> sends [hello]s. To interlace [hello]s and chunks, the splitter should send
>>>>>>>>> first to it a chunk, and this is done after receiving the list of peers
>>>>>>>>> from the splitter. This does not happen.
>>>>>>>>>
>>>>>>>>> In my opinion, a better result (not only for this experiment)
>>>>>>>>> could be obtained if you assign a latency to each message that depends on
>>>>>>>>> the message's length.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> This means that if the peer 34 were the trusted peer, the
>>>>>>>>>>> attacker would send only one poisoned chunk before it is reported. For this
>>>>>>>>>>> reason, I think that the order of the peers in the lists should have some
>>>>>>>>>>> influence in the average number of poisoned chunks.
>>>>>>>>>>
>>>>>>>>>> There is such results already. I.e. cell D43 in google sheet
>>>>>>>>>> <https://docs.google.com/spreadsheets/d/1pc6yb87xJy8gNkWSWvvCvjAjR6WBFdOzCbPvO-zEooU/edit#gid=0>.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I see :-)
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Also, I can remove the latency for simple messages (like hello
>>>>>>>>>> and goodbye), and (I suppose) results will match with expected results.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> No. Please, consider first my idea (longer messages will take more
>>>>>>>>> time traveling that shorter ones).  And, randomize, if possible, the order
>>>>>>>>> (or time) in which peers join the team.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> An accurate P2PSP simulator is very interesting for researching
>>>>>>>>>>> the performance of the P2PSP. Any kind of advance/facility in this
>>>>>>>>>>> direction is really appreciated :-)
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> Ok, I will begin to write readme file about performing
>>>>>>>>>> experiments =)
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Again, thanks. Your work will be very helpful!!
>>>>>>>>>
>>>>>>>>> Best,
>>>>>>>>> Vi.
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> Vicente González Ruiz
>>>>>>>>> Depto de Informática
>>>>>>>>> Escuela Técnica Superior de Ingeniería
>>>>>>>>> Universidad de Almería
>>>>>>>>>
>>>>>>>>> Carretera Sacramento S/N
>>>>>>>>> 04120, La Cañada de San Urbano
>>>>>>>>> Almería, España
>>>>>>>>>
>>>>>>>>> e-mail: vruiz@xxxxxx
>>>>>>>>> http://www.ual.es/~vruiz
>>>>>>>>> tel: +34 950 015711
>>>>>>>>> fax: +34 950 015486
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>
>>>