Byzantine renaming in synchronous systems with t < N
Oksana Denysyuk, Luı́s Rodrigues · 2013
In this paper we consider the fundamental problems of renaming and order-preserving renaming [1] in a synchronous message passing system with Byzantine failures. We study the feasibility of solving these problems using randomized algorithms under both non-rushing and rushing adversaries. We first show that there is a randomized algorithm that solves renaming efficiently for any t < N under the non-rushing adversary (N is the number of processes, and t is the maximum number of Byzantine processes). This result establishes a separation between randomized and deterministic renaming, since it is known that there are no efficient deterministic algorithms for t≥N/3. Our algorithm terminates in O(log N) rounds w.h.p. We next consider the renaming problem in the harder setting with the rushing adversary. Interestingly, we show that in this setting the algorithm also works with t = 1 but fails for larger t. We then give an algorithm that works with any t < N by relying on cryptographic commitment. Finally, we turn our attention to the problem of order-preserving renaming, which requires the new names to preserve the order of the initial identifiers. For this problem, we prove a tight t < N/3 bound that holds for both deterministic and randomized algorithms.