zbMATH — the first resource for mathematics

Knowledge and common knowledge in a Byzantine environment: Crash failures. (English) Zbl 0705.68019
Summary: We study what facts become common knowledge at various points in the execution of protocols in an unreliable system. This characterizes the simultaneous actions that can be carried out in such systems. For example, we obtain a complete characterization of the number of rounds required to reach simultaneous Byzantine agreement, given the pattern in which failures occur. From this we derive a new protocol for this problem that is optimal in all runs, rather than just always matching the worst- case bound. In some cases this protocol attains simultaneous Byzantine agreement in as few as two rounds. We also present a nontrivial simultaneous agreement problem called bivalent agreement for which there is a protocol that always halts in two rounds. Our analysis applies to simultaneous actions in general, and not just to Byzantine agreement. The lower bound proofs presented here generalize and simplify the previously known proofs.

68M10 Network design and communication in computer systems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Coan, B.; Dwork, C., Simultaneity is Harder than agreement, () · Zbl 0723.68014
[2] Chandy, K.M.; Misra, J., How processes learn, Distrib. comput., 1, No. 1, 40-52, (1986) · Zbl 0602.68026
[3] DeMillo, R.; Lynch, N.A.; Meritt, M., Cryptographic protocols, (), 383-400
[4] Dolev, D.; Dwork, C.; Stockmeyer, L., On the minimal synchronization needed for distributed consensus, (), 369-397
[5] Dolev, D.; Reischuk, R.; Strong, H.R., Eventual is earlier than immediate, (), 196-202
[6] Dolev, D.; Strong, H.R., Polynomial algorithms for multiple processor agreement, (), 401-407 · Zbl 0524.68021
[7] Fagin, R.; Vardi, M.Y., Knowledge and implicit knowledge in a distributed environment, (), 187-206
[8] Fischer, M.J., The consensus problem in unreliable distributed systems (A brief survey), (1983), Yale University Technical Report YALEU/DCS/RR-273 · Zbl 0517.68051
[9] Fischer, M.J.; Lynch, N.A., A lower bound for the time to assure interactive consistency, Inform. process. lett., 14, No. 4, 183-186, (1982) · Zbl 0493.68026
[10] Fischer, M.J.; Lynch, N.A.; Paterson, M., Impossibility of distributed consensus with one faulty process, () · Zbl 0629.68027
[11] Hadzilacos, V., A lower bound for Byzantine agreement with fail-stop processors, (1983), Harvard University Technical Report TR-21-83
[12] Halpern, J.Y.; Fagin, R., Modelling knowledge and action in distributed systems, () · Zbl 0685.68076
[13] Halpern, J.Y.; Moses, Y., Knowledge and common knowledge in a distributed environment; version of June 1989 (fourth revision) is available as IBM research report RJ 4421, (), 50-61, first version
[14] Halpern, J.Y.; Moses, Y., A guide to the modal logic of knowledge and belief, (), 480-490
[15] Lamport, L.; Fischer, M.J., Byzantine generals and transaction commit protocols, (1982), SRI Technical Report Op. 62
[16] Moses, Y.; Tuttle, M.R., Programming simultaneous actions using common knowledge, Algorithmica, 3, 121-169, (1988) · Zbl 0646.68031
[17] Parikh, R.; Ramanujam, R., Distributed processes and the logic of knowledge (preliminary report), (), 256-268
[18] Pease, M.; Shostak, R.; Lamport, L., Reaching agreement in the presence of faults, J. assoc. comput. Mach., 27, No. 2, 228-234, (1980) · Zbl 0434.68031
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.