Towards Hierarchical Byzantine Distributed Replication - Stein, Gabriela; Rodrigues, Luiz Antonio; Duarte Jr., Elias P. (Anais do Latin-American Symposium on Dependable Computing (LADC), 2025)
State Machine Replication has been widely employed to implement fault- and intrusion-tolerant distributed applications. The seminal PBFT (Practical Byzantine Fault Tolerance) algorithm ensures replica consistency even in the presence of Byzantine faults. However, PBFT is computationally and communication-intensive, and its performance degrades as the number of replicas increases. In this work, we take the first steps toward developing a hierarchical version of the PBFT algorithm that preserves its Byzantine fault tolerance while improving scalability, such that the cost of executing the algorithm grows more moderately with the number of replicas. Our proposal is based on the VCube, a virtual topology that is scalable by definition. We present preliminary results that suggest how this hierarchical version can enhance the original algorithm, most notably by reducing the number of messages exchanged as the system size grows. While promising, further work is required to fully specify and comprehensively evaluate the hierarchical PBFT algorithm.