log in  |  register  |  feedback?  |  help  |  web accessibility
PhD Defense: Towards scalability and efficiency in distributed systems
Jan Olkowski
Tuesday, December 17, 2024, 3:00-5:00 pm
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

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.

Bio

Jan Olkowski is a 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.

This talk is organized by Migo Gui