Say there are two devices (A & B) that talk to each other (full duplex). For the sake of this example, let's say the medium is RF (wireless).
If device A sends a message to device B, what methods/strategies are there for both devices to confirm that B received the message, and for both devices to be sure that the other device knows it?
This is perhaps best explained through a real-world example:
Say you have a full duplex RF key fob/remote for your car that controls the locks. The remote has an LCD screen.
If you command the locks to close, the remote will send a signal to the car. If the car receives the signal properly, it can lock the doors immediately and then send an acknowledgment (ACK) back to the remote to say "the doors are locked" and the remote can show this on its screen. However, the remote may or may not receive the car's ACK.
If the remote does not receive the car's ACK, the remote and user do not know if the doors are locked. At this point, the user can either attempt the process again, or give up and walk to the car, either of which are not desirable because it was unneeded. It may also cause further issues, such as the user expecting the car to be unlocked, and thus not bringing their keys to get an item out of the trunk. Thus there is desire for both remote and car to be "on the same page".
Now let's consider the same sequence, except that the remote received the ACK. The remote now knows that the car received the message. It can display to the user that the doors are locked… But the car doesn't know that the remote knows. From the car's point of view, it's possible that the ACK was not received, thus the doors should not be locked yet or else we run into the issues mentioned in the last paragraph. Thus the car can wait for the the remote to send an ACK of its own to the car. If that is received, the car knows that the remote knows that the car knows to lock the doors… But does the remote know that? No!
Seeing a pattern here? Both devices continue to pass ACKs back and forth. Neither can quit and say "I know 100% that the other device knows I'm going to perform my action".
Is there any way for both remote and car to be sure that the doors are locked and the remote shows it?
If that's not possible, what strategies other than simple brute force (car repeatedly sending ACKs) are there for being pretty sure that the doors are locked and the remote shows it as such?
Best Answer
As mentioned in the comments, this is known as the Two Generals' Problem, and is has been well studied. It has been proven that there is no perfect algorithm which will always lead to both parties agreeing and knowing the other has too. But if you are willing to send a lot of messages, you can get arbitrarily close.
The "best" strategy will be determined by the specifics of the problem. It will depend on the cost of sending the messages (which might be different in both directions), the cost of failure, the likelihood of messages going missing, and whether or not missing messages are correlated.