https://umd.zoom.us/j/
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.
Our main result is a new randomized algorithm for the Consensus problem that narrows this communication gap by a linear factor and preserves the optimal time complexity. Additionally, we establish a trade-off between communication and time complexities, allowing flexibility in optimizing either parameter. This gives the first improvement in the front of communication-efficient Consensus protocols in over 20 years.
Jan Olkowski is a third-year Ph.D. student whose research interest splits between fault-tolerant distributed computing and mechanism design. In the area of distributed computing, Jan's research addresses the currently critical question of latency and bandwidth of Consensus protocols. Consensus, a basic tool for agreement between dispersed and dislocated parties, is fundamental for applications like databases, cloud computing, and more recently, cryptocurrencies. In his work, he investigates how tools from spectral graph theory, enhanced with a fault-tolerant design, can be used toward more scalable distributed systems.