×

Modular construction of a Byzantine agreement protocol with optimal message bit complexity. (English) Zbl 0753.68009

The paper deals with a new Byzantine Agreement Protocol (BAP) whose quality is described by the following measures:
— the number of processors required to tolerate at most \(t\) faults,
— the number of rounds of communication,
— the total number of message bits,
— the size of the largest message.
The authors define the general transformation as the composition of two transformations, namely, from BAP to BBP (Byzantine Broadcast Protocol), and from a collection of BBPs to BAP. The new BAP protocol is constructed by recursive applying these transformations. In addition, some theorems which show the higher quality of the proposed BAP, as compared to well known BAPs, are proved. The new BAP turns out to be optimal or near optimal with respect to all quality measures.

MSC:

68M10 Network design and communication in computer systems
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bar-Noy, A.; Dolev, D., Consensus algorithms with one-bit messages, Distrib. Comput., 4, 105-110 (1991) · Zbl 0723.68012
[2] Bar-Noy, A.; Dolev, D.; Dwork, C.; Strong, H. R., Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement, Inform. and Comput. (1992), to appear · Zbl 0766.68002
[3] Ben-Or, M., Another advantage of free choice: Completely asynchronous agreement protocols, (Proceedings, 2nd ACM Symposium on Principles of Distributed Computing (1983)), 27-30
[4] Berman, P.; Garay, J. A., Asymptotically optimal distributed consensus, (Proceedings, 16th EATCS Colloquium on Automata, Languages, and Programming (1989)), 80-94
[5] Berman, P.; Garay, J. A., (Better Masking for Better Consensus (1990), Department of Computer Science, Pennsylvania State University), Technical Report CS-90-24
[6] Berman, P.; Garay, J. A.; Perry, K. J., Towards optimal distributed consensus, (Proceedings, 30th IEEE Symposium on Foundations of Computer Science (1989)), 410-415
[7] Berman, P.; Garay, J. A.; Perry, K. J., (Recursive Phase King Protocols for Distributed Consensus (1989), Department of Computer Science, Pennsylvania State University), Technical Report CS-89-24
[8] Chor, B.; Coan, B. A., A simple and efficient randomized Byzantine agreement algorithm, IEEE Trans. Software Engrg., SE-11, 531-539 (1985)
[9] Coan, B. A., Efficient agreement using fault diagnosis, (Proceedings, 26th Allerton Conference on Communication, Control, and Computing (1988)), 663-672 · Zbl 1282.68083
[10] Coan, B. A.; Welch, J. L., Modular construction of nearly optimal Byzantine agreement protocols, (Proceedings, 8th ACM Symposium on Principles of Distributed Computing (1989)), 295-306
[11] Coan, B. A.; Welch, J. L., A Byzantine agreement protocol with optimal message bit complexity, (Proceedings, 27th Allerton Conference on Communication, Control, and Computing (1989)), 1062-1071
[12] Dolev, D., The Byzantine generals strike again, J. Algorithms, 3, 14-30 (1982) · Zbl 0495.68093
[13] Dolev, D.; Fischer, M. J.; Fowler, R. J.; Lynch, N. A.; Strong, H. R., An efficient algorithm for Byzantine agreement without authentication, Inform. and Control, 52, 257-274 (1982) · Zbl 0507.68017
[14] Dolev, D.; Reischuk, R., Bounds on information exchange for Byzantine agreement, J. Assoc. Comput. Mach., 32, 191-204 (1985) · Zbl 0629.68026
[15] Dolev, D.; Reischuk, R.; Strong, H. R., Early stopping in Byzantine agreement, J. Assoc. Comput. Mach., 37, 720-741 (1990) · Zbl 0711.68008
[16] Fischer, M. J.; Lynch, N. A., A lower bound for the time to assure interactive consistency, Inform. Process. Lett., 14, 183-186 (1982) · Zbl 0493.68026
[17] Fischer, M. J.; Lynch, N. A.; Merritt, M., Easy impossibility proofs for distributed consensus problems, Distrib. Comput., 1, 26-39 (1986) · Zbl 0598.68024
[18] Lamport, L.; Shostak, R. E.; Pease, M., The Byzantine generals problem, ACM Trans. Program. Lang. Syst., 4, 382-401 (1982) · Zbl 0483.68021
[19] Moses, Y.; Waarts, O., Coordinated traversal: \((t + 1)\)-round Byzantine agreement in polynomial time, J. Algorithms (1992), to appear · Zbl 0822.68045
[20] Pease, M.; Shostak, R. E.; Lamport, L., Reaching agreement in the presence of faults, J. Assoc. Comput. Mach., 27, 228-234 (1980) · Zbl 0434.68031
[21] Rabin, M., Randomized Byzantine generals, (Proceedings, 24th IEEE Symposium on Foundations of Computer Science (1983)), 403-409
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.