Ratcheta: Memory-bounded hybrid byzantine consensus for cooperative embedded systems
Xu W, Kapitza R (2019)
Publication Type: Conference contribution
Publication year: 2019
Journal
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
Involved external institutions
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