Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I am trying to figure an agreement protocol on an unreliable channel. Basically two parties (A and B) have to agree to do something, so it's the two generals' problem.

Since there is no bullet-proof solution, I am trying to do this.

  • A continuously sends a message with sequence 1
  • When B receives seq 1 it continuously replies with sequence 2
  • At this point A receives seq 2 so it starts sending seq 3
  • ...

My question. When can the two parties conclude that they can take the action ? Obviously I can't set a condition: "do it after receiving 10 messages" since the last sender won't have any certainty that message 10 arrived - back to square one.

How about another idea:

  • Keep communicating like this for a predefined amount of time. At the end of that period both parties have an idea about the reliability of the channel. Would that be acceptable ?

I initially posted this in StackOverflow but someone suggested security might be a better place.

share|improve this question
    
You could flag your post for moderator attention to migrate it here. –  kinokijuf Dec 3 '11 at 16:40
add comment

1 Answer

Parties can never fully agree in a situation where a message may or may not be received by either party because there will always be a difference in state between the two parties.

This is also the "girlfriend's cellphone stopped working" conundrum. The best solution is to have an agreed-upon protocol that is followed so that you know the other party is probably doing one of a limited set of reasonable tasks which end in failsafe protocol. As a failsafe, one must make sure that updated failsafes don't create conditions where the previous failsafe doesn't result in a solution.

Also, you can't find an ideal solution because there is an impossibility proof saying that there is no ideal solution. See the bottom part of Two Generals' Problem Wikipedia Entry that you cited and its references. The rabbit hole goes on to include Byzantine fault tolerance and its related articles.

share|improve this answer
1  
"girlfriend's cellphone stopped working" conundrum - excellent –  Rory Alsop Dec 3 '11 at 21:30
    
Exactly right. The a further interesting part of the problem is simultaneous action and synchronized clocks. Synchronizing time over an error prone connection is extremely difficult because it usually required sequential messages to calibrate transmission time. –  this.josh Dec 4 '11 at 4:26
    
@this.josh Look at a clock and tell me what time it is. Look at two clocks and tell me what time it is. :) –  Jeff Ferland Dec 4 '11 at 5:40
    
@JeffFerland The problem of simultaneity led Einstein to relativity see Relativity of simultaneity –  this.josh Dec 4 '11 at 20:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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