Abstract
This paper studies the lattice agreement problem and the generalized lattice agreement problem in distributed message passing systems. In the lattice agreement problem, given input values from a lattice, processes have to nontrivially decide output values that lie on a chain. We consider the lattice agreement problem in both synchronous and asynchronous systems. For synchronous lattice agreement, we present two algorithms which run in log(f) and min{O(log^2 h(L)), O(log^2 f)} rounds, respectively, where h(L) denotes the height of the input sublattice L, f < n is the number of crash failures the system can tolerate, and n is the number of processes in the system. These algorithms have significant better round complexity than previously known algorithms. The algorithm by Attiya et al. [Attiya et al. DISC, 1995] takes log(n) synchronous rounds, and the algorithm by Mavronicolasa [Mavronicolasa, 2018] takes min{O(h(L)), O(sqrt(f))} rounds. For asynchronous lattice agreement, we propose an algorithm which has time complexity of 2*min{h(L), f + 1} message delays which improves on the previously known time complexity of O(n) message delays.
The generalized lattice agreement problem defined by Faleiro et al in [Faleiro et al. PODC, 2012] is a generalization of the lattice agreement problem where it is applied for the replicated state machine. We propose an algorithm which guarantees liveness when a majority of the processes are correct in asynchronous systems. Our algorithm requires min{O(h(L)), O(f)} units of time in the worst case which is better than O(n) units of time required by the algorithm in [Faleiro et al. PODC, 2012].
BibTeX  Entry
@InProceedings{zheng_et_al:LIPIcs:2018:9830,
author = {Xiong Zheng and Changyong Hu and Vijay K. Garg},
title = {{Lattice Agreement in Message Passing Systems}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {41:141:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770927},
ISSN = {18688969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9830},
URN = {urn:nbn:de:0030drops98301},
doi = {10.4230/LIPIcs.DISC.2018.41},
annote = {Keywords: Lattice Agreement, Replicated State Machine, Consensus}
}
Keywords: 

Lattice Agreement, Replicated State Machine, Consensus 
Seminar: 

32nd International Symposium on Distributed Computing (DISC 2018) 
Issue Date: 

2018 
Date of publication: 

28.09.2018 