Synchronous Byzantine Lattice Agreement in O(log(f )) Rounds - Archive ouverte HAL Access content directly
Conference Papers Year : 2020

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

(1) , (2) , (1) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
main.pdf (1.91 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02473843 , version 1 (11-02-2020)

Identifiers

  • HAL Id : hal-02473843 , version 1

Cite

Giuseppe Antonio 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⟩
147 View
127 Download

Share

Gmail Facebook Twitter LinkedIn More