Access Restriction

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

   Open content in new tab
Source: ACM Digital Library