CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

On the Design and Analysis of Consensus Protocols for Automotive Electronic Systems

Negin Fathollah Nejad Asl (Institutionen för data- och informationsteknik, Datorteknik (Chalmers))
Göteborg : Chalmers University of Technology, 2014. - 115 s.

This thesis deals with the fundamental problem of reaching agreement on a value in a distributed computing system in the presence of faults. We address this problem in the context of safety-critical distributed automotive applications, such as virtual traffic lights. In such systems, it is essential that different computers can make coordinated and mutually consistent decisions. To this end, they must reach agreement on the data they use as a basis for their decisions. The problem of ensuring that a group of computers agrees on a value, or a set of values, is known as the consensus problem. We consider this problem for systems that use unreliable communication channels, e.g., wireless channels, where an arbitrary number of messages can be lost during the execution of an agreement algorithm. Previous research has shown that it is impossible to construct an algorithm that guarantees consensus under the assumption that the number of communication failures is unbounded. Our aim is therefore to design consensus algorithms that minimize the probability of disagreement under this failure model. To this end, we propose and investigate three variants of an agreement algorithm. These variants are distinguished by their decision criterion, which decides whether a computer should decide on a value or abort. We conduct our analysis for both symmetric and asymmetric communication failures. Our analysis show that the probability of disagreement depends strongly on the number of computers in the system, the number of rounds of message exchange, and the probability of message loss. We show that a moderately pessimistic decision criterion achieves a lower maximum probability of disagreement compared to both an optimistic and a pessimistic decision criterion.

Nyckelord: Distributed Algorithms; Consensus; Probabilistic Analysis; Communication Failures; Automotive Systems

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2014-05-05.
CPL Pubid: 197580


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datorteknik (Chalmers)


Informations- och kommunikationsteknik
Inbäddad systemteknik

Chalmers infrastruktur


Datum: 2014-05-28
Tid: 10:00
Lokal: EF E-Building
Opponent: Felicita Di Giandomenico