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.
