Search papers, labs, and topics across Lattice.
Hermes introduces a two-round rotating-leader protocol designed to mitigate tail latency in leader-based Byzantine Fault Tolerance (BFT) systems by allowing expired views to finalize. By utilizing prefix consensus, Hermes enables any $n-f$ votes to finalize the heaviest common prefix, thus overcoming the limitations of traditional timeout strategies that either stall or invalidate leader proposals. The method achieves efficient message complexity while maintaining robustness against slow or crashed leaders, significantly improving finalization times in partially synchronous environments.
Expired views can now finalize, drastically reducing tail latency in BFT protocols where leader performance is inconsistent.
Leader-based BFT protocols finalize through their leaders: a view whose leader is crashed or slow finalizes nothing, and the timeout that ends it admits no good setting. A conservative timeout turns every crashed leader into a long stall; an aggressive one voids the views of leaders that are merely slow. Either way the expired view is wasted, and this trade-off, not the good case, governs tail latency. Hermes makes expired views finalize. Hermes is a two-round rotating-leader protocol for $n=5f+1$ processes under partial synchrony built on prefix consensus: votes carry values ordered by a prefix relation, and quorums require comparability rather than equality. Every process broadcasts a justified proposal at view start and casts a single vote, for the leader's proposal upon delivery or for a fallback proposal at the timeout; there are no nullify votes. A timely honest leader finalizes its full proposal in $2\delta$. Otherwise, any $n-f$ votes, which need not match, finalize the heaviest common prefix. We instantiate Hermes as a finality gadget over an available chain and over Autobahn-style multi-lane dissemination, where parent-relative delta tipcuts with explicit skips keep independent proposals comparable and sender-indexed erasure-coded amplification keeps complexity at $O(n^2\hat{m}+\lambda n^3)$ bits and $O(n^2)$ messages per view, where $\hat{m}$ is the number of concurrent dissemination lanes in Autobahn and $\lambda$ the security parameter.
