### Renaming in an asynchronous environmentRenaming in an asynchronous environment

Access Restriction
Subscribed

 Author Attiya, Hagit ♦ Bar-Noy, Amotz ♦ Dolev, Danny ♦ Peleg, David ♦ Reischuk, Rdiger Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1990 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract This paper is concerned with the solvability of the problem of processor renaming in unreliable, completely asynchronous distributed systems. Fischer et al. prove in [8] that “nontrivial consensus” cannot be attained in such systems, even when only a single, benign processor failure is possible. In contrast, this paper shows that problems of processor renaming can be solved even in the presence of up to $\textit{t}$ < $\textit{n}/2$ faulty processors, contradicting the widely held belief that no nontrivial problem can be solved in such a system. The problems deal with renaming processors so as to reduce the size of the initial name space. When only uniqueness of the new names is required, we present a lower bound of $\textit{n}$ + 1 on the size of the new name space, and a renaming algorithm that establishes an upper bound on $\textit{n}$ + $\textit{t}.$ If the new names are required also to preserve the original order, a tight bound of $2′(\textit{n}$ - $\textit{t}$ + 1) - 1 is obtained. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1990-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 37 Issue Number 3 Page Count 25 Starting Page 524 Ending Page 548

#### Open content in new tab

Source: ACM Digital Library