The Two Generals' Problem (wikipedia) | Hacker News Reader

The Two Generals' Problem (wikipedia)

en.wikipedia.org

34 pointspaulgb19 comments

Assuming I was the general who decided when we'd attack, I'd send n messengers each with a c chance of getting captured, yielding a (1 - c^n) chance of the other general attacking at the same time. By adjusting for n, I could have whatever probability of success I wanted, though never a guarantee of success.

One can calculate the chance of losing data stored redundantly on multiple disks due to disk failure the same way, assuming that disk failures occur independently of each other, as they might for a large internet company with the data stored across multiple data centers.

Assume a solution of N messages exists. The N'th message may fail. Either N messages is not enough, or N-1 IS enough; then recurse on N-1.

Can someone explain to me why this is important. From the outset it's clear that there will always be a chance of failure and the two generals can never be certain. Why does it matter that this proof exists. Or is there something that's non-obvious here.

It's an important impossibility result like the Halting Problem. You can be led down the wrong path for hours designing protocols which attempt to solve an unsolvable problem but do so in a seemingly-almost-correct way -- until the complexity is so great that you can't understand where it goes wrong. If you didn't have these results, you might be tempted to believe your solution at that point was correct. With this result you can be sure it's wrong, recognize the pattern of unsolvability, and give up much sooner.

That makes a lot of sense. But also just goes to show how effective preliminary design work can be for making a smoother overall production curve. Still, one can easily get lost in it if they don't step back every once in awhile and realize their beating their heads against a wall.

As a side-note, the way I came across the problem was that yesterday I was trying to change the location of a date and my text messages were not always getting through (possibly due to my proximity to the G20 cell jamming). I realized that there was no way to know for sure, by text messages, whether we both committed to the change. (fortunately it worked out anyway)

This is the same value of NP-Reductions. They let you know that you should not try to solve the problem directly (because you can solve the problem without showing P=NP). Thus you know your approach should rather use techniques like approximations or high speed SAT solvers.

Although it should be pointed out that since P=NP has never been proven false, there is theoretically a chance of success. And if such a thing were possible, it's most likely that it would happen by looking at a new form of an NP-complete problem that might give some new mental handholds on the problem, rather than SAT itself.

Just saying.

Yes, but the point is with very very high probability YOU are not going to be the one to solve P vs. NP, so you shouldn't waste your time.

On a side note, I really hate when people get voted up for bringing up things that do not have realistic probabilities associated with them.

As a real world example: Synctus depends on being able to do this correctly (what it does is described at http://www.synctus.com/tech/ and the right hand column at http://www.synctus.com/tech/locking.html) - consider how the lock transfer might work in the context of the Two Generals' Problem. How exactly I do it is currently a trade secret. I've worked around the problem, but the issues surrounding this are a big part of the solution.

One thing I never understood is how you can guarantee consistency in distributed transactions given this problem. Can you really build a 2-way ACID system, or is only "eventual" consistency achievable?

Distributed transactions generally use 2 phase-commit (2PC). If message loss happens, the 2PC algorithm will block, i.e. the transaction can neither be committed nor aborted. When the network gets reliable again, the algorithm will finish. So strong consistency isn't really affected by this problem.

A special case would be if the network is broken only in one direction. In that case, the same command may be sent multiple times, but even this is not a problem, since the 2PC commands are idempotent (e.g. receiving the Commit-message multiple times won't hurt, since the receiving node knows that it has already committed the transaction).

You can guarantee consistency; but what you must then lose is the ability to make progress in all situations ('liveness').

A trivial commit protocol that is consistent but not live simply sends no messages. All updates that succeed are consistent, but no updates succeed.

An eventually consistent protocol is often correct for stronger consistency guarantees, but instead sacrifices consistency in the case of network problems rather than liveness.

(sidebar: this is really what the CAP theorem is driving at. You must choose between consistency and liveness if the network can lose messages).

There is also the Paxos algorithm:

http://en.wikipedia.org/wiki/Paxos_algorithm

(Bigtable uses 'Chubby' - google's implementation of Paxos)

Am I the only one annoyed by the recent (to me) trend of submitting Wikipedia articles to Hacker News?

I like it.

In most real situations, people arrange more than one means of communication, or more than one step, so there is not a single point of comm that is critical. When I was in the Air Force, for one critical procedure there were 44 different methods of communication. Yeah, it was the Cold War, and we had limitless money, but it was amazingly reliable.

Commius and Vercingetorix had this problem at Alesia; Caesar's troops enforced a network partition!

Fantastic link, and timely too. Thank you.

Reply on news.ycombinator.com