Loading [MathJax]/extensions/TeX/ieee_stixext.js
On Making Generalized Paxos Practical | IEEE Conference Publication | IEEE Xplore

Abstract:

Generalized Paxos (GPaxos) is a recent solution to Generalized Consensus, a distributed problem to which several key agreement problems reduce. We envision that GPaxos ma...Show More

Abstract:

Generalized Paxos (GPaxos) is a recent solution to Generalized Consensus, a distributed problem to which several key agreement problems reduce. We envision that GPaxos may unify within a single and novel Agreement-as-a-Service infrastructure multiple distributed protocols. To date this potential is however not fully unleashed, due to the steep learning curve of the protocol and the high complexity of its implementation. Moreover, before GPaxos reaches a real world usage, several computationally expensive operations have to be optimized and simplified. This paper aims at closing this gap between theory and practice. To this end, we first provide a concise tour of Generalized Paxos, hardly found elsewhere. Then, we assess the versatility of the Generalized Consensus problem by presenting a variation of GPaxos that solves the lease coordination problem. Our last contribution consists in three optimizations that apply to the critical phases of the algorithm: (i) a method to quickly start a new round, (ii) a novel approach to execute a checkpoint, and (iii) a data structure that speeds-up the detection of an agreement.
Date of Conference: 27-29 March 2017
Date Added to IEEE Xplore: 08 May 2017
ISBN Information:
Print ISSN: 1550-445X
Conference Location: Taipei, Taiwan
Faculdade de Computação, Universidade Federal de Uberlândia
Telecom SudParis, Departement d'informatique
Faculdade de Computação, Universidade Federal de Uberlândia
Hedvig Inc.
Faculdade de Computação, Universidade Federal de Uberlândia

I. Introduction

State machine replication (SMR) is a classical technique to implement a fault-tolerant service, by creating several copies of the service and ordering the client commands across replicas. Some recent works [1], [2] observe that replicas need to order only non-commuting commands, and thus that commuting commands may execute in two message delays, sidestepping the time complexity lower bound on consensus [3]. Lamport [2] names the task of agreeing on this partial order, the Generalized Consensus problem.

Faculdade de Computação, Universidade Federal de Uberlândia
Telecom SudParis, Departement d'informatique
Faculdade de Computação, Universidade Federal de Uberlândia
Hedvig Inc.
Faculdade de Computação, Universidade Federal de Uberlândia

References

References is not available for this document.