Nicaea: A Byzantine Fault Tolerant Consensus Under Unpredictable Message Delivery Failures for Parallel and Distributed Computing

Byzantine fault-tolerant (BFT) consensus is a critical problem in parallel and distributed computing systems, particularly with potential adversaries. Most prior work on BFT consensus assumes reliable message delivery and tolerates arbitrary failures of up to <inline-formula><tex-math notation="LaTeX">$\frac{n}{3}$</tex-math></inline-formula> nodes out of <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> total nodes. However, many systems face unpredictable message delivery failures. This paper investigates the impact of unpredictable message delivery failures on the BFT consensus problem. We propose Nicaea, a novel protocol enabling consensus among loyal nodes when the number of Byzantine nodes is below a new threshold, given by: <inline-formula><tex-math notation="LaTeX">$\frac{\left(2-\rho\right)\left(1-\rho\right)^{2n-2}-1}{\left(2-\rho\right) \left(1-\rho\right)^{2n-2}+1}n$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$\rho$</tex-math></inline-formula> denotes the message failure rate. Theoretical proofs and experimental results validate Nicaea's Byzantine resilience. Our findings reveal a fundamental trade-off: as message delivery instability increases, a system's tolerance to Byzantine failures decreases. The well-known <inline-formula><tex-math notation="LaTeX">$\frac{n}{3}$</tex-math></inline-formula> threshold under reliable message delivery is a special case of our generalized threshold when <inline-formula><tex-math notation="LaTeX">$\rho=0$</tex-math></inline-formula>. To the best of our knowledge, this work presents the first quantitative characterization of unpredictable message delivery failures’ impact on Byzantine fault tolerance in parallel and distributed computing.