Hagit Attiya
Amotz Bar-Noy
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.
- 1 ATTIYA, H., DOLEV, D., AND GIL, J. Asynchronous Byzantine consensus. In Proceedings of the 3rd ACM Symposium of Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 119-133. Google Scholar
- 2 BAR-NOY, A., DOLEV, D., KOLLER, D., AND PELEG, O. Fault-tolerant critical section management in asynchronous environments. In Distributed Algorithms, 3rd International Workshop (Nice, France, Sept.) Lecture Notes in Computer Science, No. 392. Springer-Verlag, New York, 1989, pp. 13-23. Inf. Comput., to appear. Google Scholar
- 3 BEN-OR, M. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the 2nd ACM Symposium of Principles of Distributed Computing (Montreal, Que., Canada, Aug. 17-19). ACM, New York, 1983, pp. 27-30. Google Scholar
- 4 BRACHA, G. An O(log n) expected rounds randomized Byzantine generals protocol. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, 1985, pp. 316-326. Google Scholar
- 5 BRIDGLAND, M. F., AND WATRO, R.J. Fault-tolerant decision making in totally asynchronous distributed systems. In Proceedings of the 6th ACM Symposium of Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 10-12). ACM, New York, 1987, pp. 52-63. Google Scholar
- 6 DOLEV, D., DWORK, C., AND STOCKMEYER, L. On the minimal synchronism needed for distributed consensus. J. ACM 34, l (Jan. 1987), 77-97. Google Scholar
- 7 DWORK, C., LYNCH, N., AND STOCKMEYER, L. Consensus in the presence of partial synchrony. J. ACM 35, 2 (Apr. 1988), 288-323. Google Scholar
- 8 FISCHER, M. J., LYNCH, N. A., AND PATERSON, M.S. Impossibility of distributed consensus with one faulty processor. J. ACM 32, 2 (Apr. 1985), 374-382. Google Scholar
- 9 KOLLER, D. Token survival: Resilient token algorithms. M.Sc. Thesis, Hebrew University, Jerusalem, Israel, 1986.Google Scholar
- 10 MORAN, S., AND WOLFSTAHL, Y. Extended impossibility results for asynchronous complete networks. Inf. Proc. Lett. 26 (Nov. 1987), 145-151. Google Scholar
- 11 RABIN, M.O. The choice coordination problem. Actalnf. 17(1982), 121-134.Google Scholar
- 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.Google Scholar
- 13 TAUBENFELD, G. Impossibility results for decision protocols. Tech. Rep. #445. Technion, Haifa, Israel, Jan. 1987.Google Scholar
Index Terms
- Renaming in an asynchronous environment
Recommendations
Virtual register renaming
ARCS'13: Proceedings of the 26th international conference on Architecture of Computing SystemsThis paper presents a novel high performance substrate for building energy-efficient out-of-order superscalar cores. The architecture does not require a reorder buffer or physical registers for register renaming and instruction retirement. Instead, it ...
Virtual register renaming: energy efficient substrate for continual flow pipelines
GLSVLSI '13: Proceedings of the 23rd ACM international conference on Great lakes symposium on VLSIContinual Flow Pipelines (CFP) allow a processor core to process instruction windows of hundreds of in-flight instructions while keeping its cycle critical scheduler and register file small. CFP defers the execution of instructions that depend on cache ...
On the Boosting of Instruction Scheduling by Renaming
Speculative execution is the execution of instructions before it is known whether these instructions should be executed. In the speculative execution for instruction level parallelism (ILP) processors, the concept of shadow register provides a hardware ...
Reviews
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—a variation on consensus. Given n processors with old names p 1 2 <&ldots; n and new names 1, 2,…, 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—it could be broadcast, computed sets of names, or nearest neighbors—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.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments