PhD Defense: Resilient and Efficient Consensus under Unknown Network Conditions
Erica Blum
Wednesday, May 10, 2023, 10:00 am-12:00 pm 
Abstract
Large-scale distributed systems need to provide high throughput and low latency without sacrificing resilience. In particular, even if some devices crash or malfunction, the system as a whole should remain consistent. This motivates the study of consensus algorithms, broadly defined as interactive protocols for reaching agreement in the presence of faulty devices.
How effectively a consensus problem can be solved (or whether it is solvable at all) depends on a variety of factors (e.g., presumed availability of cryptographic tools, reliability of the underlying communication network). For example, assuming standard cryptographic tools, there is a well-known separation for the fundamental problem of Byzantine agreement (BA): if messages are guaranteed to arrive within a fixed, known time, then BA is feasible as long as fewer than half of the devices are faulty. Conversely, if messages can arrive after unbounded time, BA is only feasible for fewer than one-third faults. These two models are known as the synchronous and asynchronous models, respectively.
In this talk, I will define a novel network-agnostic notion of security, and present a suite of new consensus protocols that achieve precisely defined security guarantees in both the synchronous and asynchronous network models, even when the parties are unaware of the status of the network. I will also highlight matching impossibility results, showing that these protocols achieve the best-possible fault thresholds for this setting. Finally, I will discuss recent results extending this model, and give a preview of future directions.
How effectively a consensus problem can be solved (or whether it is solvable at all) depends on a variety of factors (e.g., presumed availability of cryptographic tools, reliability of the underlying communication network). For example, assuming standard cryptographic tools, there is a well-known separation for the fundamental problem of Byzantine agreement (BA): if messages are guaranteed to arrive within a fixed, known time, then BA is feasible as long as fewer than half of the devices are faulty. Conversely, if messages can arrive after unbounded time, BA is only feasible for fewer than one-third faults. These two models are known as the synchronous and asynchronous models, respectively.
In this talk, I will define a novel network-agnostic notion of security, and present a suite of new consensus protocols that achieve precisely defined security guarantees in both the synchronous and asynchronous network models, even when the parties are unaware of the status of the network. I will also highlight matching impossibility results, showing that these protocols achieve the best-possible fault thresholds for this setting. Finally, I will discuss recent results extending this model, and give a preview of future directions.
Examining Committee
Bio
Erica Blum is a 5th year PhD candidate in the Computer Science department at University of Maryland College Park, advised by Jonathan Katz. Her research is at the intersection of cryptography and distributed computing, focusing on the security of consensus protocols under different adversarial models and network conditions. While at UMD, Erica has been the recipient of a Dean's Fellowship and the 2019 DFINITY Scholarship, and has been recognized as an Honorable Mention/Finalist for NSF GRFP, Facebook PhD Fellowship, and others.
This talk is organized by Tom Hurst