BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-86-1131
       ENTRY:: May 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Processor Renaming in Asynchronous Environments
        TYPE:: Technical Report
      AUTHOR:: Bar-Noy, Amotz
      AUTHOR:: Peleg, David
        DATE:: September 1986
       PAGES:: 16
    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.
       NOTES:: [Adminitrivia V1/Prg/19950501]
         END:: STAN//CS-TR-86-1131