Document Open Access Logo

Hybrid Fault-Tolerant Consensus in Asynchronous and Wireless Embedded Systems

Authors Wenbo Xu, Signe Rüsch, Bijun Li, Rüdiger Kapitza

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.15.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

Wenbo Xu
  • Technische Universität Braunschweig, Braunschweig, Germany
Signe Rüsch
  • Technische Universität Braunschweig, Braunschweig, Germany
Bijun Li
  • Technische Universität Braunschweig, Braunschweig, Germany
Rüdiger Kapitza
  • Technische Universität Braunschweig, Braunschweig, Germany

Funding

  • Kapitza, Rüdiger: This work is part of the DFG Research Unit Controlling Concurrent Change, funding no. FOR 1800 and grant no. KA 3171/5-1.

Cite AsGet BibTex

Wenbo Xu, Signe Rüsch, Bijun Li, and Rüdiger Kapitza. Hybrid Fault-Tolerant Consensus in Asynchronous and Wireless Embedded Systems. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.15

Abstract

Byzantine fault-tolerant (BFT) consensus in an asynchronous system can only tolerate up to floor[(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 floor[(n-1)/2] 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.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Software fault tolerance
Keywords
  • Distributed system
  • consensus
  • fault tolerance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham, Danny Dolev, and Joseph Y Halpern. An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience. In Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, pages 405-414. ACM, 2008. Google Scholar
  2. Marcos K Aguilera and Sam Toueg. The correctness proof of Ben-Or’s randomized consensus algorithm. Distributed Computing, 25(5):371-381, 2012. Google Scholar
  3. ARM. ARM Security Technology - Building a Secure System using TrustZone Technology, ARM Technical White Paper, 2009. Google Scholar
  4. H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics, pages 255-256. Wiley Series on Parallel and Distributed Computing. Wiley, 2004. Google Scholar
  5. Johannes Behl, Tobias Distler, and Rüdiger Kapitza. Hybrids on Steroids: SGX-Based High Performance BFT. In Proceedings of the Twelfth European Conference on Computer Systems, pages 222-237. ACM, 2017. Google Scholar
  6. Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 27-30. ACM, 1983. Google Scholar
  7. Gabriel Bracha. An asynchronous [(n-1)/3]-resilient consensus protocol. In Proceedings of the third annual ACM symposium on Principles of distributed computing, pages 154-162. ACM, 1984. Google Scholar
  8. Gabriel Bracha and Sam Toueg. Resilient consensus protocols. In Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 12-26. ACM, 1983. Google Scholar
  9. Ran Canetti and Tal Rabin. Fast asynchronous Byzantine agreement with optimal resilience. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 42-51. ACM, 1993. Google Scholar
  10. Miguel Correia, Giuliana S Veronese, and Lau Cheuk Lung. Asynchronous Byzantine consensus with 2f+ 1 processes. In Proceedings of the 2010 ACM symposium on applied computing, pages 475-480. ACM, 2010. Google Scholar
  11. J. Q. Cui, S. K. Phang, K. Z. Y. Ang, F. Wang, X. Dong, Y. Ke, S. Lai, K. Li, X. Li, F. Lin, J. Lin, P. Liu, T. Pang, B. Wang, K. Wang, Z. Yang, and B. M. Chen. Drones for cooperative search and rescue in post-disaster situation. In 2015 IEEE 7th International Conference on Cybernetics and Intelligent Systems (CIS) and IEEE Conference on Robotics, Automation and Mechatronics (RAM), pages 167-174, 2015. URL: http://dx.doi.org/10.1109/ICCIS.2015.7274615.
  12. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288-323, 1988. Google Scholar
  13. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382, 1985. Google Scholar
  14. Zafar Iqbal, Kiseon Kim, and Heung-No Lee. A cooperative wireless sensor network for indoor industrial monitoring. IEEE Transactions on Industrial Informatics, 13(2):482-491, 2017. Google Scholar
  15. Rüdiger Kapitza, Johannes Behl, Christian Cachin, Tobias Distler, Simon Kuhnle, Seyed Vahid Mohammadi, Wolfgang Schröder-Preikschat, and Klaus Stengel. CheapBFT: Resource-efficient Byzantine Fault Tolerance. In European Chapter of ACM SIGOPS, editor, Proceedings of the EuroSys 2012 Conference, pages 295-308, 2012. Google Scholar
  16. Yasuhiro Kuriki and Toru Namerikawa. Consensus-based cooperative formation control with collision avoidance for a multi-UAV system. In American Control Conference (ACC), 2014, pages 2077-2082. IEEE, 2014. Google Scholar
  17. Dave Levin, John R Douceur, Jacob R Lorch, and Thomas Moscibroda. TrInc: Small Trusted Hardware for Large Distributed Systems. In NSDI, volume 9, pages 1-14, 2009. Google Scholar
  18. Linaro. Open Portable Trusted Execution Environment. https://www.op-tee.org, visited in September, 2018. Google Scholar
  19. Henrique Moniz, Nuno Ferreira Neves, and Miguel Correia. Turquois: Byzantine consensus in wireless ad hoc networks. In Dependable Systems and Networks (DSN), 2010 IEEE/IFIP International Conference on, pages 537-546. IEEE, 2010. Google Scholar
  20. Bruno Vavala and Nuno Neves. Robust and speculative Byzantine randomized consensus with constant time complexity in normal conditions. In Reliable Distributed Systems (SRDS), 2012 IEEE 31st Symposium on, pages 161-170. IEEE, 2012. Google Scholar
  21. Paulo E Veríssimo. Travelling through wormholes: a new look at distributed systems models. ACM SIGACT News, 37(1):66-81, 2006. Google Scholar
  22. Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, Lau Cheuk Lung, and Paulo Verissimo. Efficient byzantine fault-tolerance. Computers, IEEE Transactions on, 62(1):16-30, 2013. Google Scholar
  23. Wenbo Xu and Rüdiger Kapitza. RATCHETA: Memory-bounded Hybrid Byzantine Consensus for Cooperative Embedded Systems. In Reliable Distributed Systems (SRDS), 2018 IEEE thirty-seventh Symposium on. IEEE, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact