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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-00922415
Contributor : Carole Delporte-Gallet <>
Submitted on : Thursday, December 26, 2013 - 3:34:57 PM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

192