Hybrid fault-tolerant consensus in asynchronous and wireless embedded systems
Xu W, Schwarz-Rüsch S, Li B, Kapitza R (2019)
Publication Type: Conference contribution
Publication year: 2019
Journal
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 125
Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs
Event location: Hong Kong, CHN
ISBN: 9783959770989
DOI: 10.4230/LIPIcs.OPODIS.2018.15
Abstract
Byzantine fault-tolerant (BFT) consensus in an asynchronous system can only tolerate up to [n-1/3] faulty processes in a group of n processes. This is quite a strict limit in certain application scenarios, for example a group consisting of only 3 processes. In order to break through this limit, we can leverage a hybrid fault model, in which a subset of the system is enhanced and cannot be arbitrarily faulty except for crashing. Based on this model, we propose a randomized binary consensus algorithm that executes in complete asynchrony, rather than in partial synchrony required by deterministic algorithms. It can tolerate up to [n-1/3] Byzantine faulty processes as long as the trusted subsystem in each process is not compromised, and terminates with a probability of one. The algorithm is resilient against a strong adversary, i. e. the adversary is able to inspect the state of the whole system, manipulate the delay of every message and process, and then adjust its faulty behaviour during execution. From a practical point of view, the algorithm is lightweight and has little dependency on lower level protocols or communication primitives. We evaluate the algorithm and the results show that it performs promisingly in a testbed consisting of up to 10 embedded devices connected via an ad hoc wireless network.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Xu, W., Schwarz-Rüsch, S., Li, B., & Kapitza, R. (2019). Hybrid fault-tolerant consensus in asynchronous and wireless embedded systems. In Jiannong Cao, Faith Ellen, Luis Rodrigues, Bernardo Ferreira (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Hong Kong, CHN: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Xu, Wenbo, et al. "Hybrid fault-tolerant consensus in asynchronous and wireless embedded systems." Proceedings of the 22nd International Conference on Principles of Distributed Systems, OPODIS 2018, Hong Kong, CHN Ed. Jiannong Cao, Faith Ellen, Luis Rodrigues, Bernardo Ferreira, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019.
BibTeX: Download