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.
Der Konsens ist ein grundlegendes Problem in verteilten Systemen. Heutzutage gibt es immer mehr kooperative und autonome Systeme, in denen verschiedene Teilnehmer koordinieren und zusammenarbeiten, um ein gemeinsames Ziel zu erreichen. Die meisten dieser Systeme erfordern eine hohe Fehlerresistenz – andernfalls könnte ein einzelner fehlerhafter Knoten das gesamte System unbrauchbar machen. Dies erfordert im Wesentlichen einen byzantinisch fehlertoleranten Konsens. Typischerweise können jedoch nur (n−1)/3 fehlerhafte Knoten in einer Gruppe von n Knoten toleriert werden, wenn das System partiell synchron ist. Diese Fehlertoleranzrate ist viel niedriger als in Absturz-Fehlertoleranz, wobei (n−1)/2 fehlerhafte Knoten toleriert werden können. Noch schlimmer, Systeme mit nur drei Knoten sind zu klein, um überhaupt einen einzelnen byzantinischen Knoten zu tolerieren. Da das byzantinische Fehlermodell, in dem Knoten beliebig fehlerhaft sein können, zu pessimistisch ist, wird in dieser Arbeit ein hybrides Fehlermodell betrachtet. In einem solchen Fehlermodell ist jeder Knoten mit einem kleinen vertrauenswürdigen Subsystem ausgestattet, das nur Crash-Fehler haben kann, während der Rest des Systems weiterhin byzantinisch sein kann. Durch die Nutzung des vertrauenswürdigen Subsystems werden zwei Konsens-Algorithmen entworfen: TRUSTED BEN-OR ist ein randomisierter Algorithmus, der den binären Konsens löst, und RATCHETA ist ein deterministischer mehrwertiger Konsensalgorithmus. Beide Algorithmen verwenden vertrauenswürdige monotone Zähler und verbessern die maximal tolerierbaren Fehler auf (n−1)/2 im asynchronen oder partiell synchronen System. Darüber hinaus sind beide Algorithmen auf drahtlose eingebettete Systeme zugeschnitten. Sie haben eine kleine Nachrichtenkomplexität und verwenden Multicast, um den Kommunikationsaufwand zu verringern. Sie verlassen sich weder auf zuverlässige Netzwerkprotokolle, z.B. TCP, noch andere Kommunikationsprimitive wie Reliable-Broadcast. Es werden verschiedene Anwendungsszenarien im Bereich Robotik und Fahrzeugkommunikation untersucht. Beispielsweise wird ein Anwendungsfall von Lebenssuchrobotern vorgestellt, wenn der mehrwertige Konsens und RATCHETA vorgestellt werden. Am Ende wird eine kompliziertere Anwendung im Fahrzeug-Ad-hoc-Netzwerk mit dem Namen Maneuver Coordination Service in Betracht gezogen. Koordinierungsprotokoll für den Maneuver Coordination Service wird entwickelt. Mit diesem Protokoll kann eine Gruppe von Fahrzeugen eine Einigung über ihre Fahrbahnen erzielen, wodurch die Verkehrseffizienz verbessert und gleichzeitig die Sicherheit gewährleistet werden kann.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
