License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.15
URN: urn:nbn:de:0030-drops-100757
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10075/
Go to the corresponding LIPIcs Volume Portal

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

Hybrid Fault-Tolerant Consensus in Asynchronous and Wireless Embedded Systems

pdf-format:
LIPIcs-OPODIS-2018-15.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{xu_et_al:LIPIcs:2018:10075,
  author =	{Wenbo Xu and Signe R{\"u}sch and Bijun Li and R{\"u}diger Kapitza},
  title =	{{Hybrid Fault-Tolerant Consensus in Asynchronous and Wireless Embedded Systems}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10075},
  URN =		{urn:nbn:de:0030-drops-100757},
  doi =		{10.4230/LIPIcs.OPODIS.2018.15},
  annote =	{Keywords: Distributed system, consensus, fault tolerance}
}

Keywords: Distributed system, consensus, fault tolerance
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI