≡ Menu

communications problem

I recall we had this problem in one of my electrical engineering courses, studying packet communications between computers. Unfortunately, I’ve forgotten the answer and it’s driven me nuts for years. If anyone knows, email daddy.

You have 2 armies, on opposite hilltops. They are allied against an enemy army in the valley between them. Sometimes the 2 armies send runners to send messages to each other. The runners sometimes get killed–say, 1% of the time. So you can’t be 100% sure a message makes it to the recipient.

Now say they 2 armies can defeat the enemy if they attack togehter, but if attacking alone, eihter one will lose. Army 1 wants to attack at sunrise. So they send a runner to 2. But the dilemma is, Army 1 needs to get a message back knowing Army 2 got the message and will attack too. Army 1 can’t assume 2 gets the message since the runner might be killed.

Now Army 2, even if it gets the first message, and wants to attack, wants to be sure 1 got the reply, so 2 does not attack alone.

The question was: is it possible to arrange a communication scheme, given a less than 100% chance of message success, so that they can both attack?

It seems to me NO, but I wonder. It seems to me that to attack you have to have 100% certainty your message made it, and so does the other guy. This must be impossible. You can have an arbitrarily high confidence if you do enough handshaking, I suppose, but you can never be sure. Anyone know if Daddy is right?

Share
{ 0 comments… add one }

Leave a Reply

Next post:

Previous post:

Bad Behavior has blocked 4114 access attempts in the last 7 days.

© 2012-2019 StephanKinsella.com CC0 To the extent possible under law, Stephan Kinsella has waived all copyright and related or neighboring rights to material on this Site, unless indicated otherwise. In the event the CC0 license is unenforceable a  Creative Commons License Creative Commons Attribution 3.0 License is hereby granted.

-- Copyright notice by Blog Copyright

%d bloggers like this: