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)/n]) rounds, where N(0) is the value of the highest identifier among all the correct processors.
byzantine failures renaming problem synchronous message passing model