Tight bounds for the sequence transmission problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Tight bounds for the sequence transmission problem

Full text

Pdf (1.23 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the eighth annual ACM Symposium on Principles of distributed computing table of contents

Edmonton, Alberta, Canada

Pages: 73 - 83

Year of Publication: 1989

ISBN:0-89791-326-4

Authors

Da-Wei Wang	Department of Computer Science, Yale University
L. D. Zuck	Department of Computer Science, Yale University

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 11, Citation Count: 17

Additional Information:

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/72981.72986 What is a DOI?

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.

	AFWZ89	H. Attiya, M. J. Fischer, D. Wang, and L. D. Zuck, Reliable communication using unreliable channels, Manuscript, 1989.
	AUWY82	A.V. Aho, J. D. Ullman, A. D. Wyner, and M. Yannakakis, Bounds on the size and transmission rate of communication protocols, Comp. ~ Maths. with AppIs. 8:3, 1982, pp. 205-214. This is a later version of {AUY79}.
	AUY79	A.V. Aho, J. D. Ul\|man, and M. Yannakakis, Modeling communication protocols by automata, Proc. 20th IEEE Syrup. on Foundations of Computer Science, 1979, pp. 267-273.
	BSW69	K. A. Bartlett , R. A. Scantlebury , P. T. Wilkinson, A note on reliable full-duplex transmission over half-duplex links, Communications of the ACM, v.12 n.5, p.260-261, May 1969 [doi>10.1145/362946.362970]
	Car	D.E. Carlson, Bit-oriented data link control, Plenum New York.
	FZ88	Michael J. Fischer , Lenore D. Zuck, Reasoning about uncertainty in fault-tolerant distributed systems, Proceedings of a Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, p.142-158, September 1988, Warwick, United Kingdom
	Hal87	:I. Y. Halpern, Using reasoning; about knowledge to analyze distributed systems, Annual Review of Computer Science, Vol. 2, Annual Reviews Inc., 1987.
	HF88	J.Y. Halpern and R. Fagin, Modelling Knowledge and Action in Distribnted Systems, Technical Report, IBM, RJ6303, 1988.
	HM84	Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.50-61, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806735]
	HT89	Joseph Y. Halpern and Mark R. Turtle, Probabilistic knowledge and the power of the adversary, Proc. 8th A CM Syrup. on Principles of Distributed Computing, 1989.
	HZ87	Joseph Y. Halpern, A little knowledge goes a long way: simple knowledge-based derivations and correctness proofs for a family of protocols, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.269-280, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41863]
	LMF88	Nancy A. Lynch , Yishay Mansour , Alan Fekete, Data link layer: two impossibility results, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.149-170, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62572]
	Ste76	M.V. Stenning, A data transfer protocol, Comput. Networks 1, 1976, pp. 99- 110.
	Zim80	Zimmermann, Osi reference modelthe iso model for architecture for open systems interconnection, 1EEE Transactions on Communications COM-28, 1980.

CITED BY 17

	Ewan Tempero , Richard Ladner, Tight bounds for weakly bounded protocols, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.205-218, August 22-24, 1990, Quebec City, Quebec, Canada
	Michael Merritt , Gadi Taubenfeld, Knowledge in shared memory systems (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.189-200, August 19-21, 1991, Montreal, Quebec, Canada
	Yishay Mansour , Baruch Schieber, The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels, Journal of the ACM (JACM), v.39 n.4, p.783-799, Oct. 1992
	Ewan D. Tempero , Richard E. Ladner, Recoverable sequence transmission protocols, Journal of the ACM (JACM), v.42 n.5, p.1059-1090, Sept. 1995
	Yehuda Afek , Hagit Attiya , Alan Fekete , Michael Fischer , Nancy Lynch , Yishay Mansour , Dai-Wei Wang , Lenore Zuck, Reliable communication over unreliable channels, Journal of the ACM (JACM), v.41 n.6, p.1267-1297, Nov. 1994
	N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada
	Y. Mansour , B. Schieber, The intractability of bounded protocols for non-FIFO channels, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.59-72, June 1989, Edmonton, Alberta, Canada
	O. Goldreich , A. Herzberg , Y. Mansour, Source to destination communication in the presence of faults, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.85-101, June 1989, Edmonton, Alberta, Canada
	Da-Wei Wang , Lenore Zuck, Real-time sequence transmission problem, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.111-123, August 19-21, 1991, Montreal, Quebec, Canada
	Alan Fekete , Nancy Lynch , Yishay Mansour , John Spinelli, The impossibility of implementing reliable communication in the face of crashes, Journal of the ACM (JACM), v.40 n.5, p.1087-1107, Nov. 1993
	Micah Adler , Faith Fich, The complexity of end-to-end communication in memoryless networks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.239-248, May 04-06, 1999, Atlanta, Georgia, United States
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Shlomi Dolev , Jennifer L. Welch, Crash Resilient Communication in Dynamic Networks, IEEE Transactions on Computers, v.46 n.1, p.14-26, January 1997
	Sylvie Delaët , Sébastien Tixeuil, Tolerating transient and intermittent failures, Journal of Parallel and Distributed Computing, v.62 n.5, p.961-981, May 2002
	Michael Merritt , Gadi Taubenfeld, Knowledge in shared memory systems, Distributed Computing, v.7 n.2, p.99-109, December 1993
	Pierre Fraigniaud , Cyril Gavoille, Header-size lower bounds for end-to-end communication in memoryless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1630-1638, 14 July 2006
	Kai Engelhardt , Yoram Moses, Single-bit messages are insufficient for data link over duplicating channels, Information Processing Letters, v.107 n.6, p.235-239, August, 2008