I have just gone through Feldman-Micali, Dolev-Strong, KatzKoo (basically, most of the literature behind Byzantine agreement), however all of their protocols take a really incredible amount of rounds.

Just now, I read about PBFT from CastroLiskov and I realize that they are making a byzantine consensus that just happens in three phases.

  • Can someone explain why these two line of work diverge so much?
  • Are they tackling the same problem of agreement?
  • Could we not use the construction from CastroLiskov to make byzantine agreement?
  • 1
    $\begingroup$ Could you please link to the mentioned papers or at least to the paper / technique in question? $\endgroup$ – SEJPM Apr 12 '17 at 11:10
  • $\begingroup$ @SEJPM I think it's Practical Byzantine Fault Tolerance by Castro and Liskov from 1999 $\endgroup$ – tylo Apr 12 '17 at 11:15

I guess you have read the wikipedia page completely, and seen that all of those works mentioned are referenced. And then you have to consider two things from today's point of view:

  • The sequence of those publications.
  • The assumpions made. e.g. Practical Byzantine Fault Tolerance (PBFT) by Castro and Liskov assume $n>3t$. But I don't know which other protocols you mean, or what kind of assumpions they are based on. I would speculate they try to get high confidentiality (but no certainty) but allow a higher number of corrupted machines.

So while adressing the same problem, using different assumptions can lead to different solutions. And of course, later works should be aware of the prior ones - which is impossible the other way around.

I don't understand your last question. Yes, that's exactly what it does - under certain conditions. But what are you getting at? A general solution for any number of faulty machines? That's impossible - because what would be the correct result if all are faulty? If all but one are faulty how do we know what is faulty and actually correct? In that case we are wandering into the area of the halting problm as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.