Brief announcement: global consistency can be easier than point-to-point communication

ABSTRACT

Global consistency or Byzantine Agreement (BA) and reliable point-to-point communication are two of the most important and well-studied problems in distributed computing. Informally, BA is about maintaining a consistent view of the world among all the non-faulty players in the presence of faults. In a synchronous network over n nodes of which up to any t are corrupted by a Byzantine adversary, BA is possible only if all pair point-to-point reliable communication is possible [Dol82, DDWY93] Specifically, in the standard unauthenticated model, (2t + 1)-connectivity is necessary whereas in the authenticated setting (t + 1)-connectivity is required. Thus, a folklore is that maintaining global consistency is at least as hard as the problem of all pair point-to-point communication. Equivalently, it is widely believed that protocols for BA over incomplete graphs exist only if it is possible to simulate an overlay-ed complete graph. Surprisingly, we show that the folklore is far from true-- achieving global consistency can be strictly easier than all-pair point-to-point communication.

In the authenticated model, it is assumed that the adversary can forge the signatures of only those nodes under its control. In contrast, the unauthenticated model assumes that the adversary can forge the signatures of all the nodes (that is, secure signatures are not used). We initiate a study on the entire gamut of BA's in between, viz., the adversary can forge the signatures of up to any k nodes apart from the up to t nodes that it can actively corrupt. We completely characterize the possibility of BA across the spectrum. Thus, our work attempts to unify the extant literature on agreement. It is, however, more than a mere attempt towards unification as it provides insights into the field. Specifically, apart from the extremes (of k = 0 and k = n − t where aforementioned folklore is known to hold), for every intermediate k, there are several networks over which BA is possible but all-pair point-to-point communication is not.

REFERENCES

• 1: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 2: Danny Dolev , Cynthia Dwork , Orli Waarts , Moti Yung, Perfectly secure message transmission, Journal of the ACM (JACM), v.40 n.1, p.17-47, Jan. 1993 [doi>10.1145/138027.138036]
• 3: {Dol82} D. Dolev. The Byzantine Generals Strike Again. Journal of Algorithms, 3(1):14--30, March 1982.
• 4: 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]
• 5: Taher El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of CRYPTO 84 on Advances in cryptology, p.10-18, August 1985, Santa Barbara, California, United States
• 6: Juan A. Garay, Reaching (and Maintaining) Agreement in the Presence of Mobile Faults (Extended Abstract), Proceedings of the 8th International Workshop on Distributed Algorithms, p.253-264, September 29-October 01, 1994
• 7: Craig Gentry , Chris Peikert , Vinod Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374407]
• 8: {HKN⁺05} Danny Harnik, Joe Kilian, Moni Naor, Omer Reingold, and Alon Rosen. On robust combiners for oblivious transfer and other primitives. In EUROCRYPT, pages 96--113, 2005.
• 9: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 10: {MP06} Remo Meier and Bartosz Przydatek. On robust combiners for private information retrieval and other primitives. In CRYPTO, pages 555--569, 2006.
• 11: {MPW07} Remo Meier, Bartosz Przydatek, and Jüurg Wullschleger. Robuster combiners for oblivious transfer. In TCC, pages 404--418, 2007.
• 12: 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]
• 13: Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004 [doi>10.1145/1039488.1039490]
• 14: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 15: Adi Shamir, Efficient signature schemes based on birational permutations, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.1-12, January 1994, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Reliability, Theory

Keywords:
agreement, authentication, incomplete networks, reliable communication