Byzantine agreement with homonyms in synchronous systems

作者：Delporte Gallet Carole^*; Fauconnier Hugues; Hung Tran The

来源：Theoretical Computer Science, 2013, 496: 34-49.

DOI：10.1016/j.tcs.2012.11.012

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. %26lt;br%26gt;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 %26gt; 3t, l %26gt; t and l %26gt; (n-r)t/n-t-min(t,r) where r = n mod l. %26lt;br%26gt;This bound is to be compared with the l %26gt; 3t bound proved in Delporte-Gallet et al. (2011) [4] when the processes do not know the distribution of identifiers.

• 出版日期2013-7-22