General Extension of FABAN and a Topology-based Approach to tolerate any Number of Faults

Abstract:
FABAN is a fault tolerant atomic broadcast and agreement protocol in bridge-connected networks, which is well understood, precisely analysed and proved for the case with f = 1 faulty bridge. This paper introduces a general extension of FABAN for an arbitrary number f of faulty bridges and specifies the requirements for the underlying bridge-connected topology. The extension is fully compatible to the original protocol description, i.e. is identical in the case f = 1. A topology-based approach is provided as a solution to the problem of tolerating an arbitrary number of faults on the one side and low-cost topologies in regard to a relative small amount of bridges and connections on the other side. Related to this, a rather simple class of network topologies is defined and it is proven, that each network participant can send atomic broadcast messages via FABAN with all benefits the protocol provides.