Michael Whittaker

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2021-172

August 5, 2021

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-172.pdf

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.

Advisors: Joseph M. Hellerstein

---

BibTeX citation:

@phdthesis{Whittaker:EECS-2021-172,
    Author= {Whittaker, Michael},
    Title= {Compartmentalizing State Machine Replication},
    School= {EECS Department, University of California, Berkeley},
    Year= {2021},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-172.html},
    Number= {UCB/EECS-2021-172},
    Abstract= {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.},
}

EndNote citation:

%0 Thesis
%A Whittaker, Michael 
%T Compartmentalizing State Machine Replication
%I EECS Department, University of California, Berkeley
%D 2021
%8 August 5
%@ UCB/EECS-2021-172
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-172.html
%F Whittaker:EECS-2021-172