Leader Set Selection for Low-Latency Geo-Replicated State Machine
Authors:
- 6 December 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 28 (7) , 1933-1946
Abstract
Modern planetary scale distributed systems largely rely on a State Machine Replication protocol to keep their service reliable, yet it comes with a specific challenge: latency, bounded by the speed of light. In particular, clients of a single-leader protocol, such as Paxos, must communicate with the leader which must in turn communicate with other replicas: inappropriate selection of a leader may result in unnecessary round-trips across the globe. To cope with this limitation, several all-leader and leaderless alternatives have been proposed recently. Unfortunately, none of them fits all circumstances. In this article we argue that the “right” choice of the number of leaders depends on a given replica configuration and the workload. Then we present ${\mathsf {Droopy}}$ and ${\mathsf {Dripple}}$ , two sister approaches built upon state machine replication protocols. ${\mathsf {Droopy}}$ dynamically reconfigures the set of leaders. Whereas, ${\mathsf {Dripple}}$ coordinates state partitions wisely, so that each partition can be reconfigured (by ${\mathsf {Droopy}}$ ) separately. Our experimental evaluation on Amazon EC2 shows that, ${\mathsf {Droopy}}$ and ${\mathsf {Dripple}}$ reduce latency under imbalanced or localized workloads, compared to their native protocol. When most requests are non-commutative, our approaches do not affect the performance of their native protocol and both outperform a state-of-the-art leaderless protocol.
Keywords
Funding Information
- EU H2020 (643964)
- Swiss Secretariat for Education, Research and Innovation (15.0025)
- National key research and development program (2016YFB1000101)
- China Scholarship Council
This publication has 21 references indexed in Scilit:
- ZooFence: Principled Service Partitioning and Application to the ZooKeeper Coordination Service2014
- Clock-RSM: Low-Latency Inter-datacenter State Machine Replication Using Loosely Synchronized Physical Clocks2014
- MDCC2013
- Paxos made live2007
- Fast PaxosDistributed Computing, 2006
- Generic Broadcast1999
- The part-time parliamentACM Transactions on Computer Systems, 1998
- Implementing fault-tolerant services using the state machine approach: a tutorialACM Computing Surveys, 1990
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985