  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>t^2+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 > 2t^2 + t$.
