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$\frac{n}{3}$nodes out of$n$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:$\frac{\left(2-\rho\right)\left(1-\rho\right)^{2n-2}-1}{\left(2-\rho\right) \left(1-\rho\right)^{2n-2}+1}n$, where$\rho$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$\frac{n}{3}$threshold under reliable message delivery is a special case of our generalized threshold when$\rho=0$. 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.

The openness of wireless networks opens the door to Byzantine attacks on the physical channels, making the communications unreliable and resulting in more challenges in achieving consensus among mobile devices. To address this issue, this paper studies the Byzantine-fault-tolerant (BFT) consensus problem based on an unreliable Byzantine communication model. Different from the previous works requiring stable communications between the honest nodes, considering the unreliable communication makes our problem more realistic but also harder. Based on the unreliable communication model, we first implement a BFT abstract MAC (absMAC) layer with a distributed and randomized multi-channel communication algorithm. In the implemented absMAC layer, its acknowledgement and progress operations can be completed within$O\left ({{\frac {kn}{k-f}\log n}}\right)$and$O\left ({{\frac {k}{k-f}\log n}}\right)$rounds, respectively. n, f, and k are the numbers of nodes, Byzantine nodes, and channels, respectively. With the implemented absMAC layer, an efficient and elegant BFT consensus algorithm is designed, which can solve the binary consensus problem within$O\left ({{\frac {kn}{k-f}\log n}}\right) ^{^{^{^{}}}}$rounds in expectation. Even though a series of works have discussed how to achieve consensus with a specific absMAC layer provided, to the best of our knowledge, this paper is the first one that implements a BFT absMAC layer.

Wireless networks have become integral to modern communication systems, enabling the seamless exchange of information across a myriad of applications. However, the inherent characteristics of wireless channels, such as fading, interference, and openness, pose significant challenges to achieving fault-tolerant consensus within these networks. Fault-tolerant consensus, a critical aspect of distributed systems, ensures that network nodes collectively agree on a consistent value even in the presence of faulty or compromised components. This survey paper provides a comprehensive overview of fault-tolerant consensus mechanisms specifically tailored for wireless networks. We explore the diverse range of consensus protocols and techniques that have been developed to address the unique challenges of wireless environments. The paper systematically categorizes these consensus mechanisms based on their underlying principles, communication models, and fault models. It investigates how these mechanisms handle various types of faults, including communication errors, node failures, and malicious attacks. It highlights key use cases, such as sensor networks, Internet of Things applications, wireless blockchain, and vehicular networks, where fault-tolerant consensus plays a pivotal role in ensuring reliable and accurate data dissemination.

In many edge computing applications, edge devices are required to reach fault-tolerant consensus in order to provide collaborative services in outdoor environments. In this paper, we study a comprehensive$(a,b)$-majority consensus problem based on a novel failure model, which takes$a$distinct opinions as inputs and outputs a$b$-majority opinion as the final agreement. This problem formulation is drastically different from traditional ones, which usually require a majority consensus from the binary opinions of multiple supporters. It is more practical and flexible as it can accommodate more than 2 input opinions and output one that satisfies the application requirement defined by parameter$b$. We also consider physical layer in our failure model while previous models mainly focus on faults occurred in protocol layer and data layer. Based on this more realistic failure model and a more practical consensus problem definition, we present a distributed protocol for$n$edge devices to reach an$(a,b)$-majority consensus within$\Theta (n)$time steps with high probability. Empirical results from our simulation studies validate the fault tolerance property and efficiency of our work in achieving the$(a,b)$-majority consensus.