Abstract
The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound Δ on the time required for a message to be sent from one processor to another and a known fixed upper bound Φ on the relative speeds of different processors. In an asynchronous system no fixed upper bounds Δ and Φ exist. In one version of partial synchrony, fixed bounds Δ and Φ exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds Δ and Φ. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T, and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.
- 1 ATTIYA, A., DOLEV, D., AND GIL, J. Asynchronous Byzantine consensus. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 119-133. Google Scholar
- 2 BRACHA, G., AND TOUEG, S. Asynchronous consensus and broadcast protocols. J. ACM 32, 4 (Oct. 1985), 824-840. Google Scholar
- 3 DOLEV, D., AND STRONG, H. R. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12 (1983), 656-666.Google Scholar
- 4 DOLEV, D., DWORK, C., AND STOCKMEYER, L. On the minimal synchronism needed for distributed consensus, d. ACM 34, 1 (Jan. 1987), 77-97. Google Scholar
- 5 DOLEV, D., FISCHER, i. J., FOWLER, R., LYNCH, N. A., AND STRONG, H.R. Efficient Byzantine agreement without authentication. Inf. Control 52 (1982), 257-274.Google Scholar
- 6 DOLEV, D., LYNCH, N. A., PINTER, S. S., STARK, E. W., AND WEIHL, W.E. Reaching approximate agreement in the presence of faults. J. ACM 33, 3 (July 1986), 499-516. Google Scholar
- 7 DWORK, C., AND MOSES, Y. Knowledge and common knowledge in a Byzantine environment I: Crash failures. In Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning about Knowledge (Monterey, Calif., Mar. 19-22). Kaufmann, Los Altos, Calif., 1986, pp. 149-169. Google Scholar
- 8 FISCHER, M.J. The consensus problem in unreliable distributed systems (a brief survey). Rep. YALEU/DSC/RR-273. Dept. of Computer Science, Yale Univ., New Haven, Conn., June 1983.Google Scholar
- 9 FISCHER, M. J., AND LAMPORT, L. Byzantine generals and transaction commit protocols. Tech. Rep. Op. 62, SRI International, Menlo Park, Calif., 1982.Google Scholar
- 10 FISCHER, i. J., LYNCH, N. A., AND PATERSON, M.S. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (Apr. 1985), 374-382. Google Scholar
- 11 GARCIA-MOLINA, H., PITI"ELLI, F., AND DAVIOSON, S. Is Byzantine agreement useful in a distributed database? In Proceedings of the 3rd SIGACT-SIGMOD Symposium on Principles of Database Systems (Waterloo, Ont., Canada, Apr. 2-4). ACM, New York, 1984, pp. 61-69. Google Scholar
- 12 GRAY, J. N. Notes on database operating systems. In Operating Systems: An Advanced Course. Lecture Notes in Computer Science, vol. 60. Springer-Verlag, New York, 1978, pp. 393-481. Google Scholar
- 13 LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565. Google Scholar
- 14 LAMPORT, L. The weak Byzantine generals problem. J. ACM 30, 3 (July 1983), 668-676. Google Scholar
- 15 LAMPORT, L., SHOSTAK, R., AND PEASE, M. The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 382-401. Google Scholar
- 16 PINTER, S. Distributed computation systems: Modelling, verification and algorithms. Ph.D. dissertation. Dept. of Computer Science, Boston Univ., Boston, Mass., 1984. Google Scholar
- 17 REISCHUK, R. A new solution for the Byzantine generals problem. Inf. Control 64 (1985), 23-42. Google Scholar
- 18 SCHNEIDER, F.B. Byzantine generals in action: Implementing fail-stop processors. ACM Trans. Comput. Syst. 2, 2 (May 1984), 145-154. Google Scholar
- 19 SKEEN, D. A quorum based commit protocol. Tech. Rep. TR 82-483, Computer Science Dept., Cornell Univ., Ithaca, N.Y., Feb. 1982. Google Scholar
- 20 SRIKANTH, T. K., AND TOUEG, S. Simulating authenticated broadcasts to derive simple faulttolerant algorithms. Rep. 84-623, Computer Science Dept., Cornell Univ., Ithaca, N.Y., 1984.Google Scholar
Index Terms
- Consensus in the presence of partial synchrony
Recommendations
Solving Consensus in True Partial Synchrony
The notion of partial synchrony has been introduced to circumvent the FLP impossibility result for solvability of consensus in fault tolerant distributed systems. This notion helps us to evaluate the efficiency of algorithms that needs to solve consensus ...
Minimal Synchrony for Byzantine Consensus
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed ComputingSolving the consensus problem requires in one way or another that the underlying system satisfies some synchrony assumption. Considering an asynchronous message-passing system of n processes where (a) up to t< n/3 may commit Byzantine failures, and (b) ...
Comments