UC Berkeley

State machine replication is at the heart of almost every strongly consistent distributed system. In this thesis, we introduce a novel technique called compartmentalization that involves decoupling a protocol into its simplest components and then scaling each component independently. Compartmentalization is simple yet effective. It can be used to increase the throughput of a protocol, to simplify an exiting protocol, or to design new functionality for a protocol. In this thesis specifically, we apply compartmentalization to state machine replication protocols in a number of different ways. We compartmentalize MultiPaxos and increase its throughput by over an order of magnitude. We then compartmentalize a family of complex state machine protocols called generalized multi-leader protocols. The compartmentalization simplifies the protocols and brings clarity to a family of protocols that were previously extremely difficult to understand. Finally, we use compartmentalization to design a new reconfiguration protocol based on Vertical Paxos that state machine replication protocols can use to replace failed machines with new machines without any downtime.