Homework 1 forum

Sending rumors one by one

Sending rumors one by one

Hi,

I had a question regarding the way we need to send missing rumors to a peer, especially what the "one by one" means.

Does the sender need to wait for the acknowledgement of a rumor before sending the next one and if so, if no acknowledgement comes, what is the procedure ?

Or does it simply mean sending N packets, N being the number of missing rumors, and assume that they were correctly received ?

Cheers!

Re: Sending rumors one by one

On the same idea, can we bypass this problem by only sending the first missing packet, and relying on the status reply mechanism to deal with the other missing packets ?
For example, let's say A knows of (C,5) but B only knows (C,2). When receiving status from B, A could just send back the message 2 of C, which makes B know (C,3) and trigger a status send to A as an acknowledgement. The status sent to A will trigger the send of message 3 of C, and a status in return, and so on.
Is that correct or should we implement a specific behaviour for nodes catching up ? Combined with the resend timeouts mechanisms and random rumors it seems a bit of a mess.
Re: Sending rumors one by one

Hello

The messages are sent one by one; meaning that it does not wait for the status messages.

More clearly, assume A finds that B is missing messages 3, 4, and 5. In this case A will send them one by one in a loop (and before sending the second rumor, A does not wait for a status reply).

Hope this is clear now

Re: Sending rumors one by one

Perfectly clear. Thank you!

Re: Sending rumors one by one

But if A does so, B will receive messages 3 then 4 and then 5, which will trigger the send of status of B 3 times. For the first two times, B will still lack messages (4,5 and then only 5), which will make A send 4,5, then 5.

So A will send 3,4,5 then 4,5 then 5 right ?

If we want to prevent this behavior we would need to remember for each node if we are in a synchronizing process with it, and as we can be synchronizing with several nodes at a time, it makes things really complex ?

I may be missing something obvious, but to me, the more stateless nodes are, the easier it is to ensure correctness in all cases.

Thank you for your help !

Re: Sending rumors one by one

Can  someone help me there ? :)

Re: Sending rumors one by one

I am wondering the same thing.

Re: Sending rumors one by one

Hello,

I totally agree with your point, but I still continue my previous answer; node A will send rumors without waiting for the corresponding status messages.

I agree that this would cause a significant waste of messages depending on the timings, as you have pointed out. But for this homework, we have decided to continue with our original handout explanation.

Ultimately this is a question about efficiency / performance rather than correctness. So here we are expecting only the correctness (and I accept this is not very efficient)

Hope this helps

Re: Sending rumors one by one

But just out of curiosity, what would be wrong in having the following behaviour:

When receiving a status from a peer B that lacks messages (say it lacks (A,4), (A,5) and (C,7)), send only one of the messages that the peer could accept (either (A,4) or (C,7), as B will not accept (A,5)). It will trigger B to send back a status message, which triggers the sending of another missing message, and so on until it gets all missing messages. That the way I implemented it before our discussion, and it seemed coherent with the handout phrasing : "which causes R to send the missing messages back ​ (one at a time);". The stateless part came from the fact that A and B only answer messages, they don't have to store the fact that they are in a synchronizing state. (But, as you pointed out, if we are okay we resending messages then it is also stateless)

Thanks !

Re: Sending rumors one by one

Hello,

I have implemented the logic of sending other known rumors in the way that the sender will send the next rumor after it receives the status acknowledgement packet for the former one (as mentioned before). It seems that this implementation also pass the tests, so I am wondering should I change the logic or it is also OK.

Thank you very much!
Re: Sending rumors one by one

Hello,

One at a time means that "a node does not compress multiple messages inside a single message", in the HW1 context.

What you say is logically correct and sound. My only concern is, if you deviate from my suggestion,  there is a chance that some tests will fail, because we implemented all the tests by assuming the behavior I mentioned. So I would suggest you to do in the way I proposed.

Regards