Abstract | ||
---|---|---|
Implementations of state machine replication are prevalently using variants of Paxos or other leader-based protocols. Typically these protocols are also leader-centric, in the sense that the leader performs more work than the non-leader replicas. Such protocols scale poorly, because as the number of replicas or the load on the system increases, the leader replica quickly reaches the limits of one of its resources. In this paper we show that much of the work performed by the leader in a leader-centric protocol can in fact be evenly distributed among all the replicas, thereby leaving the leader only with minimal additional workload. This is done (i) by distributing the work of handling client communication among all replicas, (ii) by disseminating client requests among replicas in a distributed fashion, and (iii) by executing the ordering protocol on ids. We derive a variant of Paxos incorporating these ideas. Compared to leader-centric protocols, our protocol not only achieves significantly higher throughput for any given number of replicas, but also increases its throughput with the number of replicas. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/SRDS.2012.66 | Reliable Distributed Systems |
Keywords | Field | DocType |
client-server systems,fault tolerant computing,finite state machines,multi-threading,protocols,replicated databases,S-Paxos,client communication,client request dissemination,high-throughput state machine replication,leader replicas,leader-centric protocols,nonleader replicas,ordering protocol execution,work distribution,High Throughput,Paxos,Performance,Scalability,State Machine Replication | Replica,Multithreading,State machine replication,Computer science,Computer network,Real-time computing,Finite-state machine,Dissemination,Throughput,Paxos,Distributed computing,Scalability | Conference |
ISSN | ISBN | Citations |
1060-9857 | 978-1-4673-2397-0 | 25 |
PageRank | References | Authors |
1.00 | 22 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Biely | 1 | 25 | 1.00 |
Zarko Milosevic | 2 | 25 | 1.00 |
Nuno Santos | 3 | 189 | 24.08 |
André Schiper | 4 | 40 | 2.63 |