Self-Stabilizing Byzantine Fault-Tolerant State Machine Replication - Rust Implementation, Experimental Evaluation and Applications in Trucks

Abstract

Modern society relies on many critical digital services such as cloud storage and vehicular systems. To bring reliability to these services, State Machine Replication (SMR) is one possibility. This thesis focuses on the performance evaluation of the SMR algorithm by Dolev et al.. Specifically, our evaluation criterion considers latency, which is the time from when a client issues a request until it has received replies from the servers. We base our study on an analytical estimation of the latency as well as a high-quality pilot implementation in the Rust programming language, which is suitable for embedded systems. Moreover, since Dolev et al. consider both synchronous and asynchronous system executions, we study our pilot implementation on PlanetLab with 15 nodes and 26 ms message round trip delay as well as an embedded system with 5 nodes and 0.17 ms message round trip delay. We find that the SMR algorithm by Dolev et al. scales linearly with the number of completed requests, the number of servers as well as the number of clients. Furthermore, we also find that the performance behavior is similar in the two environments, although the network latency plays a big role. In addition to the above, we have also identified three possible use cases of SMR in trucks. Regarding the use of unbounded variables, queues, and message sizes that appear in the SMR algorithm by Dolev et al., we offer the use of a global reset algorithm by Georgiou et al. In addition to a detailed evaluation of the algorithm, we explain how this self-stabilizing algorithm can fit in the analytical framework of Dolev et al., which considers both Byzantine faults and arbitrary transient faults. Our evaluation shows that the latency of the global reset algorithm is around four times the slowest network round trip time of the participating nodes.