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

Abstract:
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.