Ratcheta: Memory-bounded hybrid byzantine consensus for cooperative embedded systems

Xu W, Kapitza R (2019)

Publication Type: Conference contribution

Publication year: 2019

Journal

Proceedings of the IEEE Symposium on Reliable Distributed Systems IEEE Computer Society

Publisher: IEEE Computer Society

Book Volume: 2019-October

Pages Range: 103-112

Conference Proceedings Title: Proceedings of the IEEE Symposium on Reliable Distributed Systems

Event location: Salvador, BRA

ISBN: 9781538683019

DOI: 10.1109/SRDS.2018.00021

Abstract

Cooperative autonomous systems gain increasing popularity nowadays. Most of these systems demand for high fault-resilience, otherwise a single faulty node could render the whole system useless. This essentially calls for a Byzantine fault-tolerant consensus. However, in such algorithms typically only [ ^n−1/ 3 ] faulty nodes can be tolerated in a group of n nodes and the message complexity is high. Even worse, systems with only 3 nodes are too small to even tolerate a single Byzantine node. In this work we present a novel consensus algorithm, RATCHETA. On the one hand it increases the maximum tolerable faulty nodes to [ ^n−1/ 2] and lowers the message complexity. This is achieved by assuming a hybrid fault model, which features the use of a small trusted subsystem that hosts a pair of monotonic counters for message authentication to prevent equivocation. Moreover, it can ensure an upper bound of the memory usage and message size, which is not addressed by most other hybrid consensus algorithms. On the other hand RATCHETA is tailored for wireless embedded systems. It uses multicast to reduce the communication overhead, and it does not rely on any packet loss detection or retransmission mechanisms. We implemented RATCHETA with its trusted subsystem built on top of ARM TrustZone. Our experimental results show that RATCHETA can tolerate both Byzantine faults and a certain amount of omission faults. With 20% message omissions, a 10-node group needs less than 1 second on average to reach a consensus. If 4 nodes out of 10 become Byzantine, the consensus latency is only about 1-3.6 seconds even under rough network conditions.

Authors with CRIS profile

Rüdiger Kapitza

Involved external institutions

Technische Universität Braunschweig

Germany (DE)

How to cite

APA:

Xu, W., & Kapitza, R. (2019). Ratcheta: Memory-bounded hybrid byzantine consensus for cooperative embedded systems. In Proceedings of the IEEE Symposium on Reliable Distributed Systems (pp. 103-112). Salvador, BRA: IEEE Computer Society.

MLA:

Xu, Wenbo, and Rüdiger Kapitza. "Ratcheta: Memory-bounded hybrid byzantine consensus for cooperative embedded systems." Proceedings of the 37th Symposium on Reliable Distributed Systems, SRDS 2018, Salvador, BRA IEEE Computer Society, 2019. 103-112.

BibTeX: Download