Methods for confirming on both sides that a signal was received in one direction

Question

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?

Answer 1

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.

Answer 2

Mmm! The usual way mimics the way we exchange information ourselves. "Here is a message to which I will need a response. The message is "lock the doors when you get my OK." One good way for the car to respond would be to send back the same message but with an ACK1 code attached. It is waiting now for the remote to repeat the command perhaps with a slightly different ack2 code. For something like remote door closing flashing the car lights is a good way in practice of indicating that the message has been actioned.

However I think you have in mind something much more critical than car door locking & unlocking in mind. How about "landing gear locked down" on an aircraft?

These systems are called open & closed loop. An open loop just carries out the action. There are many ways in which a message can be checked for its authenticity. The addition of check characters at the end is once such method. Cyclic Check Character (CCC) or Block Check Character (BCC) are ways of counting say, the number of "ones" in a digital message. A bit like counting the numbers of "A's" in a text would give you a better check on integrity.

At the end of the day if of vital importance the message can be sent twice or more times and compared to make sure it is faithfully received. {faithfully received - faithfully received}! It will not be actioned until a previously agreed number of similar messages are exchanged.

I hope this opens up the possibilities of how it is possible to proceed with pretty near bombproof security and authenticity and answers your query sufficiently.

This in no way considers the question of interception or rogue generation of commands. That is more within the sphere of cyphers & codes - a rather different ballgame.

Answer 3

In computer networking, the requesting side usually resends the request until it gets an ACK. If the ACK is lost, then a duplicate request will be received.

Example exchange:

Remote: "Lock the door."
Car: (locks door)
Car: "ACK" (message lost in transmission)
Remote: "Lock the door."
Car: (notes door is already locked and does nothing)
Car: "ACK" (message lost in transmission)
Remote: "Lock the door."
Car: (notes door is already locked and does nothing)
Car: "ACK" (message received successfully)

Note that to use this method, the protocol must be designed so that duplicate requests do not matter. So the remote can't tell the car "change door status". Instead, the remote has to first ask whether the door is currently locked (with retries) and then set it to the opposite status (with retries).

After a certain number of failed retries the remote has to give up (maybe the car is not in range). In that case it doesn't know whether the car is out of range, or whether the car failed to transmit the response. This can be avoided by sending a no-op message first (which causes the car to send an ACK, but not do anything) to see whether the car is in range.

As noted by other answerers, there is always a nonzero possibility that the remote will fail to receive the ACKs from the car when the operation was successful. This is unavoidable. At best, the probability can be reduced so that it's unlikely to occur in normal scenarios.