FABAN – Fault-Tolerant Atomic Broadcast and Agreement in Bridge-Connected Networks

Abstract:
FABAN is a new protocol to solve atomic broadcast and Byzantine agreement in a bridge-connected network that provides only f + 1 disjoint paths between any pair of bridges, where f is the number of bridges assumed to be faulty. The case f = 1 with 2 redundant paths is expected to be typical since higher numbers of redundant paths lead to costly networks. In FABAN broadcast messages are signed by the sender and distributed in the network by so-called waves and counterwaves. The three tasks (1) message distribution, (2) message’s timeliness checking, and (3) message forwarding are separated between disjoint sets of bridges. As usual, bridges must forward messages according to the topology of the network. Besides this the functionality of bridges is kept as simple as possible. An algorithm for the generation of waves and counterwaves for arbitrary topologies is provided and its completeness formally proven.