Report Number: CS-TR-86-1131
Institution: Stanford University, Department of Computer Science
Title: Processor Renaming in Asynchronous Environments
Author: Bar-Noy, Amotz
Author: Peleg, David
Date: September 1986
Abstract: Fischer, Lynch and Paterson proved that in a completely asynchronous system "weak agreement" cannot be achieved even in the presence of a single "benign" fault. Following the direction proposed in Attiya, Bar-Noy, Dolev and Koller (Aug 1986), we demonstrate the interesting fact that some weaker forms of processor cooperation are still achievable in such a situation, and in fact, even in the presence of up to t < n/2 such faulty processors. In particular, we show that n processors, each having a distinct name taken from an unbounded ordered domain, can individually choose new distinct names from a space of size n + t (where n is an obvious lower bound). In case the new names are required also to preserve the original order, we give an algorithm in which the space of new names is of size ${2^t}(n - t + 1) - 1$, which is tight.
http://i.stanford.edu/pub/cstr/reports/cs/tr/86/1131/CS-TR-86-1131.pdf