On the improbability of reaching Byzantine agreements

ABSTRACT

It is well known that for the Byzantine Generals Problem, no deterministic protocol can exist for an n-processor system if the number t of faulty processors is allowed to be as large as n/3. In this paper we investigate the maximum achievable agreement probability Β_n,t in a model in which the faulty processors can be as devious and powerful as possible. We also discuss a restricted model with Β_n,t denoting the corresponding maximum achievable probability. We will prove that: (i) for n = 3, t = 1 (the first nontrivial case), Β_3,1 = (√5 - 1)/2 (the reciprocal of the golden ratio); (ii) for all ε with 0 < ε < 1, if t/n > 1 - log (1 -ε)^1/2/ log (1 - (1 -ε)^1/2) then Β^t_n,t < ε

References

1. ABDKPR.H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg, and R. Reischuk, "Achievable cases in an asynchronous environment," Proc. 28th 1EEE Syrup. on Found. of Computer Science, (1987), 337-346.
2. Be.M. Ben-Or, "Another Advantage of Free Choice' Completely Asynchronous Agreement Protocols," Proc. 2nd ACM Syrup. on Principles of Distributed Computing (1983), 27-30.
3. BLS.M. Ben-Or, N. Linial, and M. Saks, "Collective coin flipping and other models of imperfect information, Rutcor Research Report 44-87, R UTCOR, Rutgers UniversiO', December, 1987.
4. Bra1.G. Brach a, "An Asynchronous Protocol," Proc. 3rd ACM Symp. on Principles of Distributed Computing (1984), 154-162.
5. Bra2.G. Bracha, "An O(logn) expected rounds randomized Byzantine Generals protocol," Journal of ACM 34 (1987), 910-920.
6. BD.A.Z. Broder and D. Dolev, "Flipping Coins in Many Pockets (Byzantine Agreement on Uniformly Random Values)," Proc. 25th IEEE Symp. on Found. of Computer Science (1984), 157-170.
7. CC.B. Chor and B. Coan, "A simply and efficient randomized Byzantine agreement algorithm," Proc. 4th Symp. on ReliabiliD' in Distributed Software and Database Systems (1984), 98-106.
8. CMS.B. Chor, M. Merritt, and D. Shmoys, "Simple Constant-Time Consensus Protocols and Realistic Failure Models," Proc. 4th ACM Syrup. on Principles of Distributed Computing (1985), 152-162.
9. DFFLS.D. Dolev, M. Fischer, M. J. Fowler, N. Lynch, and R. Strong, "Efficient Byzantine agreement without authentication," information and Control 52 (1982), 257-274.
10. DLPSW.D. Dolev, N. Lynch, S. Pinter, E. Start, and W. Weihl, "Reaching approximate agreement in the presence of faults," Journal of ACM 33 (1986), 499-516.
11. DS.D. Dolev and H.R. Strong, "Polynomial algorithms for multiple rocessor agreement." In Proceedings of the 14th ACM Syrup. on Theory of Computing (1982), 401-407.
12. DLS.C. Dwork, N. }Lynch and L. Stockmeyer, "Consensus in the presence of partial Synchrony," Journal of ACM 35 (1988), 288-!323.
13. DSS.C. Dwork, D. Shmoys, and L. Stockm eyer, ' 'Flip p in g co in s persuasively in constant expected time," Proc. 27 IEEt7 Syrup. on Found. of Computer Science (1986), 222-232.
14. FL.M. Fischer, and N. Lynch, "A lower bound for the lime to assure interactive consistence," Inf. Proc. Lett 14, 4 (1982), 183-186.
15. FLM.M. Fischer, N. Lynch, and M. Merritt, "Easy impossibility proofs for distributed consensus problems," Distr. Comput. 1, 1 (1986).
16. FLP.M. Fischer, N. Lynch, and M.S. Paterson, "impossibility of distributed consensus with one faulty process," Journal of ACM 32, 2 (1985), 374-382.
17. KKL.J. Kahn, G. Kalai, and N. Linial, "The Influence of Variables on Boolean Functions," Proc. 29 iEEE Symp. on Found. of Computer Science (1988), 68- 80.
18. KY.A, Karlin and A. Yao, "Probabilistic lower bounds for the Byzantine Generals Problem," unpublished.
19. LSP.L. Lamport, R. Shostak, and J. Pease, "The Byzantine generals problems," ACM Trans. Program Lang. Syst. 4, 2 (1982), 382-40,1.
20. MS.S. Mahaney and F. Schneider, "Inexact agreement' accuracy, precision, and graceful degradation," Preprint, May, 1985.
21. PSL.M. Pease, R. Shostak, and L. Lamport, "Reaching Agreement in the Presence of Faults," Journal of ACM 27 (I980), 228-234.
22. R.M.O. Rabin, "Randomized Byzantine Generals," Proc. 24th IEEE Syrup. on Found. of Computer Science (1983), 403-409.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

    • Parallel architectures

      • Multiple instruction, multiple data

• Networks

  • Network protocols

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making