N N that preserve the original order on names. Assuming that this system has evolved to a state in which the original name assignment is inefficient or inappropriate, the goal is to rename the processors using as small an N as possible. Computations must be defined by an asynchronous distributed algorithm without global knowledge. The problem is complicated by allowing at most t of the processors to be nonfunctional. Messages are sent to destinations and stored in an unordered buffer.
Individual activity consists of simultaneous state change and message generation.
Individuals have potentially infinite memory. The authors also give noncomputability results. Investigations of models of asynchronous distributed computations, and especially of the limits of global computability, are among the most exciting areas of current research. This paper addresses many important issues and should have become a useful addition to the literature. Unfortunately, it may be most useful to technical writing classes.