Automatic Compartmentalization of Distributed Protocols

Distributed protocols, like Paxos and PBFT, were not designed to scale. This limitation has led to the creation of countless new distributed protocols; unfortunately, many have not passed the test of time and contain subtle bugs. This approach— “if I see a slow protocol, I will think really hard about it and make it faster”— is also deeply unsatisfying; each new protocol starts from scratch and presents a new “trick” that is supposedly general but only applies to the protocol at hand. Let’s stop writing new distributed protocols, put together all the tricks we’ve learned throughout the years, and figure out when and why they work.

We have written down the explicit assumptions of many such tricks—mainly decoupling (vertical parallelism) and partitioning (horizontal parallelism)—proven them correct, and demonstrated that they can be systematically applied to rewrite any distributed protocol to 2x-5x their performance. Our group at Berkeley (Hydro) aims to turn this into an optimizer for distributed systems, eliminating the middleman who determines where to best apply the tricks.


David Chu, Shadaj Laddad, Chris Liu, Rithvik Panchapakesan, Natacha Crooks, Joe Hellerstein, Heidi Howard