Renaming in an asynchronous environment

Publisher Website
Google Scholar
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 tot<n/2 faulty processors, contradicting the widely held belief that no nontrivial problem can be solved in such a system. The problems deal withrenaming processorsso as to reduce the size of the initial name space. When only uniqueness of the new names is required, we present a lower bound ofn+ 1 on the size of the new name space, and a renaming algorithm that establishes an upper bound onn+t. If the new names are required also to preserve the original order, a tight bound of 2′(n-t+ 1) - 1 is obtained.

This publication has 6 references indexed in Scilit: