Byzantine agreement with homonyms in synchronous systems - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2013

Byzantine agreement with homonyms in synchronous systems

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

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.

Dates and versions

hal-00922415 , version 1 (26-12-2013)

Identifiers

Cite

Carole Delporte-Gallet, Hugues Fauconnier, Hung Tran-The. Byzantine agreement with homonyms in synchronous systems. Theoretical Computer Science, 2013, 496, pp.34-49. ⟨10.1016/j.tcs.2012.11.012⟩. ⟨hal-00922415⟩
78 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More