We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when faulty processors are able to cheat about their original identities, this problem cannot be solved in an a priori bounded number of rounds for t ≥ (n + n mod 3)/3, where n is the size of the network and t is the number of failures. This result also implies a t ≥ (n+n mod 4)/2 bound for the case of faulty processors that are not able to falsify their original identities. In addition, we present several Byzantine renaming algorithms based on distinct approaches, each providing a different tradeoff between its running time and the solution quality.
展开▼
机译：我们在具有拜占庭故障的完全连接的同步网络中研究了重命名问题。我们认为，当故障处理器能够欺骗其原始身份时，在T≥（n + n mod 3）/ 3的先验圆形圆数中不能解决这个问题，其中n是网络的大小和T是失败的数量。该结果也意味着T≥（n + n mod 4）/ 2绑定，用于故障处理器的情况，这些处理器无法伪造其原始身份。此外，我们基于不同的方法提供了几种拜占庭式重命名算法，每个算法在其运行时间和解决方案质量之间提供不同的权衡。
展开▼
