Renaming in Message Passing Systems with Byzantine Failures

摘要

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.