A Fast Byzantine Fault-Tolerant Diagnostic Agreement Protocol for Synchronous Distributed Systems

Conference: ARCS 2016 - 29th International Conference on Architecture of Computing Systems
04/04/2016 - 04/07/2016 at Nürnberg, Deutschland

Proceedings: ARCS 2016

Pages: 11Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Bousbiba, Omar; Echtle, Klaus (Dependability of Computer Systems, University of Duisburg-Essen, Essen, Germany)

Generally, most Byzantine Agreement protocols reach agreement on a value or vector of values proposed by one or more predefined nodes (called source nodes). Only few protocols are also capable of detecting and locating faulty nodes. On the contrary, most diagnosis algorithms are restricted to local fault detection and localization. In this paper we present a new fault-tolerant Byzantine diagnostic agreement protocol (FTDAP) which performs fault detection as well as agreement on the faulty components (nodes and communication channels). An FTDAP can be combined with a “standard” agreement protocol (AP) to provide both fault tolerance and fault-tolerant fault localization. This is the first proposal of a diagnostic agreement protocol which solves the diagnosis agreement problem (DAP) in the presence of f arbitrarily faulty components using at least max(2, rAP + 1) rounds. The value rAP depends on the used AP. As a minimum only two rounds are required to solve the FTDAP problem by exchanging one message per node in the first round, and a matrix with at most 3∙(2f + 1) diagnostic information entries in the second round, where f is the number of faulty components.