Hybrid Fault Tolerant Consensus in Wireless Embedded Systems

摘要

Consensus is a fundamental problem in distributed system. Nowadays cooperative autonomous systems gain increasing popularity, in which different participants can work in a coordinated way to achieve a common goal. 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, typically only （n−1)/3 faulty nodes can be tolerated in a group of n nodes if the system is partially synchronous. This fault-tolerance rate is much lower than (n−1)/3 in crash fault-tolerance. Even worse, systems with only 3 nodes are too small to even tolerate a single Byzantine node. Since the Byzantine fault model where nodes can be arbitrarily faulty is too pessimistic, a more realistic hybrid fault model is considered in this thesis. In such a hybrid fault model, every node is equipped with a small trusted subsystem that can only be faulty by crashing, while the remaining part of the system can still be Byzantine. By exploiting the trusted subsystem, two consensus algorithms are proposed: TRUSTED BEN-OR is a binary consensus algorithm that can work in an asynchronous system, and RATCHETA is a multi-value consensus algorithm designed for partially synchronous systems. Both algorithms utilize the trusted monotonic counter(s) and improve the maximum tolerable faults to (n−1)/2 in their system models. Moreover, both algorithms are tailored for wireless embedded systems. They have low message complexity and use multicast to reduce the communication overhead, and they rely on neither low-level reliable transmission protocols, e.g. TCP, nor other complex primitives such as reliable broadcasting. Several application scenarios in the field of robotics and vehicular communication are investigated. For example, a use case of life-searching robots is introduced when explaining multi-value consensus and RATCHETA. In the end, a more complicated application in vehicular ad-hoc network named Maneuver Coordination service is introduced. A coordination protocol based on consensus is designed for Maneuver Coordination service, allowing a group of vehicles to reach agreement on their driving trajectories, which can improve traffic efficiency while keeping safety.