Order-Preserving Renaming in Synchronous Systems with Byzantine Faults

Abstract—Renaming is a fundamental problem in distributed computing, which consists of a set of processes picking distinct names from a given namespace. The paper presents algorithms that solve order-preserving renaming in synchronous message passing systems with Byzantine processes. To the best of our knowledge, this work is the first to address order-preserving renaming in the given model. Although this problem can be solved by using consensus, it is known that renaming is “weaker ” than consensus, therefore we are mainly concerned with the efficiency of performing renaming and make three contributions in this direction. We present an order-preserving renaming algorithm for N> 3t with target namespace of size N+t−1 and logarithmic step complexity (where N is the number of processes and t is an upper bound on the number of faults). Similarly to the existing crash-tolerant solution, our algorithm employs the ideas from the approximate agreement problem. We show that our algorithm has constant step complexity if N> t2 + 2t and achieves tight namespace of size N. Finally, we present an algorithm that solves order-preserving renaming in just 2 communication steps, if N> 2t2 + t. I