Processor Renaming in Asynchronous Environments

[摘要] Fischer, Lynch and Paterson proved that in a completely asynchronous system "weak agreement" cannot be achieved even in the presence of a single "benign" fault. Following the direction proposed in Attiya, Bar-Noy, Dolev and Koller (Aug 1986), we demonstrate the interesting fact that some weaker forms of processor cooperation are still achievable in such a situation, and in fact, even in the presence of up to t < n/2 such faulty processors. In particular, we show that n processors, each having a distinct name taken from an unbounded ordered domain, can individually choose new distinct names from a space of size n + t (where n is an obvious lower bound). In case the new names are required also to preserve the original order, we give an algorithm in which the space of new names is of size ${2^t}(n - t + 1) - 1$, which is tight.

[学科分类] 计算机科学（综合）