License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.29
URN: urn:nbn:de:0030-drops-118158
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11815/
Zheng, Xiong ;
Garg, Vijay K. ;
Kaippallimalil, John
Linearizable Replicated State Machines With Lattice Agreement
Abstract
This paper studies the lattice agreement problem in asynchronous systems and explores its application to building a linearizable replicated state machine (RSM). First, we propose an algorithm to solve the lattice agreement problem in O(log f) asynchronous rounds, where f is the number of crash failures that the system can tolerate. This is an exponential improvement over the previous best upper bound of O(f). Second, Faleiro et al have shown in [Faleiro et al. PODC, 2012] that combination of conflict-free data types and lattice agreement protocols can be applied to implement a linearizable RSM. They give a Paxos style lattice agreement protocol, which can be adapted to implement a linearizable RSM and guarantee that a command by a client can be learned in at most O(n) message delays, where n is the number of proposers. Later, Xiong et al in [Xiong et al. DISC, 2018] gave a lattice agreement protocol which improves the O(n) message delay guarantee to O(f). However, neither of the protocols is practical for building a linearizable RSM. Thus, in the second part of the paper, we first give an improved protocol based on the one proposed by Xiong et al. Then, we implement a simple linearizable RSM using our improved protocol and compare our implementation with an open source Java implementation of Paxos. Results show that better performance can be obtained by using lattice agreement based protocols to implement a linearizable RSM compared to traditional consensus based protocols.
BibTeX - Entry
@InProceedings{zheng_et_al:LIPIcs:2020:11815,
author = {Xiong Zheng and Vijay K. Garg and John Kaippallimalil},
title = {{Linearizable Replicated State Machines With Lattice Agreement}},
booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
pages = {29:1--29:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-133-7},
ISSN = {1868-8969},
year = {2020},
volume = {153},
editor = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11815},
URN = {urn:nbn:de:0030-drops-118158},
doi = {10.4230/LIPIcs.OPODIS.2019.29},
annote = {Keywords: Lattice Agreement, Generalized Lattice Agreement, Replicated State Machine, Consensus}
}
|
Keywords: |
|
Lattice Agreement, Generalized Lattice Agreement, Replicated State Machine, Consensus |
|
Collection: |
|
23rd International Conference on Principles of Distributed Systems (OPODIS 2019) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.02.2020 |
