Summary
In systems where many computers need to share the same message reliably even if some computers are broken or acting badly, how the message is shared matters a lot. The authors compare three different methods for doing this kind of reliable message sharing, including one called coded MBRB that uses special math to send less data. They found that coded MBRB works better for bigger messages by saving time and bandwidth but uses more computing power to handle math and encryption. The other methods use less computing power for smaller messages but become more costly as messages get bigger. Their work also provides tools to test and compare these methods fairly and in realistic settings.
Byzantine reliable broadcastfault tolerancedistributed systemscryptographynetwork latencydata encodingfault injectionprotocol benchmarkingmessage disseminationcloud deployment
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.