Treasonous Topologies: The Mathematical Bounds of Byzantine Agreement

Abstract

The Byzantine Generals Problem, introduced by Lamport, Shostak, and Pease, fundamentally addresses how a distributed system can achieve consensus even when some of its components are unreliable or malicious. This paper delves into the mathematical bounds that govern the solvability and efficiency of Byzantine Agreement (BA) protocols, specifically exploring the role of network topology in these limits. We examine classical impossibility results, such as the n $>$ 3f requirement for unauthenticated synchronous systems and the Fischer-Lynch-Paterson impossibility for deterministic asynchronous systems. Furthermore, we introduce "treasonous topologies" as a conceptual framework to systematically analyze how graph-theoretic properties like connectivity and diameter influence the minimum number of honest nodes required, message complexity, and time complexity. Special attention is paid to authenticated protocols which can relax certain bounds by employing digital signatures. This study elucidates the intricate relationship between adversarial capabilities, network structure, and the inherent mathematical constraints on achieving robust agreement in the presence of malicious nodes. We also touch upon modern applications in blockchain and distributed ledger technologies, where these theoretical bounds translate into practical considerations for security, scalability, and decentralization. A core contribution of this work is the synthesis of these established bounds with a detailed examination of how varying network structures fundamentally dictate protocol design and performance, offering a clearer lens through which to understand the vulnerabilities and strengths of real-world distributed systems.