HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Synchronous Byzantine Lattice Agreement in O(log(f )) Rounds

Abstract : In the Lattice Agreement (LA) problem, originally proposed by Attiya et al. [1], a set of processes has to decide on a chain of a lattice. More precisely, each correct process proposes an element e of a certain join-semi lattice L and it has to decide on a value that contains e. Moreover, any pair pi, pj of correct processes has to decide two values deci and decj that are comparable (e.g., deci ≤ decj or decj < deci). In this paper we present new contributions for the synchronous case. We investigate the problem in the usual message passing model for a system of n processes with distinct unique IDs. We first prove that, when only authenticated channels are available, the problem cannot be solved if f = n/3 or more processes are Byzantine. We then propose a novel algorithm that works in a synchronous system model with signatures (i.e., the authenticated message model), tolerates up to f byzantine failures (where f < n/3) and that terminates in O(log f) rounds. We discuss how to remove authenticated messages at the price of algorithm resiliency (f < n/4). Finally, we present a transformer that converts any synchronous LA algorithm to an algorithm for synchronous Generalised Lattice Agreement.
Complete list of metadata

https://hal-cnrs.archives-ouvertes.fr/hal-02473843
Contributor : Emmanuelle Anceaume Connect in order to contact the contributor
Submitted on : Tuesday, February 11, 2020 - 8:29:31 AM
Last modification on : Monday, April 4, 2022 - 9:28:20 AM
Long-term archiving on: : Tuesday, May 12, 2020 - 12:32:05 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02473843, version 1

Citation

Giuseppe Di Luna, Emmanuelle Anceaume, Silvia Bonomi, Leonardo Querzoni. Synchronous Byzantine Lattice Agreement in O(log(f )) Rounds. ICDCS 2020 - 40th IEEE International Conference on Distributed Computing Systems, IEEE, Nov 2020, Singapore, Singapore. pp.1-11. ⟨hal-02473843⟩

Share

Metrics

Record views

145

Files downloads

117