Possibility and complexity of probabilistic reliable communication in directed networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Possibility and complexity of probabilistic reliable communication in directed networks

Full text

Pdf (290 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing table of contents

Denver, Colorado, USA

SESSION: Fault tolerance table of contents

Pages: 265 - 274

Year of Publication: 2006

ISBN:1-59593-384-0

Authors

Kannan Srinathan	International Institute of Information Technology, Hyderabad, India
C. Pandu Rangan	Indian Institute of Technology, Madras, India

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 43, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1146381.1146421 What is a DOI?

ABSTRACT

We provide a complete characterization of directed networks in which probabilistic reliable communication is possible. We also outline a round optimal protocol for the same.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Yvo Desmedt , Yongge Wang, Perfectly Secure Message Transmission Revisited, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.502-517, May 02, 2002
	2	W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22:644--654, November 1976.
	3	D. Dolev. The Byzantine Generals Strike Again. Journal of Algorithms, 3(1):14--30,1982.
	4	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]
	5	M. Franklin and R. N. Wright. Secure Communication in Minimal Connectivity Models. In Proceedings of EUROCRYPT, pages 346--360, 1998.
	6	Matthew Franklin , Moti Yung, Secure hypergraphs: privacy from partial broadcast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.36-44, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225077]
	7	Juan A. Garay , Kenneth J. Perry, A Continuum of Failure Models for Distributed Computing, Proceedings of the 6th International Workshop on Distributed Algorithms, p.153-165, November 02-04, 1992
	8	Martin Hirt , Ueli Maurer, Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.25-34, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259412]
	9	M V N Ashwin Kumar , Pranava R. Goundan , K Srinathan , C. Pandu Rangan, On perfectly secure communication over arbitrary networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571858]
	10	Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112605]
	11	T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
	12	H. M. Sayeed , H. Abu-Amara, Perfectly secure message transmission in asynchronous networks, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.100, October 25-28, 1995
	13	Hasan Md. Sayeed , Hosame Abu-Amara, Efficient perfectly secure message transmission in synchronous networks, Information and Computation, v.126 n.1, p.53-61, April 10, 1996 [doi>10.1006/inco.1996.0033]

CITED BY 3

	Arpita Patra , Ashish Choudhary , Chanrasekharan Pandu Rangan, Constant phase efficient protocols for secure message transmission in directed networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Bhavani Shankar , Prasant Gopal , Kannan Srinathan , C. Pandu Rangan, Unconditionally reliable message transmission in directed networks, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1048-1055, January 20-22, 2008, San Francisco, California
	Kannan Srinathan , Arpita Patra , Ashish Choudhary , C. Pandu Rangan, Unconditionally secure message transmission in arbitrary directed synchronous networks tolerating generalized mixed adversary, Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, March 10-12, 2009, Sydney, Australia