Strong order-preserving renaming in the synchronous message passing model

In [14] Chaudhuri et al. (1999) presented a strong, wait-free renaming algorithm for a synchronous message passing system with crash failures, which runs in an optimal O(logn) time, where n is the number of initially participating processors. Here, we extend their work by presenting a renaming algorithm which has similar characteristics and in addition is order-preserving. The new algorithm is based on an approximate agreement protocol.