Benchmarking Byzantine broadcast algorithms reveals trade offs in cloud environments
From Bracha to Coded MBRB: Benchmarking Byzantine Reliable Broadcast Implementations
Distributed, Parallel, and Cluster Computing
Summary
Ensuring that messages are reliably shared even when some parts of a network misbehave (called Byzantine faults) is important for secure distributed systems. This paper compares three key algorithms for this problem by implementing and testing them in realistic settings. The researchers found that one new method, called Coded MBRB, sends less data and is faster for bigger messages in cloud environments, but it costs more in computation. Older methods use less CPU for small messages but become costly as message size grows. Their work provides detailed performance insights beyond theoretical descriptions.
What this means in practice
- •For distributed systems engineers: Optimize fault-tolerant message broadcast choices in cloud-based networks by balancing communication and computation costs for different payload sizes.
- •For cloud infrastructure teams: Deploy more efficient reliable broadcast protocols in multi-node cloud environments to improve latency and bandwidth usage for large data transfers.
Authors
Yenan Wang, Jesper Kullberg, Fabian Paglianno Persson, Elad Michael Schiller, Timothé Albouy
Abstract
Byzantine Reliable Broadcast (BRB) and Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) are reliable-dissemination abstractions for fault-tolerant distributed systems. Yet their operational behavior is shaped not only by specifications and asymptotic communication bounds, but also by serialization, cryptography, buffering, orchestration, deployment environment, and fault-injection semantics. This paper implements and evaluates Bracha [Information and Computation, 1987], AFRT by Albouy et al. [TCS, 2023], and Coded MBRB by Albouy et al. [OPODIS, 2024]. We implement the algorithms in a shared Go codebase with common orchestration, instrumentation, parser-based specification checks, fault injection, and an open-source reproducibility artifact. The evaluation uses single-shot broadcasts in the Shadow network simulator, native profiling, a Google Cloud Platform deployment, and a distributed FABRIC testbed, covering controlled experiments up to 30 nodes, payloads up to 40 MB, 92,190 runs, and 2,361,600 parser-checked entries. The results show that Coded MBRB reduces transmitted data and improves latency in the evaluated cloud setting for larger payloads, but shifts cost to cryptographic and coding computation. Bracha and AFRT incur lower CPU costs at smaller payloads, but their full-payload dissemination increases processing, allocation, and network costs as payloads grow. Across the tested configurations, the parser found no duplicate deliveries, conflicting deliveries, or deliveries of values different from the sender's payload. The paper contributes implementation-level evidence and an extensible artifact for benchmarking BRB and MBRB as executable distributed-system components, exposing bottlenecks and operational trade-offs that are hidden by algorithmic descriptions alone.