2024/12/18 by Monti, Matteo, Camaioni, Martina, Roman, Pierre-Louis · 1 citation
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2412.14061
This paper presents the Byzantine fault-tolerant agreement protocols Flutter and Blink. Both algorithms are deterministic, leaderless and signature-free; both assume partial synchrony and at least (5f + 1) servers, where f bounds the number of faults. The main contribution, Flutter, is a Total-Order Broadcast implementation that achieves faster broadcast-to-delivery latency by removing the extra message delay associated with serializing messages through a leader. In the "good case" where all processes are correct, the network is synchronous, and local clocks are well-synchronized, Flutter delivers client requests in (2Δ+ ε) time units, Δ being the message delay and ε an arbitrarily small constant. Under the same conditions, state-of-the-art protocols require 3Δ time units. Flutter's good-case latency is quasi-optimal, meaning it cannot be improved upon by any finite amount. Under the hood, Flutter builds upon Blink, a (Representative) Binary Consensus implementation whose fast path enables decisions in Δ time units when all correct servers propose the same value. Blink generalizes the existing Binary Consensus solution Bosco from the (7f + 1) to the (5f + 1) setting.