One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity.

For example, PBFT message complexity is O(n^2) that means that it is only scalable to tens of nodes. Thus, classical BFT (Byzantine Fault Tolerant) consensus mechanisms are not scalable to the large networks.

Nevertheless, I am looking for the most scalable BFT consensus  among all. 

In other words, is there a distributed BFT consensus with less than O(n^2) message complexity?

P.S. I brought up this question before in scicomp.stackexchange.com, but they suggested me to bring up it here. (https://scicomp.stackexchange.com/q/36087/37225)

  • $\begingroup$ May I suggest to begin studying modern algorithms such as Lamport's Paxos. A reverse reference search from the original paper should be fruitful. $\endgroup$
    – Kai
    Feb 23, 2023 at 14:01
  • $\begingroup$ @Kai , Yes, Paxos's message complexity is O(n) in a normal operation and O(n^2) if the leader fails, but it is not Byzantine fault tolerant, it's only crash tolerant. $\endgroup$
    – Questioner
    Feb 23, 2023 at 23:05
  • $\begingroup$ That's why I recommended the reverse reference search. It'd reveal e.g. Byzantizing Paxos by Refinement, L. Lamport, 2010. $\endgroup$
    – Kai
    Feb 25, 2023 at 1:35

1 Answer 1


You can turn a lot of consensus algorithms that utilize a "leader" into one that takes only O(n) message complexity in the optimistic case, by sending every message in that iteration to the leader, who then broadcasts your message to everyone. (PBFT should fall into this category, except for the view change). Assuming threshold signatures, we can further get O(n) bit complexity. (See Hotstuff, Jolteon, Tendermint).

IIRC in the pessimistic case, Hotstuff still needs a quadratic pacemaker, so the message complexity is still O(n^2), but one could argue (as they do) that they achieve a O(n) ``view change''.

I would also look at the Algorand style of protocol, which achieves $O(n\lambda)$ communication, where $\lambda$ is a choice of security parameter. (It will end up being about $2500$ servers each doing a multicast every round, with current concrete notions of security).

  • $\begingroup$ If you could suggest some references or articles, it'll be more clear of course. $\endgroup$
    – Questioner
    Jun 3, 2021 at 18:42
  • $\begingroup$ The transformation I described in my answer is pretty folklore and can be applied to essentially every modern consensus protocol. If you look up "linear Hotstuff", they actually wrote it down, and that should take O(n) communication, but you lose adaptive security (i.e. if the adversary can corrupt parties during the execution, it can corrupt the leader, and break the protocol). For the most scalable practical and implemented BFT protocol out there, take a look at algorand. It takes O(nlogn) communication complexity. $\endgroup$
    – Vervious
    Jun 4, 2021 at 15:10
  • $\begingroup$ The more esoteric stuff (i.e balanced BFT) you can maybe look at ui.adsabs.harvard.edu/abs/2020arXiv200202516B/abstract as a starting point, and the related work section. $\endgroup$
    – Vervious
    Jun 4, 2021 at 15:11
  • $\begingroup$ I had commented earlier (and couldn't edit), somewhat unfairly, that this answer addresses neither the "B" nor the "FT" in BFT. Apologies, that's incorrect. I took issue with the recommendation to degrade BFT to a one-round relay service. @Vervious's pointers given in the comments are helpful. $\endgroup$
    – Kai
    Feb 25, 2023 at 8:47
  • $\begingroup$ I updated my answer a bit also, it is maybe more thorough now. $\endgroup$
    – Vervious
    Feb 26, 2023 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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