Date: Fri, 22 Feb 2008 14:29:13 +0000 (GMT)
From: Jan Sacha <jsacha@cs.tcd.ie>
To: Alberto Montresor <alberto.montresor@unitn.it>
Subject: Re: Potential bug in SG1

Hi Alberto,

I've done it. See the attached code please.

This is a crude list of changes to the original code.

- Added the SUPERPEERS set, as another instance of ReducedNewscast

- Extended RandomSpp: added a loop where super-peers compare the capacity 
of their clients with nodes in the SUPERPEER set, and swap them if needed

- Fixed SuperpeerObserver: changed the stop condition

- Updated one config file (sf-degree)

I didn't test it in all scenarios, but I hope it works ok.

Regs,
Jan


On Thu, 21 Feb 2008, Alberto Montresor wrote:

> Jan,
>  seems to me a good idea. Thanks for working on this.
>
> Alberto
>
> Jan Sacha wrote, On 02/21/2008 11:01 PM:
>>
>> Alberto,
>>
>> I think I found a relatively cheap solution.
>>
>> It can be assumed that every super-peer knows the capacity of its clients.
>> At every time step, a super-peer checks if there is a node in its
>> SUPERPEER set that has a lower capacity than the maximum capacity
>> client. If a node is found, their roles are swapped.
>>
>> The main advantage of this is that it does not require any extra
>> communication unless two peers are actually swapped. The comparison of
>> capacity can be done without any message exchange.
>>
>> The convergence time to the target topology is probably linear with the
>> number of super-peers in the system - not great but should be good
>> enough. Finally, experiments get a bit more complicated because the
>> SUPERPEER set has to be simulated, but the changes in the code should
>> not be drastic.
>>
>> I'll try to implement this and send you another email with more details.
>>
>> Jan
>>
>>
>> On Wed, 20 Feb 2008, Alberto Montresor wrote:
>>
>>> Now that I think about it a little more, I think you are right; if you
>>> end up in using and modifying my code, let me know that I will post an
>>> update. If not, I will work on it eventually...
>>> Thanks again,
>>>
>>>  Alberto
>>>
>>> Jan Sacha wrote, On 02/20/2008 12:58 PM:
>>>>
>>>> Hi Alberto,
>>>>
>>>> Thanks for a quick response. I was thinking about your proposed
>>>> solution, but I believe there's still a problem. That is, super-peers
>>>> only gossip with _underloaded_ super-peers. In my scenario, when peer B
>>>> (highest capacity peer) becomes fully loaded, it would stop
>>>> participating in the UNDERLOADED set and no other peer would swap with A
>>>> (second highest capacity peer).
>>>>
>>>> One solution would be to change the way super-peers gossip with each
>>>> other in the SUPERPEERS set - lower capacity super-peers could swap with
>>>> higher capacity clients. But in this case the convergence speed would
>>>> not be so good as in the original paper (probably).
>>>>
>>>> Regards,
>>>> Jan
>>>>
>>>>
>>>> On Mon, 18 Feb 2008, Alberto Montresor wrote:
>>>>
>>>>> Hi Jan,
>>>>>  of course I remember you. Thanks for testing my code.
>>>>>
>>>>> In the text, your scenario should be avoided by this:
>>>>>
>>>>> "Otherwise, a last check is performed. If the local node has a client
>>>>> whose capacity is larger than the capacity of the remote one, the
>>>>> client
>>>>> and the remote node exchange their roles, by transferring the clients
>>>>> from the latter t?o the former."
>>>>>
>>>>> It should be implemented in the doClient code in the RandomSpp.java
>>>>> class.
>>>>>
>>>>> Let me know if this solves your problem, or I have made an error.
>>>>>
>>>>>  Alberto
>>>>>
>>>>> Jan Sacha wrote, On 02/18/2008 11:57 AM:
>>>>>>
>>>>>> Hi Alberto,
>>>>>>
>>>>>> You might remember me from some conferences, like the last P2P
>>>>>> conference in Galway. I'm doing some experiments for my thesis and I
>>>>>> chose your super-peer election algorithm, SG1, for a comparison
>>>>>> study. I
>>>>>> found something that might be a bug. You may already know about it,
>>>>>> or I
>>>>>> may be completely wrong, but this is what I though.
>>>>>>
>>>>>> I was wondering about the following scenario in SG1. The 2nd highest
>>>>>> capacity peer in the system, A, connects and becomes client of the
>>>>>> highest capacity peer B. Other nodes connect to B, and B becomes fully
>>>>>> utilised. The configuration becomes stable - B is a super-peer,
>>>>>> while A
>>>>>> is not. But in the target topology, quite likely, both A and B
>>>>>> should be
>>>>>> super-peers, because they are the highest capacity peers in the
>>>>>> system.
>>>>>>
>>>>>> I was wondering, how can the system converge to the target topology
>>>>>> then? I downloaded the code with SG1 and I think I found a bug in the
>>>>>> function that checks if the topology is optimal. Basically, it does
>>>>>> not
>>>>>> detect situations as the one described above. The code is in the
>>>>>> SuperpeerObserver class, analyze() method, lines 130-160.
>>>>>>
>>>>>> What do you think? Am I completely wrong?
>>>>>>
>>>>>> Thanks,
>>>>>> Jan
>>>>>>
