3 ms·

1. Alice sends “Bob attack on Friday. I will send this continously until I receive a message” 2. Bob sends “Got it. Do not send another message.” 3. Alice rec

by k2xl 4y ago

1. Alice sends “Bob attack on Friday. I will send this continously until I receive a message” 2. Bob sends “Got it. Do not send another message.” 3. Alice receives it and then stops sending messages. 4. Bob now knows Alice received the message as she has stopped sending messages. Ends. What am I missing?

Twisol 4y ago
In 4, Bob only knows that he has stopped receiving messages. Alice may still be sending messages, but a mysterious fissure has appeared between their camps, and their couriers keep falling in.
OrkWard 4y ago
Bob just can't receive message from Alice anymore. But he don't know whether it's caused by acknowledgement or all messagers from Alice was caught. Whatever it was a low probability depending on how hard can be for a messager to cross the city, but never centainty.
rocqua 4y ago
When does Bob decide to re-send "Got it. Do not send another message". I think Bob needs to keep sending his message until he is sure Alice received one of them. So step 2 becomes: Bob sends “Got it. Do not send another message.” continuously and step 4 becomes: Bob now knows Alice received the message as she has stopped sending messages, so Bob stops sending messages. Note that in this case, Alice does not need to wait for silence from Bob. She can consider her silence a sort of "unbreakable acknowledge", so she doesn't need an acknowledge. This is an interesting approach. It works to solve the problem with 99.9% certainty if one considers message failure an identically distributed independent event. (I.e. every message is a dice roll with chance p for failure) and the message rate can be considered roughly constant. Then after n 'message intervals' without receiving a message there is chance p^n that Alice received Bobs acknowledge. Picking n large enough gives arbitrary certainty. I wonder if this has a better message complexity than sending N acknowledges. I imagine it might have to do with latency. Certainly Bobs 'repeat rate' relative to Alice's 'repeat rate' also factors in. However, the big assumption here is that message failure is an independent event. As pointed out by others, if at some point the connection is completely severed, this approach will fail. Because in that case silence of the other side could be the result of communication failure.

by k2xl 4y ago

Twisol 4y ago

In 4, Bob only knows that he has stopped receiving messages. Alice may still be sending messages, but a mysterious fissure has appeared between their camps, and their couriers keep falling in.

OrkWard 4y ago

Bob just can't receive message from Alice anymore. But he don't know whether it's caused by acknowledgement or all messagers from Alice was caught. Whatever it was a low probability depending on how hard can be for a messager to cross the city, but never centainty.

rocqua 4y ago

When does Bob decide to re-send "Got it. Do not send another message". I think Bob needs to keep sending his message until he is sure Alice received one of them. So step 2 becomes: Bob sends “Got it. Do not send another message.” continuously and step 4 becomes: Bob now knows Alice received the message as she has stopped sending messages, so Bob stops sending messages. Note that in this case, Alice does not need to wait for silence from Bob. She can consider her silence a sort of "unbreakable acknowledge", so she doesn't need an acknowledge. This is an interesting approach. It works to solve the problem with 99.9% certainty if one considers message failure an identically distributed independent event. (I.e. every message is a dice roll with chance p for failure) and the message rate can be considered roughly constant. Then after n 'message intervals' without receiving a message there is chance p^n that Alice received Bobs acknowledge. Picking n large enough gives arbitrary certainty. I wonder if this has a better message complexity than sending N acknowledges. I imagine it might have to do with latency. Certainly Bobs 'repeat rate' relative to Alice's 'repeat rate' also factors in. However, the big assumption here is that message failure is an independent event. As pointed out by others, if at some point the connection is completely severed, this approach will fail. Because in that case silence of the other side could be the result of communication failure.