Renaming in synchronous message passing systems with Byzantine failures

摘要

We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original namespace of the processors is unbounded, 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. On the other hand, for n > 3t, we present a Byzantine renaming algorithm that runs in O (lg n) rounds. In addition, we present a fast, efficient strong renaming algorithm for n > t, which runs in O (n lg~2 [N_0]) rounds, where N_0 is the value of the highest identifier among all the correct processors.