PhD Defense: Towards scalability and efficiency in distributed systems

https://umd.zoom.us/u/aKuBBlCxU
Effective agreement is crucial for coordinating actions within decentralized systems consisting of many independent agents (processes) that are prone to failures. With the rise of the demand and interest in decentralized systems, with the most notable examples of decentralized currencies like Bitcoin and Ethereum, the effort required to maintain consistency in these systems grows significantly. For instance, data reveals that Bitcoin miners consume between 0.6% to 2.3% of U.S. electricity. Consequently, there is a pressing need for new agreement algorithms that could reduce energy consumption but at the same time offer scalability for the growing number of users. Nevertheless, despite almost 40 years of research, the foundational theoretical model of agreement in all distributed systems, the Consensus problem still holds unresolved complexity issues obstructing practical deployments.In this thesis, I present several advancements in understanding the theoretical complexities of Consensus. For systems where processes can crash, I propose a new approach that improves communication complexity by a linear factor. When restricted to deterministic algorithms, I provide tight solutions as long as the number of failures is logarithmically smaller than the size of the system. Additionally, I characterize the trade-off between entropy and time complexity in Consensus solutions. For link failures, I present the first solution that is tight, up to polylogarithmic factors, in terms of time and communication complexity. Finally, I extend some of these techniques to distributed systems with quantum channels, achieving solutions with improved quantum communication complexity.