PhD Proposal: Resilience and Efficiency of Consensus in Arbitrary Network Conditions

A key challenge in distributed systems is ensuring agreement between many devices, even if some fraction of those devices may be faulty. This type of problem is known as a consensus problem. One of the most fundamental consensus problems is Byzantine agreement (BA). In the Byzantine agreement problem, honest (non-faulty) parties must agree on a shared output in the presence of Byzantine (faulty) parties, who may behave arbitrarily. Over the years, techniques for solving this conceptually simple problem have become the basis for a wide variety of Byzantine fault tolerant (BFT) protocols and systems. Recently, growing interest in blockchains has sparked renewed interest in BFT protocols, as techniques from BFT literature have proved to be useful for blockchain (and vice versa).Consensus problems have frequently been studied in the context of two contrasting network models. In the synchronous network model, any message sent by an honest party will be delivered within time delta, where delta is a fixed parameter known to all parties. In the asynchronous network model, messages may be delayed for arbitrary lengths of time. It is often possible to tolerate strictly more faults in the synchronous model than the asynchronous model. For example, assuming a public key infrastructure (PKI), the optimal fault tolerance for an n-party BA protocol in the synchronous model is t < n/2, compared to only t < n/3 in the asynchronous model. This raises the question of whether it is possible to design consensus protocols that are network-agnostic, i.e., that tolerate ts ≥ n/3 faults when run in a synchronous network while still tolerating ta < n/3 faults when run in an asynchronous network. In this work, I present the first network-agnostic protocols for Byzantine agreement and other consensus primitives, and show that they achieve the optimal tradeoff between ts and ta.I will also discuss my proposed work, which will focus on improving performance of consensus protocols for problems like atomic broadcast and state machine replication (SMR). In these problems, the goal is to agree on not just one value, but on a growing sequence of values. Key performance metrics include latency (how long it takes to agree on a new value once it is input), throughput (the rate at which new values are agreed upon), and amortized communication complexity (total bits of communication per value agreed upon). I will discuss challenges and techniques related to designing consensus protocols with high throughput, low latency, and low amortized communication complexity.Examining Committee:

Chair:Department Representative:Members:

Dr. Jonathan Katz Dr. Ian Miers Dr. Julian LossDr. Dana Dachman-Soled