Paper 2024/137

Consensus in the Known Participation Model with Byzantine Failures and Sleepy Replicas

Abstract

We study consensus in the known participation model with both Byzantine failures and sleepy replicas, where honest replicas may unpredictably fall asleep, and replicas know the minimum number of awake honest replicas. Our main contribution is providing a fine-grained treatment of consensus in such a mixed failure model. First, we present a synchronous atomic broadcast protocol with $5\Delta+2\delta$ expected latency and $2\Delta+2\delta$ best-case latency, where $\Delta$ is the bound on network delay and $\delta$ is the actual network delay. Second, in the partially synchronous network (the value of $\Delta$ is unknown), we show that one can make a conventional Byzantine fault-tolerant (BFT) protocol tolerate sleepy replicas but has to make the stable storage assumption (where replicas need to store intermediate consensus parameters in stable storage). Finally, in the partially synchronous network but not assuming stable storage, we show several bounds on the relationship between the total number of replicas $n$, the maximum number of Byzantine replicas $f$, and the maximum number of simultaneous sleeping replicas $s$. Using these bounds, we transform HotStuff (PODC'19) into a protocol that tolerates sleepy replicas without sacrificing the performance.