Tushar Deepak Chandra
Abstract
We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In Chandra and Toueg [1996], it is shown that W, a failure detector that provides surprisingly little information about which processes have crashed, is sufficient to solve Consensus in asynchronous systems with a majority of correct processes. In this paper, we prove that to solve Consensus, any failure detector has to provide at least as much information as W. Thus, W is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.
- ATTIYA, H., BAR-NOY, A., DOLEV, D., KOLLER, D., PELEG, D., AND REISCHUK R. 1987. Achievable cases in an asynchronous environment. In Proceedings of the 28th Symposium on Foundations of Computer Science. IEEE Computer Society Press, New York, pp. 337-346.Google Scholar
- BIRAN, O., MORAN, S., AND ZAKS, S. 1988. A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (Toronto, Ont., Canada, Aug. 15-17). ACM, New York, pp. 263-275. Google Scholar
- BRIDGLAND,M.F.,AND WATRO, R. J. 1987. Fault-tolerant decision making in totally asynchronous distributed systems. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 10-12). ACM, New York, pp. 52-63. Google Scholar
- CHANDRA,T.D.,AND TOUEG, S. 1996. Unreliable failure detectors for reliable distributal systems. J. ACM 43, 2 (Mar.), 225-267. Google Scholar
- CHOR, B., AND DWORK, C. 1989. Randomization in byzantine agreement. Adv. Comput. Res. 5, 443-497.Google Scholar
- DOLEV, D., DWORK, D., AND STOCKMEYER, L. 1987. On the minimal synchronism needed for distributed consensus. J. ACM 34, 1 (Jan.), 77-97. Google Scholar
- DOLEV, D., LYNCH,N.A.,PINTER,S.S.,STARK,E.W.,AND WEIHL, W. E. 1986. Reaching approximate agreement in the presence of faults. J. ACM 33, 3 (July), 499-516. Google Scholar
- DWORK, C., LYNCH,N.A.,AND STOCKMEYER, L. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2 (Apr.), 288-323. Google Scholar
- FISCHER,M.J.,LYNCH,N.A.,AND PATERSON, M. S. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (Apr.), 374-382. Google Scholar
- RICCIARDI,A.M.,AND BIRMAN, K. P. 1991. Using process groups to implement failure detection in asynchronous environments. In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing (Montreal, Que., Canada, Aug. 19-21). ACM, New York, pp. 341-351. Google Scholar
Index Terms
- The weakest failure detector for solving consensus
Recommendations
Unreliable failure detectors for reliable distributed systems
We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties—completeness and accuracy. We ...
Failure Detection and Randomization: A Hybrid Approach to Solve Consensus
We present a consensus algorithm that combines unreliable failure detection and randomization, two well-known techniques for solving consensus in asynchronous systems with crash failures. This hybrid algorithm combines advantages from both approaches:...
On Quiescent Reliable Communication
We study the problem of achieving reliable communication with quiescent algorithms (i.e., algorithms that eventually stop sending messages) in asynchronous systems with process crashes and lossy links. We first show that it is impossible to solve this ...
Comments