Hacker News Reader

Comment by Aardwolf | Hacker News Reader

I assume they must meet to discuss the algorithm beforehand.

So they could choose as algorithm: never attack

(Even if they cannot meet beforehand, the above is a strategy they can figure out on their own assuming the other is also choosing an optimal solution. Never attack is better than always attack because it doesn't depend on timing)

Then they need no communication yet know what to do and what the other does.

So problem is solvable, and something is wrong in the proof? Or alternatively I missed something in the problem statement preventing the above.

View on HN

The problem could be formulated better, basically it's about reaching consensus about what the state is right now through a lossy medium. Your suggestion is to have a default, which is a good idea, but it doesn't really solve the problem if you want both processes to react to the state (there's an opportunity for an attack now, let's attack).

What also makes it unsolvable is that you do not want to endanger more messengers than necessary, i.e you don't want to send the another messenger with a message already sent. It's impossible to always know whether or not the receiver really did get the last message.

While I have not seen this problem before, I agree that a better formulation would have been helpful in thinking about it. For example, I (and it looks like some others in the thread) got caught up on the idea that Eve should just burn all of the messages and obviously you couldn't have consensus. This is because the article says Eve has the ability to burn all of the messages. I think it would be better stated as something like, "Bob/Alice is sending a messenger past the enemy to the other and the messenger may or may not be caught by Eve and killed." Or maybe I am still misunderstanding?

Is this similar to the problem of:

Two ships on the ocean of two different civilizations (who don't have shared traffic rules, and they also cannot communicate) are by accident on a head-on collision course towards each other. To avoid collision, they each need to turn a different direction, not the same direction. So each needs to quickly decide which direction to turn.

(Actually, more recognizable: walking on a sidewalk in a different country where people appear to have a different, or no, convention about which side people should cross each other)

I had the same confusion until I read the proof, though maybe I missed something earlier too. This corresponds to the validity condition in the last section.

Both generals start with either 0 or 1, and the condition is that if both started with 0 (i.e., initially wanted to individually retreat), they should both output 0. Likewise for 1. The thing about Eve deciding which value the generals start with may also be confusing; a better way to think of it is that 'no matter what both generals start with, this validity condition holds'.

The problem statement in the article merely misses a clause to exclude this which it should have.

Reply on news.ycombinator.com