PhD Defense: Resilient and Efficient Consensus under Unknown Network Conditions

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.

Examining Committee

Chair:

Dr. Jonathan Katz

Dean's Representative:

Dr. Dana Dachman-Soled

Members:

Dr. Dave Levin

Dr. Julian Loss (CISPA Helmholtz)

Dr. Ian Miers