The Pipes Model for Latency and Throughput Analysis


Abstract: In much of the distributed computing literature, latency is expressed as the number of communication rounds or network delays; such metrics do not directly account for the amount of data sent or the dependencies among parties sending the data. Throughput is also normally evaluated empirically. As a consequence, the standard models used for analysing state machine replication (SMR) protocols do not by themselves provide an end-to-end analytical comparison of practical latency and throughput as functions of per-processor bandwidth and transaction arrival rate.

In this paper, we present Pipes, a model for analysing latency and throughput in SMR protocols. The Pipes model captures the effect of processor bandwidth $S$, transaction arrival rate $D$, and network delays, enabling us to explicitly specify the throughput bottleneck and the latency of a protocol. Using Pipes, we derive good-case latency expressions and throughput bottlenecks for concrete multi-shot protocols implementing Best-effort Broadcast, Consistent Broadcast, Reliable Broadcast, and Reliable Broadcast with erasure coding and pipelining. We consider both single-sender and multi-sender approaches, and extend the analysis to SMR protocols including DispersedSimplex, Sailfish, Tendermint, and HotStuff. Our comparisons reveal the trade-off between the lower latency achievable through pipelining and erasure coding in single-sender protocols and the higher throughput bottlenecks achievable by multi-sender DAG-based protocols. We also quantify when the additional communication phases of HotStuff are preferable to the fixed wait in a Tendermint-style protocol.

Beyond these protocol-specific latency calculations, we establish tight Best-effort Broadcast latency bounds in both the single-sender and multi-sender settings. The analysed protocols are optimal when each recipient receives a full block directly from the transaction’s source, the same blocks are sent to everyone, and outstanding upload work is bounded. We give a second tight bound assuming only direct receipt, attained by a protocol that staggers block boundaries across recipients. For protocols using AVID-style erasure coding, we prove latency lower bounds that combine block formation, reconstruction and fragment forwarding.

Finally, we implement and evaluate variants of DispersedSimplex and Sailfish, comparing measured latency with the predictions of the Pipes model.

Joint work with Kartik Nayak and Nibesh Strestha.

Here is the pdf, (S&P 2026)