> 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

> 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 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.