A survey of fault tolerant consensus in wireless networks

Abstract

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 (IoT) applications, wireless blockchain, and vehicular networks, where fault-tolerant consensus plays a pivotal role in ensuring reliable and accurate data dissemination.

Keywords

Consensus / Fault-tolerance / Byzantine-resilience / Wireless networks

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grant (62102232, 6212 2042), Shandong Science Fund for Excellent Young Scholars, China (2023HWYQ-007), Natural Science Foundation of Shandong Province, China (ZR2021QF064), and Key R&D Program of Shandong Province, China (2022CXGC020107).

References

[1] M.H. DeGroot, Reaching a consensus, Taylor Francis J. Am. Stat. Assoc. 69 (345) (1974) 118-121.

[2] Ke Liu, Nael Abu-Ghazaleh, Kyoung-Don Kang, Location verification and trust management for resilient geographic routing, J. Parallel Distrib. Comput. 67 (2) (2007) 215-228.

[3] D. Dolev, M.J. Fischer, R.J. Fowler, N.A. Lynch, H.R. Strong, An efficient algorithm for Byzantine agreement without authentication, Inf. Control. 52 (3) (1982) 257-274.

[4] M.J. Fischer, N.A. Lynch, A lower bound for the time to assure interactive consistency, Inf. Process. Lett. 14 (4) (1982) 183-186.

[5] L. Lamport, R.E. Shostak, M.C. Pease, The Byzantine generals problem, ACM Trans. Program. Lang. Syst. 4 (3) (1982) 382-401.

[6] L. Lamport, The part-time parliament, ACM Trans. Comput. Syst. 16 (2) (1998) 133-169.

[7] H. Howard, M. Schwarzkopf, A. Madhavapeddy, J. Crowcroft, Raft refloated: Do we have consensus? ACM SIGOPS Oper. Syst. Rev. 49 (1) (2015) 12-21.

[8] Oluwakayode Onireti, Lei Zhang, Muhammad Ali Imran, On the viable area of wireless Practical Byzantine Fault Tolerance (PBFT) blockchain networks, in: 2019 IEEE Global Communications Conference, GLOBECOM, 2019, pp. 1-6.

[9] M. Yin, D. Malkhi, M.K. Reiter, G.G. Gueta, I. Abraham, HotStuff: BFT consensus in the lens of blockchain, 2018, arXiv preprint arXiv:1803.05069.

[10] M. Xu, C. Liu, Y. Zou, F. Zhao, J. Yu, X. Cheng, Wchain: A fast fault-tolerant blockchain protocol for multihop wireless networks, IEEE Trans. Wirel. Commun. 20 (10) (2021) 6915-6926.

[11] M. Xu, F. Zhao, Y. Zou, C. Liu, X. Cheng, F. Dressler, BLOWN: A blockchain protocol for single-hop wireless networks under adversarial SINR, IEEE Trans. Mob. Comput. 22 (8) (2023) 4530-4547.

[12] Y. Zou, M. Xu, J. Yu, F. Zhao, X. Cheng, A fast consensus for permissioned wireless blockchains, IEEE Internet Things J. 10 (14) (2023) 12102-12111.

[13] Guanlin Jing, Yifei Zou, Dongxiao Yu, Chuanwen Luo, Xiuzhen Cheng, Efficient fault-tolerant consensus for collaborative services in edge computing, IEEE Trans. Comput. 72 (8) (2023) 2139-2150.

[14] C. Gao, X. He, H. Dong, H. Liu, G. Lyu, A survey on fault-tolerant consensus control of multi-agent systems: trends, methodologies and prospects, Internat. J. Systems Sci. 53 (13) (2022) 2800-2813.

[15] X. Pang, Z. Wang, D. Liu, J.C.S. Lui, Q. Wang, J. Ren, Towards personalized privacy-preserving truth discovery over crowdsourced data streams, IEEE/ACM Trans. Netw. 30 (1) (2022) 327-340.

[16] Z. Wang, K. Liu, J. Hu, J. Ren, H. Guo, W. Yuan, Attrleaks on the edge: Exploiting information leakage from privacy-preserving co-inference, Chin. J. Electron. 32 (1) (2023) 1-12.

[17] Y. Xiao, N. Zhang, W. Lou, Y.T. Hou, A survey of distributed consensus protocols for blockchain networks, IEEE Commun. Surv. Tutorials 22 (2) (2020) 1432-1465.

[18] J. Qin, Q. Ma, Y. Shi, L. Wang, Recent advances in consensus of multi-agent systems: A brief survey, IEEE Trans. Ind. Electron. 64 (6) (2017) 4972-4983.

[19] W. Ren, R.W. Beard, E.M. Atkins, A survey of consensus problems in multi-agent coordination, in: IEEE ACC, 2005, pp. 1859-1864.

[20] L. Yang, Y. Zou, M. Xu, Y. Xu, D. Yu, X. Cheng, Distributed consensus for blockchains in Internet-Of-Things networks, TUP Tsinghua Sci. Technol. 27 (5) (2022) 817-831.

[21] Q. Xu, Y. Zou, D. Yu, M. Xu, S. Shen, F. Li, Consensus in wireless blockchain system, in: Springer WASA, Vol. 12384, 2020, pp. 568-579.

[22] Michael Barborak, Anton Dahbura, Miroslaw Malek, The consensus problem in fault-tolerant computing, ACM Comput. Surv. 25 (2) (1993) 171-220.

[23] G. Jing, Y. Zou, D. Yu, C. Luo, X. Cheng, Efficient fault-tolerant consensus for collaborative services in edge computing, IEEE Trans. Comput. 72 (8) (2023) 2139-2150.

[24] Narayan Bhusal, Michael Abdelmalak, Md Kamruzzaman, Mohammed Benidris, Power system resilience: Current practices, challenges, and future directions, IEEE Access 8 (2020) 18064-18086.

[25] Diego Ongaro, John Ousterhout, In search of an understandable consensus algorithm, in:2014 USENIX Annual Technical Conference, USENIX ATC 14, USENIX Association, Philadelphia, PA, 2014, pp. 305-319.

[26] Teemu Koponen, Martin Casado, Natasha Gude, Jeremy Stribling, Leon Poutievski, Min Zhu, Rajiv Ramanathan, Yuichiro Iwata, Hiroaki Inoue, Takayuki Hama, Scott Shenker, Onix: A distributed control platform for large-scale production networks,in:9th USENIX Symposium on Operating Systems Design and Implementation, OSDI 10, USENIX Association, Vancouver, BC, 2010.

[27] Fabian Kuhn, Nancy Lynch, Calvin Newport, The Abstract MAC Layer, in: Idit Keidar (Ed.), Distributed Computing, 2009, pp. 48-62.

[28] Henrique Moniz, Nuno F. Neves, Miguel Correia, Byzantine fault-tolerant consensus in wireless ad hoc networks, IEEE Trans. Mob. Comput. 12 (12) (2013) 2441-2454.

[29] Nicola Santoro, Peter Widmayer, Agreement in synchronous networks with ubiquitous faults, Theoret. Comput. Sci. 384 (2) (2007) 232-249, Structural Information and Communication Complexity (SIROCCO 2005).

[30] Vitalik Buterin, Virgil Griffith, Casper the friendly finality gadget, 2017, CoRR bs/1710.09437.

[31] Liquan Chen, Chengjing Wang, Wenxuan Jiang, An efficient Byzantine fault-tolerant consensus mechanism based on aggregate threshold ring signature, in:2023 8th International Conference on Computer and Communication Systems, ICCCS, 2023, pp. 430-439.

[32] Xiaosheng Yu, Jie Qin, Peng Chen, Jiewu Leng, GPBFT: A practical Byzantine fault-tolerant consensus algorithm based on dual administrator short group signatures, Sec. Commun. Netw. 2022 (2022).

[33] A. Ogierman, A. Richa, C. Scheideler, S. Schmid, J. Zhang, Competitive MAC under adversarial SINR, in: IEEE INFOCOM, 2014, pp. 2751-2759.

[34] M. Castro, B. Liskov, Practical Byzantine fault tolerance, in: USENIX OSDI, 1999, pp. 173-186.

[35] George Coulouris, Jean Dollimore, Tim Kindberg, Distributed Systems - Concepts and Designs, third ed., 2002, p. 452.

[36] Henrique Moniz, Nuno Ferreira Neves, Miguel Correia, Paulo Veríssimo, Randomization can be a healer: Consensus with dynamic omission failures, in: Idit Keidar (Ed.), Distributed Computing, 2009, pp. 63-77.

[37] Nicola Santoro, Peter Widmayer, Agreement in synchronous networks with ubiquitous faults, Theoret. Comput. Sci. 384 (2) (2007) 232-249.

[38] Jinho Choi, Shancang Li, Xinheng Wang, Jeongseok Ha, A general distributed consensus algorithm for wireless sensor networks, in: 2012 Wireless Advanced, WiAd, 2012, pp. 16-21.

[39] Shu-Ching Wang, Kuo-Qin Yan, Wei-Shu Xiong, New anatomy of consensus in a multiple damage communication VANET, in: Jeng-Shyang Pan, Akinori Ito, Pei-Wei Tsai, Lakhmi C. Jain (Eds.), Recent Advances in Intelligent Information Hiding and Multimedia Signal Processing, Springer International Publishing, Cham, 2019, pp. 289-296.

[40] J. Wu, F. Dai, Mobility-sensitive topology control in mobile ad hoc networks, in:18th International Parallel and Distributed Processing Symposium, 2004. Proceedings, 2004, p. 28.

[41] Tao Li, Minyue Fu, Lihua Xie, Ji-Feng Zhang, Distributed consensus with limited communication data rate, IEEE Trans. Automat. Control 56 (2) (2011) 279-292.

[42] Shrut Kirti, Anna Scaglione, Robert J. Thomas, A scalable wireless communication architecture for average consensus, 2007, pp. 32-37.

[43] Stefania Santini, Alessandro Salvi, Antonio Saverio Valente, Antonio Pescapè Michele Segata, Renato Lo Cigno, Platooning maneuvers in vehicular networks: A distributed and consensus-based approach, IEEE Trans. Intell. Veh. 4 (1) (2019) 59-72.

[44] P. Thambidurai, You keun Park, Interactive consistency with multiple failure modes, in:Proceedings Seventh Symposium on Reliable Distributed Systems, IEEE Computer Society, Los Alamitos, CA, USA, 1988, 93, 94, 95, 96, 97, 98, 99, 100.

[45] Leslie Lamport, The part-time parliament, ACM Trans. Comput. Syst. 16 (2) (1998) 133-169.

[46] Ao Zhou, Shangguang Wang, Bo Cheng, Zibin Zheng, Fangchun Yang, Rong N. Chang, Michael R. Lyu, Rajkumar Buyya, Cloud service reliability enhancement via virtual machine placement optimization, IEEE Trans. Serv. Comput. 10 (6) (2017) 902-913.

[47] Fanmin Shi, Anthony Romano, Brandon Philips, Joe Betz, Gyuho Lee, Jingyi Hu, Xiang Li, Ben Darnell, Sam Batschelet, ETCD, https://github.com/etcdio/etcd.

[48] Tanghui Lin, BRAFT, https://github.com/baidu/braft.

[49] Teng Xu, Miodrag Potkonjak, Energy-efficient fault tolerance approach for Internet of Things applications, in:2016 IEEE/ACM International Conference on Computer-Aided Design, ICCAD, 2016, pp. 1-8.

[50] D.D. Geeta, N. Nalini, Rajashekhar C. Biradar, Fault tolerance in wireless sensor network using hand-off and dynamic power adjustment approach, J. Netw. Comput. Appl. 36 (4) (2013) 1174-1185.

[51] J.H. Kim, Ziqiang Liu, A.A. Chien, Compressionless routing: A framework for adaptive and fault-tolerant routing, IEEE Trans. Parallel Distrib. Syst. 8 (3) (1997) 229-244.

[52] Michael Dimopoulos, Yi Gang, Mounir Benabdenbi, Lorena Anghel, Nacer-Eddine Zergainoh, Michael Nicolaidis, Fault-tolerant adaptive routing under permanent and temporary failures for many-core systems-on-chip, in: 2013 IEEE 19th International on-Line Testing Symposium, IOLTS, 2013, pp. 7-12.

[53] Tian He J.A. Stankovic, Chenyang Lu T. Abdelzaher, SPEED: A stateless protocol for real-time communication in sensor networks,in:23rd International Conference on Distributed Computing Systems, 2003. Proceedings, 2003, pp. 46-55.

[54] T. He, J.A. Stankovic, T.F. Abdelzaher, C. Lu, A spatiotemporal communication protocol for wireless sensor networks, IEEE Trans. Parallel Distrib. Syst. 16 (10) (2005) 995-1006.

[55] Calvin Newport, Peter Robinson, Fault-Tolerant Consensus with an Abstract MAC Layer, in: Ulrich Schmid, Josef Widder (Eds.), DISC, Vol. 121, 2018, pp. 38:1-38:20.

[56] Calvin Newport, Consensus with an abstract MAC layer, in: PODC, 2014, pp. 66-75.

[57] Dongxiao Yu, Yifei Zou, Jiguo Yu, Yong Zhang, Feng Li, Xiuzhen Cheng, Falko Dressler, Francis C.M. Lau, Implementing the abstract MAC layer in dynamic networks, IEEE Trans. Mob. Comput. 20 (5) (2021) 1832-1845.

[58] Qilian Liang, Lingming Wang, Qingchun Ren, Fault-tolerant and energy efficient cross-layer design for wireless sensor networks, Int. J. Sen. Netw. 2 (3/4) (2007) 248-257.

[59] Bo Fu, Yang Xiao, Hongmei Deng, Hui Zeng, A survey of cross-layer designs in wireless networks, IEEE Commun. Surv. Tutor. 16 (1) (2014) 110-126.

[60] Leslie Lamport, Using time instead of timeout for fault-tolerant distributed systems, ACM Trans. Program. Lang. Syst. 6 (2) (1984) 254-280.

[61] Miguel Castro, Barbara Liskov, Practical Byzantine fault tolerance and proactive recovery, ACM Trans. Comput. Syst. 20 (4) (2002) 398-461.

[62] Seungmo Kim, Ahmed S. Ibrahim, Byzantine-fault-tolerant consensus via reinforcement learning for permissioned blockchain-empowered V2X network, IEEE Trans. Intell. Veh. 8 (1) (2023) 172-183.

[63] Lingjun Kong, Bing Chen, Feng Hu, LAP-BFT: Lightweight asynchronous provable Byzantine fault-tolerant consensus mechanism for UAV network trusted systems, in: Bohan Li, Lin Yue, Chuanqi Tao, Xuming Han, Diego Calvanese, Toshiyuki Amagasa (Eds.), Web and Big Data, Springer Nature Switzerland, Cham, 2023, pp. 232-246.

[64] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich, Algorand: Scaling Byzantine agreements for cryptocurrencies,in:Proceedings of the 26th Symposium on Operating Systems Principles, SOSP ’17, Association for Computing Machinery, New York, NY, USA, 2017, pp. 51-68.

[65] Zhiyuan Jiang, Zixu Cao, Bhaskar Krishnamachari, Sheng Zhou, Zhisheng Niu, SENATE: A permissionless Byzantine consensus protocol in wireless networks for real-time internet-of-things applications, IEEE Internet Things J. 7 (7) (2020) 6576-6588.

[66] Yifei Zou, Minghui Xu, Jiguo Yu, Feng Zhao, Xiuzhen Cheng, Fault-tolerant consensus with NOMA in mobile networks, IEEE Wirel. Commun. 29 (3) (2022) 80-86.

[67] Rong Wang, Wei-Tek Tsai, Feng Zhang, Le Yu, Hongyang Zhang, Yaowei Zhang, Adaptive Byzantine fault-tolerant ConsensusProtocol, in: Meikang Qiu, Zhihui Lu, Cheng Zhang (Eds.), Smart Computing and Communication - 7th International Conference, SmartCom 2022, New York City, NY, USA, November 18-20, 2022, Proceedings, in: Lecture Notes in Computer Science, vol. 13828, Springer, 2022, pp. 66-75.

[68] Li Zhang, Baoxian Zhang, Cheng Li, An efficient and reliable Byzantine fault tolerant blockchain consensus protocol for single-hop wireless networks, IEEE Trans. Wireless Commun. (2023) 1.

[69] Laphou Lao, Xiaohai Dai, Bin Xiao, Songtao Guo, G-pbft: A location-based and scalable consensus protocol for IoT-blockchain applications, in: 2020 IEEE International Parallel and Distributed Processing Symposium, IPDPS, IEEE, 2020, pp. 664-673.

[70] Wenyu Li, Chenglin Feng, Lei Zhang, Hao Xu, Bin Cao, Muhammad Ali Imran, A scalable multi-layer PBFT consensus for blockchain, IEEE Trans. Parallel Distrib. Syst. 32 (5) (2020) 1146-1160.

[71] Ningjie Gao, Ru Huo, Shuo Wang, Tao Huang, FIBFT: An improved Byzantine consensus mechanism for edge computing, in: 2023 IEEE Wireless Communications and Networking Conference, WCNC, IEEE, 2023, pp. 1-6.

[72] Xiaojun Xu, Lu Hou, Yankai Li, Yunxin Geng, Weighted RAFT: An improved blockchain consensus mechanism for internet of things application,in:2021 7th International Conference on Computer and Communications, ICCC, 2021, pp. 1520-1525.

[73] Md Shahjalal, Md Mainul Islam, Md Morshed Alam, Yeong Min Jang, Implementation of a secure LoRaWAN system for industrial Internet of Things integrated with IPFS and blockchain, IEEE Syst. J. 16 (4) (2022) 5455-5464.

[74] Lei Zhang, Hao Xu, Oluwakayode Onireti, Muhammad Ali Imran, Bin Cao, How much communication resource is needed to run a wireless blockchain network? IEEE Netw. 36 (1) (2021) 128-135.

[75] Ziyi Zhou, Oluwakayode Onireti, Lei Zhang, Muhammad Ali Imran, Muhammad Ali Imran, Performance analysis of wireless practical Byzantine fault tolerance networks using IEEE 802.11, in: 2021 IEEE Globecom Workshops, GC Wkshps, IEEE, 2021, pp. 1-6.

[76] L. Yang, Y. Zou, D. Yu, J. Yu, Distributed age-of-information optimization in edge computing for internet of vehicles, J. Syst. Archit. 144 (2023) 103000.

[77] Seungmo Kim, Ahmed S. Ibrahim, Byzantine-fault-tolerant consensus via reinforcement learning for permissioned blockchain-empowered V2X network, IEEE Trans. Intell. Veh. 8 (1) (2022) 172-183.

[78] Thomas Li, Lewis Tseng, Takamasa Higuchi, Seyhan Ucar, Onur Altintas, Poster: Fault-tolerant consensus for connected vehicles: A case study, in: Frank Kargl, Onur Altintas, Christoph Sommer, Takamasa Higuchi, Florian Klingler (Eds.), 13th IEEE Vehicular Networking Conference, VNC 2021, Ulm, Germany, November 10-12, 2021, IEEE, 2021, pp. 133-134.

[79] Tzu-Yen Tseng, Ding-Jiun Huang, Jia-You Lin, Po-Jui Chang, Chung-Wei Lin, Changliu Liu, Consensus-based fault-tolerant platooning for connected and autonomous vehicles, in: IEEE Intelligent Vehicles Symposium, IV 2023, Anchorage, AK, USA, June 4-7, 2023, IEEE, 2023, pp. 1-8.

[80] Lingjun Kong, Bing Chen, Feng Hu, LAP-BFT:Lightweight asynchronous provable Byzantine fault-tolerant consensus mechanism for UAV network trusted systems, in: Bohan Li, Lin Yue, Chuanqi Tao, Xuming Han, Diego Calvanese, Toshiyuki Amagasa (Eds.), Web and Big Data - 6th International Joint Conference, APWeb-WAIM 2022, Nanjing, China, November 25-27, 2022, Proceedings, Part III, in: Lecture Notes in Computer Science, vol. 13423, Springer 2022, pp. 232-246.