News for hackers. Stuff that matters.
Re:The Two Generals Problem by k2xl on Monday May 09, 2022 @11:14PM (#31323017)
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?

Re:The Two Generals Problem by rocqua on Tuesday May 10, 2022 @05:27AM (#31325102)
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.

Re:The Two Generals Problem by Twisol on Monday May 09, 2022 @11:20PM (#31323051)
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.
Re:The Two Generals Problem by OrkWard on Monday May 09, 2022 @11:51PM (#31323249)
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.