Two Generals' Problem | Hacker News Reader

Two Generals' Problem

en.wikipedia.org

97 pointsaburan2828 comments

Given HN's recent obsession with Bitcoins, it's probably worth noting that the "double-spend" problem is a variation on the Two Generals problem (or, more accurately, the Byzantine Generals problem). Regardless of your views on Bitcoin as a currency replacement, it's hard to deny that the block chain is a rather clever solution to this problem.

Of course, it's not exactly a breakthrough solution. As noted in the article, it is possible to increase the confidence of coordination at the expense of speed and resources. In this case, requiring the "commander" to commit limited resources (computational power to generate hashes) and a majority of the "lieutenants" to agree on one commander's solution, then chaining multiple decision events together, the result is actually fairly robust.

Obviously, for most use cases something like the block chain is completely impractical. You wouldn't want to have to wait an hour for each commit to your web app's database. That said, it will be interesting to see if future variations on this theme make their way into other applications.

You may be interested in looking into some of the research that has been done in other areas on Byzantine consensus. Depending on the system model, solutions that are much more efficient than the Bitcoin block chain (but have other tradeoffs) exist. For example, check out Castro and Liskov (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.127....). Personally, I think some people in the Bitcoin community have been a bit dishonest in claiming that bitcoin's protocol solves a consensus problem which wasn't solvable before.

Lower bounds on Byzantine consensus in any practical system model exist which makes it very attractive, for efficiency reasons, to solve a subset of that problem for things like database replication in trusted systems. Lower bounds for consensus vary from f+1 (for f faults) to 2f+1 to 3f+1 depending on what kinds of faults you admit. Still it's very interesting to think about.

"Whenever I go the a conference and I discover that there will be a presentation about Byzantine fault tolerance, I always feel an immediate, unshakeable sadness, kind of like when you realize that bad things happen to good people, or that Keanu Reeves will almost certainly make more money than you over arbitrary time scales."

-- James Mickens

http://research.microsoft.com/en-us/people/mickens/thesaddes...

Holy crap, that guy's an amazingly witty writer.

He uses standard techniques. Just compare to Dave Barry.

Best HN comment ever.

Great article.

For a little bit more, here [1] is a link to the lecture notes from the Distributed Systems course I took that covers this. Also covers the related Byzantine Generals problem. If you find this interesting I'd recommend taking a look through the rest of the course's lecture notes too. They're very descriptive and written really well.

[1] http://www.andrew.cmu.edu/course/15-440-f13/index/lecture_in...

This reminds me a bit of the "A Biological Solution to a Fundamental Distributed Computing Problem" paper that I believe came up here, especially the probabilistic approach with (implicit, synchronized) clocks in the last paragraph of the wiki page.

I made a little simulation of the former algorithm here

http://jberryman.github.io/fly-mis/

The solution: a catapult.

Fire the message over Army B with a catapult.

Right! Forget the slow, unreliable upload. Overnight a USB drive.

I worked at one place where it was easier to take the server from a remote location, transport it to a central hub, upgrade and install new software, and transport it back then to download the updates and remote install. This was a while back, but bandwidth in some places was horrible and dropped often.

Smoke signal would work wonders.

Lovely. Armies A1 and A2 destroying each other with confirmation messages.

'Some people, when confronted with a problem, think "I know, I'll use a catapult."...'

Attacking Generals and Buridan's Ass, or How did the chicken cross the road? http://muratbuffalo.blogspot.com/2013/04/attacking-generals-...

Wait... A 2013 blog entry about the Two Generals' problem which repeats several times that there's an "impossibility result" in an unreliable distributed network for that problem and not a single mention of Bitcoin.

I thought that Bitcoin's major technical feat was precisely that it showed that you could solve the Byzantine Generals' problem (which is a generalization of the Two Generals' problem).

So which is it? Impossible result or not? Or does the article talk about something else (but then a mention of Bitcoin, what Bitcoin solves and why it doesn't apply to what's described in the blog entry would have helped)? I'm confused now...

As a sidenote I'd say that writing about either the two generals' or the Byzantine Generals' problem in 2013 without mentioning Bitcoin even once is a bit weird.

> I thought that Bitcoin's major technical feat was precisely that it showed that you could solve the Byzantine Generals' problem (which is a generalization of the Two Generals' problem).

This sort of thing is extremely sensitive to the definition of the problem you are solving, and the system model you are solving it under. Impossibility results like Lynch and Gilbert's CAP result and the FLP result prove that certain problems are impossible to deterministically solve in finite time in some kinds of system models. Change those system models only slightly, and you get things like Ben-Or's algorithm (http://dl.acm.org/citation.cfm?id=806707) which depend on a random oracle that is not available in FLP's system model.

So it is with Bitcoin. Not only is the definition of consensus different (uniform consensus vs. probability-one convergence on consensus among non-failed processes), but the system model is different. As I understand the bitcoin protocol, a random Oracle is needed, and liveness is only guaranteed against some forms of byzantine behavior (but I may be wrong about that, I'm not an expert in this area).

> As a sidenote I'd say that writing about either the two generals' or the Byzantine Generals' problem in 2013 without mentioning Bitcoin even once is a bit weird.

I don't think Bitcoin was a substantial advance in distributed systems theory. It's got a lot of interesting properties for sure, but I'm not aware that there's anything theoretically new there.

It isn't solved. Just "workable".

If 100% of messages are lost, the battle is lost. 100% only has to be "for a meaningful amount of time".

Think of it like Raid Arrays. They "solve" hard disk failure. But only up to a certain level of loss. You can lose 1 drive, but not 10.

This formulation is also with "undetectable arbitrary message loss". If you can detect at the sender when a sent message is lost or succeeded (for example like collision detection in Ethernet bus, or wireless collision detection), the result doesn't apply. Because then the parties would know which round was successful and they can stop.

So smoke signals would work :-) Assuming bidirectional visibility (no clouds etc.)

I don't understand this problem, I don't think. If it was so imperative that your generals attack at precisely the right time, why would you not have coordinated this attack long before the assault? Is that not a solution?

It is meant for things like a network, but to make the analogy work I will provide a scenario.

The imaginary Red Army, and the Imaginary Blue army were both being attacked by the Green army. After waging a long war the Red army and Blue army arrive at the capital of the Greens. The Red and Blue Armies have never met, and are only united by their hatred of the Greens.

The only way for the Greens to be defeated is for the Reds and Blues to attack on two fronts simultaneously.

No. I get point of the problem, but what I don't get is how it would be considered unsolvable. I mean it seems like it should be solvable through protocol, which this link doesn't seem to explain how it can't.

In a network, "be in the same place" is not a real solution. Try laying out a protocol in terms of messages passed, and you'll see the issue.

My attempt at an explanation: At any given point, one general has less information than the other. When I send a message I learn that I've sent a message, but I don't know that they've received the message. When I receive a message, I learn both. If there is any specific threshold of knowledge required to go, one general must pass it first.

That is not a solution because "attacking" is not the stated problem. The problem is how to exchange message(s) and acknowledgement.

This brings back memories of learning about TCP

could solutions to this be used for settlement purposes I.e bank transfers etc.

Reply on news.ycombinator.com