Cynthia Dwork
Nancy Lynch
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) ...
Reviews
Jason Gait
A distributed set of processors reaches consensus on a value when the correctly performing processors decide on the same value. This outcome is subject to the conditions that if those correct processors begin with the same value, then they must agree on the result, and that the presence of faulty processors does not prevent an agreement among the correct ones. A synchronous system has known upper bounds on message transit time and processor speed. For a partially synchronous system, either the upper bounds exist but are not a priori known, or the bounds are known but are only valid at some undetermined future time. For processor synchronous systems, it is known that the existence of a moment after which the message transit time will respect a known bound is equivalent to the conditions of safety (i.e., correct processors do not disagree and do make valid decisions) and termination (i.e., correct processors will eventually decide). The authors study fault-tolerant consensus protocols for partially synchronous systems and for various fault models. These protocols are optimal with respect to the number of faults tolerated. The resiliency of a synchronization model is the maximum number of faults that can be tolerated by any protocol in the model. If either communication or processor operation is asynchronous, then it is known that no resilient consensus protocol exists. It is thus meaningful to study partially synchronous systems. In the general method that the authors use, each processor sends messages to the others to see if they agree with the value it has found. A processor decides on a value when it receives sufficiently many acknowledgements from other processors. The protocols depend on distributed clocks maintained by a number of processors; this number is linear in the number of faults tolerated. The authors' protocols reach consensus in time polynomial in the system parameters, and the communication overhead to reach consensus is also polynomial in the system parameters.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments