4 ms·

It's not really a solution to the Two Generals Problem. The Two Generals Problem, as stated, implies that a failure to reach consensus about a future decision

It's not really a solution to the Two Generals Problem. The Two Generals Problem, as stated, implies that a failure to reach consensus about a future decision would be catastrophic and ought to be considered as a failure of the protocol. By contrast, in blockchains a failure to reach consensus about a future decision is not catastrophic, instead we have a very strong guarantee that we do reach consensus for the whole of the past up to some reasonable time close enough to the present. This is rather "eventual consistency". I really dislike how many academic and non-academic papers lump all of these difference types of "byzantine generals problem" all into the same phrase. Another aspect is protecting against attacks. Some papers "defend" against attacks by modelling random errors that they also call "byzantine", this is bullshit and sort of like saying Error Correction Codes are equivalent to cryptography.

dsacco 9y ago
> It's not really a solution to the Two Generals Problem. The Two Generals Problem, as stated, implies that a failure to reach consensus about a future decision would be catastrophic and ought to be considered as a failure of the protocol. Strictly speaking, sure. But I still agree with the parent's point. Bitcoin was the original innovation that inspired later research in proof-of-stake based blockchains. PoS consensus systems do allow for blockchains to be used to resolve consensus for future decisions in the context of deterministic state machines (ironically, somewhat at the expense of strong eventual consistency guarantees provided by proof of work consensus). > I really dislike how many academic and non-academic papers lump all of these difference types of "byzantine generals problem" all into the same phrase. Another aspect is protecting against attacks. Some papers "defend" against attacks by modelling random errors that they also call "byzantine", this is bullshit and sort of like saying Error Correction Codes are equivalent to cryptography. Interesting - do you mind providing an exemplary paper or two? I'd like to read them.
- infinity0 9y ago
  > PoS consensus systems do allow for blockchains to be used to resolve consensus for future decisions I suppose you mean that someone (out of a group G) can commit an instruction saying "the future decision is Y" into the blockchain, and at some time later everyone will be convinced this is the future decision. This is not related to PoS, this will work for pretty much any system that supports smart contracts. In this situation the decision is not executed in a shared manner - even if one of G gets disconnected from the network, the decision still gets executed by the blockchain. So it is still different from the Two Generals Problem (as stated), where everyone in the group G must participate in executing the decision. So blockchains still don't solve the Two General Problem. Nor should this be a goal. I think the Two Generals Problem is stupidly strong and really unnecessary in the vast majority of real computing scenarios, including the blockchain. > Interesting - do you mind providing an exemplary paper or two? I'd like to read them. It's basically all of them, and I don't think many are worth reading so I don't remember the titles. Search for papers that try to solve the Sybil or Eclipse attacks. (Quite a lot of them rely on trusted authorities, these are not relevant here, I mean the other ones.)
  - dsacco 9y ago
    > I suppose you mean that someone (out of a group G) can commit an instruction saying "the future decision is Y" into the blockchain, and at some time later everyone will be convinced this is the future decision. This is not related to PoS, this will work for pretty much any system that supports smart contracts. No, I specifically mean a voting protocol in which the "round" will not proceed ("the generals will not attack") unless all voters v in the voting set V come to consensus about the values t in the set of transactions T at the next block height ("the city to be attacked", "the time to attack", etc). Then the voting protocol asserts a proof of stake, such that Byzantine voters are penalized and honest/correct voters are rewarded. Then future decision resolution is provably guaranteed, so long as all activity remains deterministic, the cryptography is secure, all voters in the set V are online and active, and proof of stake is a plausible economic incentive. The caveat here is - pretty obviously - that it's possible for the consensus system to enter an infinite loop if it fails to reach consensus (just like the original problem). So no, it's not perfect, but it is modeling the Two Generals Problem and compartmentalizing it somewhat, though it can't completely resolve it. Otherwise, I agree with you - the classical Two Generals problem is an inordinate fault-tolerance ideal.
    - infinity0 9y ago
      > [..] Then the voting protocol asserts a proof of stake, such that Byzantine voters are penalized and honest/correct voters are rewarded. How do you decide which one is a "Byzantine" voter? A minority is not necessarily dishonest. If you penalise a minority, at each step at most ceil(n/2-1) of the group will lose their stake, even if they were honest. That sounds overly-harsh.
      - schoen 9y ago
        I believe this is a terminological mistake. In the original formulation, all of the generals are "Byzantine" because they all work for the Byzantine Empire. In the original paper by Lamport, Shostak, and Pease, the problem is described this way: "We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement." A common way to describe the participants in such a scenario is simply "honest" and "dishonest". The term "Byzantine" has become used in distributed systems research to refer to situations in which we can't be sure of participants' honesty and intentions. However, it doesn't correctly refer only to the dishonest participants.
- peterwwillis 9y ago
  The Two Generals Problem is a specific problem, separate from the Byzantine Generals Problem, which is an extension of the Dining Philosophers Problem. There are other papers which advertise "Byzantine" solutions or problems, due to the references to qualities of similar problems. They are all concurrency problems, but they all have different specific criteria and solutions. You can find the related papers under each problem on Wikipedia (they are officially behind paywalls, but you can find the PDFs indexed on search engines)
  - infinity0 9y ago
    I understand, however my whole point is that these different other qualities change the shape of the problem (and necessary solutions or impossibilities) completely, often in ways that make it unrealistic for the real-world problems that the paper appeals to in its abstract as motivation. The word "byzantine" is so over-used as well as abused in this field of research, that for a random paper that mentions that word I can't really tell what actual problem it's solving unless I read through it fully in detail. I suggest that a wider more systematic set of terms would help to avoid this problem. e.g. instead of saying "secure" say "unforgeable against a chosen-message adversary" etc. Lamport's original paper does seem to treat adversaries appropriately, but I've seen many worse papers from recently failing to consider what happens if a malicious peer specifically tries to exploit your "defence" mechanism.
    - peterwwillis 9y ago
      > The word "byzantine" is so over-used as well as abused in this field of research, that for a random paper that mentions that word I can't really tell what actual problem it's solving unless I read through it fully in detail I wouldn't say this is a problem. It's a useful red flag that you should stop reading this paper, or at the very least question the competency of the authors. Could save hours of your life!
      - infinity0 9y ago
        It is a massive problem because it wastes a lot of people's time doing research in this area, trying to read up on previously-done work most of which is uninsightful and useless. The whole point is that I can't tell if it's a red flag simply by reading the abstract, I have to read the entire paper. The good papers also use the same vague terminology!
chrisseaton 9y ago
There are no known solutions to the Two Generals problem at all, are there? It is proven to be not solvable isn't it?
- infinity0 9y ago
  Right, it's not solvable. But as I stated in the other reply, it's also unnecessary in the vast majority of systems - either failure is not catastrophic, or you only need consensus about the past, or the decision is not executed in a shared synchronised matter, or some other property that means you don't actually need to solve the actual Two Generals Problem. I really think we need to stop citing it as a "thing", it's like the Halting Problem, stupidly strong and not necessary most of the time. Saying that something "solves" Two Generals is diverting the conversation into pointless impossibilities.

dsacco 9y ago

> It's not really a solution to the Two Generals Problem. The Two Generals Problem, as stated, implies that a failure to reach consensus about a future decision would be catastrophic and ought to be considered as a failure of the protocol. Strictly speaking, sure. But I still agree with the parent's point. Bitcoin was the original innovation that inspired later research in proof-of-stake based blockchains. PoS consensus systems do allow for blockchains to be used to resolve consensus for future decisions in the context of deterministic state machines (ironically, somewhat at the expense of strong eventual consistency guarantees provided by proof of work consensus). > I really dislike how many academic and non-academic papers lump all of these difference types of "byzantine generals problem" all into the same phrase. Another aspect is protecting against attacks. Some papers "defend" against attacks by modelling random errors that they also call "byzantine", this is bullshit and sort of like saying Error Correction Codes are equivalent to cryptography. Interesting - do you mind providing an exemplary paper or two? I'd like to read them.

infinity0 9y ago
> PoS consensus systems do allow for blockchains to be used to resolve consensus for future decisions I suppose you mean that someone (out of a group G) can commit an instruction saying "the future decision is Y" into the blockchain, and at some time later everyone will be convinced this is the future decision. This is not related to PoS, this will work for pretty much any system that supports smart contracts. In this situation the decision is not executed in a shared manner - even if one of G gets disconnected from the network, the decision still gets executed by the blockchain. So it is still different from the Two Generals Problem (as stated), where everyone in the group G must participate in executing the decision. So blockchains still don't solve the Two General Problem. Nor should this be a goal. I think the Two Generals Problem is stupidly strong and really unnecessary in the vast majority of real computing scenarios, including the blockchain. > Interesting - do you mind providing an exemplary paper or two? I'd like to read them. It's basically all of them, and I don't think many are worth reading so I don't remember the titles. Search for papers that try to solve the Sybil or Eclipse attacks. (Quite a lot of them rely on trusted authorities, these are not relevant here, I mean the other ones.)
- dsacco 9y ago
  > I suppose you mean that someone (out of a group G) can commit an instruction saying "the future decision is Y" into the blockchain, and at some time later everyone will be convinced this is the future decision. This is not related to PoS, this will work for pretty much any system that supports smart contracts. No, I specifically mean a voting protocol in which the "round" will not proceed ("the generals will not attack") unless all voters v in the voting set V come to consensus about the values t in the set of transactions T at the next block height ("the city to be attacked", "the time to attack", etc). Then the voting protocol asserts a proof of stake, such that Byzantine voters are penalized and honest/correct voters are rewarded. Then future decision resolution is provably guaranteed, so long as all activity remains deterministic, the cryptography is secure, all voters in the set V are online and active, and proof of stake is a plausible economic incentive. The caveat here is - pretty obviously - that it's possible for the consensus system to enter an infinite loop if it fails to reach consensus (just like the original problem). So no, it's not perfect, but it is modeling the Two Generals Problem and compartmentalizing it somewhat, though it can't completely resolve it. Otherwise, I agree with you - the classical Two Generals problem is an inordinate fault-tolerance ideal.
  - infinity0 9y ago
    > [..] Then the voting protocol asserts a proof of stake, such that Byzantine voters are penalized and honest/correct voters are rewarded. How do you decide which one is a "Byzantine" voter? A minority is not necessarily dishonest. If you penalise a minority, at each step at most ceil(n/2-1) of the group will lose their stake, even if they were honest. That sounds overly-harsh.
    - schoen 9y ago
      I believe this is a terminological mistake. In the original formulation, all of the generals are "Byzantine" because they all work for the Byzantine Empire. In the original paper by Lamport, Shostak, and Pease, the problem is described this way: "We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement." A common way to describe the participants in such a scenario is simply "honest" and "dishonest". The term "Byzantine" has become used in distributed systems research to refer to situations in which we can't be sure of participants' honesty and intentions. However, it doesn't correctly refer only to the dishonest participants.
peterwwillis 9y ago
The Two Generals Problem is a specific problem, separate from the Byzantine Generals Problem, which is an extension of the Dining Philosophers Problem. There are other papers which advertise "Byzantine" solutions or problems, due to the references to qualities of similar problems. They are all concurrency problems, but they all have different specific criteria and solutions. You can find the related papers under each problem on Wikipedia (they are officially behind paywalls, but you can find the PDFs indexed on search engines)
- infinity0 9y ago
  I understand, however my whole point is that these different other qualities change the shape of the problem (and necessary solutions or impossibilities) completely, often in ways that make it unrealistic for the real-world problems that the paper appeals to in its abstract as motivation. The word "byzantine" is so over-used as well as abused in this field of research, that for a random paper that mentions that word I can't really tell what actual problem it's solving unless I read through it fully in detail. I suggest that a wider more systematic set of terms would help to avoid this problem. e.g. instead of saying "secure" say "unforgeable against a chosen-message adversary" etc. Lamport's original paper does seem to treat adversaries appropriately, but I've seen many worse papers from recently failing to consider what happens if a malicious peer specifically tries to exploit your "defence" mechanism.
  - peterwwillis 9y ago
    > The word "byzantine" is so over-used as well as abused in this field of research, that for a random paper that mentions that word I can't really tell what actual problem it's solving unless I read through it fully in detail I wouldn't say this is a problem. It's a useful red flag that you should stop reading this paper, or at the very least question the competency of the authors. Could save hours of your life!
    - infinity0 9y ago
      It is a massive problem because it wastes a lot of people's time doing research in this area, trying to read up on previously-done work most of which is uninsightful and useless. The whole point is that I can't tell if it's a red flag simply by reading the abstract, I have to read the entire paper. The good papers also use the same vague terminology!

chrisseaton 9y ago

There are no known solutions to the Two Generals problem at all, are there? It is proven to be not solvable isn't it?

infinity0 9y ago
Right, it's not solvable. But as I stated in the other reply, it's also unnecessary in the vast majority of systems - either failure is not catastrophic, or you only need consensus about the past, or the decision is not executed in a shared synchronised matter, or some other property that means you don't actually need to solve the actual Two Generals Problem. I really think we need to stop citing it as a "thing", it's like the Halting Problem, stupidly strong and not necessary most of the time. Saying that something "solves" Two Generals is diverting the conversation into pointless impossibilities.