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