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.

Synchronous byzantine lattice agreement in O(log(f)) rounds / Di Luna, G. A.; Anceaume, E.; Bonomi, S.; Querzoni, L.. - (2020), pp. 146-156. (Intervento presentato al convegno International Conference on Distributed Computing Systems tenutosi a online) [10.1109/ICDCS47774.2020.00056].

Synchronous byzantine lattice agreement in O(log(f)) rounds

Di Luna G. A.
;
Bonomi S.
;
Querzoni L.
2020

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.
2020
International Conference on Distributed Computing Systems
Byzantine fault tolerance; lattice agreement
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Synchronous byzantine lattice agreement in O(log(f)) rounds / Di Luna, G. A.; Anceaume, E.; Bonomi, S.; Querzoni, L.. - (2020), pp. 146-156. (Intervento presentato al convegno International Conference on Distributed Computing Systems tenutosi a online) [10.1109/ICDCS47774.2020.00056].
File allegati a questo prodotto
File Dimensione Formato  
DiLuna_Synchronous_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 922.46 kB
Formato Adobe PDF
922.46 kB Adobe PDF   Contatta l'autore
DiLuna_preprint_Synchronous_2020.pdf

accesso aperto

Note: https://ieeexplore.ieee.org/document/9355713
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.95 MB
Formato Adobe PDF
2.95 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1525704
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact