Efficient player-optimal protocols for strong and differential consensus

ABSTRACT

In this paper we consider the following two variants of the consensus problem. First, the strong consensus problem, where n players attempt to reach agreement on a value initially held by one of the correct players, despite the (malicious) behavior of up to t of them. (Recall that in the standard version of the problem, the players are also required to decide on one of the correct players' input values, but only when they all start with the same value; otherwise, they can decide on a default.) Although the problem is closely related to the standard problem, the only known solution with the optimal number of players requires exponential computation and communication in the unconditional setting.Even though the decision would be a value originally held by a correct player, strong consensus allows for a decision value that is the least common among the correct players. We also formulate the δ-differential consensus problem, which specifies that the value agreed on must be of a certain plurality among the correct players --- specifically, that the plurality of any other value cannot exceed the plurality of the decision value by more than δ.In this paper we study these problems, and present efficient protocols and tight lower bounds for several standard distributed computation models --- unconditional, computational, synchronous, and asynchronous.

REFERENCES

• 1: Amotz Bar-Noy , Xiaotie Deng , Juan A. Garay , Tiko Kameda, Optimal Amortized Distributed Consensus (Extended Abstract), Proceedings of the 5th International Workshop on Distributed Algorithms, p.95-107, October 07-09, 1991
• 2: Amotz Bar-Noy , Danny Dolev , Cynthia Dwork , H. Raymond Strong, Shifting gears: changing algorithms on the fly to expedite Byzantine agreement, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.42-51, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41844]
• 3: Donald Beaver , Nicol So, Global, unpredictable bit generation without broadcast, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.424-434, January 1994, Lofthus, Norway
• 4: Mihir Bellare , Juan A. Garay , Tal Rabin, Distributed pseudo-random bit generators—a new way to speed-up shared coin tossing, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.191-200, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248090]
• 5: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 6: Michael Ben-Or , Ran El-Yaniv, Resilient-optimal interactive consistency in constant time, Distributed Computing, v.16 n.4, p.249-262, December 2003 [doi>10.1007/s00446-002-0083-3]
• 7: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 8: Piotr Berman , Juan A. Garay , Kenneth J. Perry, Bit optimal distributed consensus, Computer science: research and applications, Plenum Press, New York, NY, 1992
• 9: Piotr Berman , Juan A. Garay, Asymptotically Optimal Distributed Consensus (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.80-94, July 11-15, 1989
• 10: Piotr Berman , Juan A. Garay, Adaptability and the Usefulness of Hints (Extended Abstract), Proceedings of the 6th Annual European Symposium on Algorithms, p.271-282, August 24-26, 1998
• 11: P. Berman, J. A. Garay, and K. J. Perry. Towards optimal distributed consensus (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 410--415, Research Triangle Park, North Carolina, 30 Oct.--1 Nov. 1989. IEEE.
• 12: Gabriel Bracha, An asynchronous [(n - 1)/3]-resilient consensus protocol, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.154-162, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806743]
• 13: Christian Cachin , Klaus Kursawe , Frank Petzold , Victor Shoup, Secure and Efficient Asynchronous Broadcast Protocols, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.524-541, August 19-23, 2001
• 14: Christian Cachin , Klaus Kursawe , Victor Shoup, Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.123-132, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343531]
• 15: Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167105]
• 16: Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
• 17: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 18: Roberto de Prisco , Dahlia Malkhi , Michael Reiter, On k-Set Consensus Problems in Asynchronous Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.1, p.7-21, January 2001 [doi>10.1109/71.899936]
• 19: D. Dolev and H. R. Strong. Authenticated algorithms for Byzantine agreement. SIAM Journal on Computing, 12(4):656--666, 1983.
• 20: P. Feldman. Asynchronous byzantine agreement in constant expected time. Manuscript, 1989.
• 21: Pesech Feldman , Silvio Micali, An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement, SIAM Journal on Computing, v.26 n.4, p.873-933, Aug. 1997 [doi>10.1137/S0097539790187084]
• 22: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 23: Juan A. Garay , Yoram Moses, Fully Polynomial Byzantine Agreement for Processors in Rounds, SIAM Journal on Computing, v.27 n.1, p.247-290, Feb. 1998 [doi>10.1137/S0097539794265232]
• 24: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 25: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 26: A. Karlin and A. C. Yao. Probabilistic lower bounds for the byzantine generals problem. Unpublished manuscript.
• 27: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 28: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 29: Michael Merritt , Omer Reingold , Gadi Taubenfeld , Rebecca N. Wright, Tight Bounds for Shared Memory Systems Accessed by Byzantine Processes, Proceedings of the 16th International Conference on Distributed Computing, p.222-236, October 28-30, 2002
• 30: Silvio Micali , Tal Rabin, Collective Coin Tossing Without Assumptions nor Broadcasting, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.253-266, August 11-15, 1990
• 31: Gil Neiger, Distributed consensus revisited, Information Processing Letters, v.49 n.4, p.195-201, Feb. 25, 1994 [doi>10.1016/0020-0190(94)90011-6]
• 32: Jesper Buus Nielsen, A Threshold Pseudorandom Function Construction and Its Applications, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.401-416, August 18-22, 2002
• 33: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 34: B. Pfitzmann and M. Waidner. Information-theoretic pseudosignatures and byzantine agreement for t >= n/3. Research report, IBM Research, Nov. 1996. Submitted for Publication.
• 35: M. O. Rabin. Randomized Byzantine Generals. In Proc. 24th Ann. IEEE Syrup. on Foundations of Computer Science, pages 403--409, 1983.
• 36: Sam Toueg, Randomized Byzantine Agreements, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.163-178, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806744]
• 37: R. Turpin and B. A. Coan. Extending binary Byzantine Agreement to multivalued Byzantine Agreement. Information Processing Letters, 18(2):73--76, Feb. 1984.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

General Terms:
Algorithms, Design, Performance