Renaming in an asynchronous environment

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.

REFERENCES

• 1: Chagit Attiya , Danny Dolev , Joseph Gil, Asynchronous Byzantine consensus, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.119-133, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806740]
• 2: Amotz Bar-Noy , Danny Dolev , Daphne Koller , David Peleg, Fault-Tolerant Critical Section Management in Asynchronous Networks, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.13-23, September 26-28, 1989
• 3: Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
• 4: G Bracha, An O(lg n) expected rounds randomized Byzantine generals protocol, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.316-326, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22180]
• 5: Michael F. Bridgland , Ronald J. Watro, Fault-tolerant decision making in totally asynchronous distributed systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.52-63, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41845]
• 6: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 7: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 8: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 9: KOLLER, D. Token survival: Resilient token algorithms. M.Sc. Thesis, Hebrew University, Jerusalem, Israel, 1986.
• 10: S. Moran , Y. Wolfstahl, Extended impossibility results for asynchronous complete networks, Information Processing Letters, v.26 n.3, p.145-151, Nov. 23, 1987 [doi>10.1016/0020-0190(87)90052-4]
• 11: RABIN, M.O. The choice coordination problem. Actalnf. 17(1982), 121-134.
• 12: RABIN, M. O. Randomized Byzantine generals. In Proceedings of the 24th Symposium of Foundations of Computer Science (Nov.). IEEE, New York, 1983, pp. 403-409.
• 13: TAUBENFELD, G. Impossibility results for decision protocols. Tech. Rep. #445. Technion, Haifa, Israel, Jan. 1987.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Theory