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! identifiers, we define a distribution of the identifiers as an integer partition of n into l parts n(1,) .... ,n(l) 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! identifiers enabling to solve Byzantine agreement with at most t Byzantine processes if and only if n > 3t, l > t and l > (n-r)t/n-t-min(t,r) where r = n mod l. 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. (C) 2012 Elsevier B.V. All rights reserved.
