In this paper we present the Multidimensional Byzantine Agreement (MBA) Protocol, a leaderless Byzantine agreement protocol defined for complete and synchronous networks that allows a network of nodes to reach consensus on a vector of relevant information regarding a set of observed events. The consensus process is carried out in parallel on each component, and the output is a vector whose components are either values with wide agreement in the network (even if no individual node agrees on every value) or a special value perpendicular to that signals irreconcilable disagreement. The MBA Protocol is probabilistic and its execution halts with probability 1, and the number of steps necessary to halt follows a Bernoulli-like distribution. The design combines a Multidimensional Graded Consensus and a Multidimensional Binary Byzantine Agreement, the generalization to the multidimensional case of two protocols presented by Micali et al. (SIAM J Comput 26(4):873-933, 1997; Byzantine agreement, made trivial, 2016). We prove the correctness and security of the protocol assuming a synchronous network where less than a third of the nodes are malicious.

Multidimensional Byzantine agreement in a synchronous setting / Flamini, Andrea; Longo, Riccardo; Meneghetti, Alessio. - In: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING. - ISSN 0938-1279. - 2022:(2022), pp. 1-19. [10.1007/s00200-022-00548-5]

Multidimensional Byzantine agreement in a synchronous setting

Andrea Flamini
;
Riccardo Longo;Alessio Meneghetti
2022-01-01

Abstract

In this paper we present the Multidimensional Byzantine Agreement (MBA) Protocol, a leaderless Byzantine agreement protocol defined for complete and synchronous networks that allows a network of nodes to reach consensus on a vector of relevant information regarding a set of observed events. The consensus process is carried out in parallel on each component, and the output is a vector whose components are either values with wide agreement in the network (even if no individual node agrees on every value) or a special value perpendicular to that signals irreconcilable disagreement. The MBA Protocol is probabilistic and its execution halts with probability 1, and the number of steps necessary to halt follows a Bernoulli-like distribution. The design combines a Multidimensional Graded Consensus and a Multidimensional Binary Byzantine Agreement, the generalization to the multidimensional case of two protocols presented by Micali et al. (SIAM J Comput 26(4):873-933, 1997; Byzantine agreement, made trivial, 2016). We prove the correctness and security of the protocol assuming a synchronous network where less than a third of the nodes are malicious.
2022
Flamini, Andrea; Longo, Riccardo; Meneghetti, Alessio
Multidimensional Byzantine agreement in a synchronous setting / Flamini, Andrea; Longo, Riccardo; Meneghetti, Alessio. - In: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING. - ISSN 0938-1279. - 2022:(2022), pp. 1-19. [10.1007/s00200-022-00548-5]
File in questo prodotto:
File Dimensione Formato  
s00200-022-00548-5.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Creative commons
Dimensione 1.65 MB
Formato Adobe PDF
1.65 MB Adobe PDF Visualizza/Apri

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/11572/378889
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact