4

To my understanding message acknowledge deadlock problem is this:

In order to sync value X between A and B

  • A sends X to B
  • A waits for B to send acknowledgment to A so it makes sure B has latest X
  • B waits for A to send acknowledgment of acknowledgment that B received their acknowledgment.
  • and so on ...

How in real world applications we solve such problem? Do we just assume the infrastructure work and stop checking for acks?

3

In practice you solve it like this:

  1. A sends X to B.
  2. B sends an acknowledgement to A verifying that it received what was sent. (For simple protocols like TCP it sends back a checksum, more complex ones like rsync might send back an MD5 hash.)
  3. If A fails to receive the acknowledgement in a timely fashion, it sends X again. In careful world protocols (eg TCP) it usually does do with a variable delay in case the problem is network congestion.

This continues until either A receives an acknowledgment, or gives up on sending the message.

In theory you could do much more complex and reliable stuff. However research into this area is likely to induce depression. See http://research.microsoft.com/en-us/people/mickens/thesaddestmoment.pdf to get the joke.

3

In theory, this problem is not solvable for single messages, and A and B cannot know for certain that a message has been received and acknowledged. See the Two Generals' Dilemma.

If you are sending a string of messages, this changes somewhat. It is possible for both sender and receiver to know that some messages have been successfully sent and received. For instance, TCP/IP uses a strategy that includes the use of sequence numbers. Each segment contains a sequence number which is sent back in the acknowledgement. This arrangement seems to be sufficient for running a large, world-wide data network.

1

Do you really need to verify that A knows that B knows that A knows that B knows that A knows that B knows that A changed the value of X?

B needs to know that A changed the value of X. This is obvious.

A needs to know that B knows that A changed the value of X, because if B didn't get the message A needs to resend it. This one can not be avoided unless you assume the entire messaging pipe is perfect and can not loose messages.

But does B need to know that A knows that B knows that A changed the value of X? One can say that B needs to know when to stop sending ACKs, but is that really necessary? I say not! This is where the ACK chain stops!

B does not need to verify that A got the ACK. If A did not get the ACK, it will simply assume that B did not get the original message and resend it. B will receive the resent message, and will either recognize it already got it and do nothing or - if no such duplicate message recognition was implemented - will simply set the value of X again. No harm done. But in any case - B will send an ACK on the resent message.

A is the one responsible to make sure B get the new value of X. A needs to resend again and again - but B only needs to send one ACK for each message of A.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.