Byzantine agreement with homonyms in synchronous systems

Carole Delporte-Gallet 1, 2 Hugues Fauconnier 1, 2 Hung Tran-The 1, 2
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : We consider here the Byzantine agreement problem in synchronous systems with homonyms. In this model different processes may have the same authenticated identifier. In such a system of n processes sharing a set of l identifiers, we define a distribution of the identifiers as an integer partition of n into l parts n1,...,nl giving for each identifier i the number of processes having this identifier. Assuming that the processes know the distribution of identifiers we give a necessary and sufficient condition on the integer partition of n to solve the Byzantine agreement with at most t Byzantine processes. Moreover we prove that there exists a distribution of l identifiers enabling to solve Byzantine agreement with at most t Byzantine processes if and only if n>3t, l>t and View the MathML source where r=nmodl. This bound is to be compared with the l>3t bound proved in Delporte-Gallet et al. (2011) [4] when the processes do not know the distribution of identifiers.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, 496, pp.34-49. 〈10.1016/j.tcs.2012.11.012〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00922415
Contributeur : Carole Delporte-Gallet <>
Soumis le : jeudi 26 décembre 2013 - 15:34:57
Dernière modification le : mardi 17 avril 2018 - 11:48:04

Lien texte intégral

Identifiants

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Hung Tran-The. Byzantine agreement with homonyms in synchronous systems. Theoretical Computer Science, Elsevier, 2013, 496, pp.34-49. 〈10.1016/j.tcs.2012.11.012〉. 〈hal-00922415〉

Partager

Métriques

Consultations de la notice

131