Renaming in an asynchronous environment

Reviewer: W. Richard Stark

The problem of reaching agreement in unreliable asynchronous distributed systems has been studied since about 1980 in papers such as Fischer et al. [1]. This paper develops asynchronous algorithms for renaming&#8212;a variation on consensus. Given n processors with old names p 1 2 <&ldots; n and new names 1, 2,&#8230;, N, the processors must compute unique new names 1r 1 2 &ldots; 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 do not specify the exact communications mechanism for computed messages&#8212;it could be broadcast, computed sets of names, or nearest neighbors&#8212;but they do not mention communications graphs and they state that no individual knows all the original names, so broadcast is a good candidate. For t the renaming problem can be solved by a distributed algorithm using N=2 t n-t+1 -1 new names. 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. The exposition is a disaster. Some sentences are unreadable, the paper contains excessive and unnecessary terminology, some important definitions are missing or badly placed, and inappropriate distinctions exist (such as between input and output values and between messages and states). An editors note indicates that the paper was returned for revision three times after the original submission. As in automata theory and recursion theory, a clear and powerful algebraic formalism is desirable. To achieve this, computability within individuals and communication between individuals should have been developed in a single unifying algebra.