I'm studying distributed systems and I'm trying to understand how to achieve Byzantine fault tolerance. Aside from the specific algorithms (PBFT, ...), I'm particularly interested in the minimum number of nodes a system has to be composed of to be K-fault tolerant, i.e. to tolerate the Byzantine failure of K nodes.
Reading from "Distributed Systems - Principles and Paradigms" by Tanenbaum/Van Steen (4th ed., chapter 8), it firstly says that if the client is able to apply a voting mechanism and the system is flat (i.e. there is no hierarchy among nodes), the minimum number of nodes to be BFT is 2K+1, because there has to be a majority of non-faulty nodes (K+1).
Moving on, the book says that if the system has a hierarchical setting (a leader and several followers), it turns out the total minimum number of nodes is 3K+1.
Now, suppose having a system composed of three nodes which executes the same calculations in parallel and send their results to a final stage which simply returns the first of the three results.
As the three nodes are configured in a flat setup, it is needed just one functioning node to be CFT. For example, if 2 out of 3 computing nodes simply stop, the system as a whole continues to be active, because there is one healthy node doing its job correctly.
In order to achieve BFT, instead, something more sophisticated is required. I think it is necessary to use something similar to the TMR (Triple Modular Redundancy) setup.
In this way, using 3 computing nodes, we can tolerate the failure of up to 1 node. Indeed, every voter will see a majority of functioning nodes and compute the correct answer. Also, replicating the voter system, we can tolerate one of three voter to fail and still obtain the correct answer. Please, tell me if there is something wrong with that and if you have any better answers.