Distributed computer systems have become a fundamental part of our lives. These systems power so many critical functions of our society that it is hard to imagine the consequences if they were to collapse. However, many of these systems are just a single point away from failure: if even a single machine is compromised by a malicious actor, the entire system can crumble. In order to build a reliable digital foundation for the future, our computer systems must be able to tolerate such faults. Through replication, Byzantine agreement protocols enable us to build applications that function normally even when some machines behave maliciously. However, existing Byzantine agreement protocols are expensive: the more failures they tolerate, the steeper the communication costs. For some applications, those protocols fail to scale: the bandwidth usage is simply too high to meet the application demand.

In this thesis, we revisit the problem of Byzantine agreement, the most important building block of fault-tolerant distributed systems. We focus on the communication cost of Byzantine agreement, providing contributions in three directions: (1) showing that some costs are unavoidable, (2) improving the cost in worst-case scenarios, and (3) improving the cost in good-case scenarios that are common in practice.

First, we study the Byzantine agreement problem in the synchronous network model in a general manner. We determine the weakest non-trivial variant of the problem and show that, if we want to tolerate up to t faulty machines, we must exchange at least Ω(t^2) messages to solve even this variant. This proves that, regardless of the type of Byzantine agreement problem we attempt to solve, we cannot avoid exchanging Ω(t^2) messages.

Second, we improve the worst-case communication cost of Byzantine agreement in the partially synchronous network model. We first present DARE, an optimally resilient Byzantine agreement algorithm for any n machines that effectively improves on the state-of-the-art by a factor of pn exchanged bits. We then present DARE-STARK, a version of DARE enhanced with heavier cryptography, which achieves optimal bit-complexity for sufficiently large values.

Finally, we improve the cost of Byzantine agreement in practice, focusing on the good-case performance of Byzantine atomic broadcast (a form of Byzantine agreement). We present Chop Chop, a Byzantine atomic broadcast system that can order, authenticate, deduplicate, and reliably deliver tens of millions of client messages per second. Chop Chop relies on a new interactive algorithm that leverages trustless entities, brokers, to securely outsource most of the communication and computation costs of the main servers. This enables Chop Chop to achieve close to line rate network efficiency, using upwards of 92% of server bandwidth for application payloads, effectively eliminating the overhead of Byzantine agreement in normal situations. Running on 64 medium servers across the globe, Chop Chop processes 43 million messages per second, two orders of magnitude better than competing systems.