Renaming in an asynchronous environment Export

@article{citeulike:4035123, 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 t \< 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 n + 1 on the size of the new name space, and a renaming algorithm that establishes an upper bound on n + t . If the new names are required also to preserve the original order, a tight bound of 2\′( n - t + 1) - 1 is obtained.}, address = {New York, NY, USA}, author = {Attiya, Hagit and Noy, Amotz B. and Dolev, Danny and Peleg, David and Reischuk, R\"udiger}, citeulike-article-id = {4035123}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=79158}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/79147.79158}, doi = {10.1145/79147.79158}, issn = {0004-5411}, journal = {J. ACM}, keywords = {1990, asynchronous, renaming}, number = {3}, pages = {524--548}, posted-at = {2009-02-11 13:19:38}, priority = {2}, publisher = {ACM}, title = {Renaming in an asynchronous environment}, url = {http://dx.doi.org/10.1145/79147.79158}, volume = {37}, year = {1990} }

TY - JOUR ID - citeulike:4035123 L3 - citeulike-article-id:4035123 N2 - 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 t < 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 n + 1 on the size of the new name space, and a renaming algorithm that establishes an upper bound on n + t . If the new names are required also to preserve the original order, a tight bound of 2′( n - t + 1) - 1 is obtained. IS - 3 JF - J. ACM SN - 0004-5411 AD - New York, NY, USA EP - 548 TI - Renaming in an asynchronous environment PB - ACM VL - 37 SP - 524 KW - 1990 KW - asynchronous KW - renaming AU - Attiya, Hagit AU - Noy, Amotz AU - Dolev, Danny AU - Peleg, David AU - Reischuk, R\"udiger PY - 1990/// UR - http://dx.doi.org/10.1145/79147.79158 ER -