Ecole d'ingénieur et centre de recherche en Sciences du numérique

Leader set selection for low-latency geo-replicated state machine

Liu, Shengyun; Vukolic, Marko

IEEE Transactions on Parallel and Distributed Systems, Vol. 28, N°7, July 2017

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: wrong selection of a leader may result in unnecessary round-trips across the globe. To cope with this limitation, several all-leader and leaderless geo-replication 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 Droopy and Dripple, two sister approaches built upon state machine replication protocols. Droopy dynamically reconfigures the set of leaders. Whereas, Dripple divides the system state into partitions and coordinates them wisely, so that each partition can be reconfigured separately. Our experimental evaluation on Amazon EC2 shows that, Droopy and 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.

Document Doi Bibtex

Titre:Leader set selection for low-latency geo-replicated state machine
Mots Clés:State machine replication, geo-replication, latency optimization, state-partitioning
Type:Journal
Langue:English
Ville:
Date:
Département:Sécurité numérique
Eurecom ref:5087
Copyright: © 2016 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @article{EURECOM+5087, doi = {http://dx.doi.org/10.1109/TPDS.2016.2636148}, year = {2016}, month = {12}, title = {{L}eader set selection for low-latency geo-replicated state machine}, author = {{L}iu, {S}hengyun and {V}ukolic, {M}arko}, journal = {{IEEE} {T}ransactions on {P}arallel and {D}istributed {S}ystems, {V}ol. 28, {N}°7, {J}uly 2017}, url = {http://www.eurecom.fr/publication/5087} }
Voir aussi: