Cost-sensitive analysis of communication protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cost-sensitive analysis of communication protocols

Full text

Pdf (1.09 MB)

Source

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

Quebec City, Quebec, Canada

Pages: 177 - 187

Year of Publication: 1990

ISBN:0-89791-404-X

Authors

Baruch Awerbuch	Dept. of Mathematics and Lab. for Computer Science, M.I.T., Cambridge, MA
Alan Baratz	IBM T. J. Watson Research Center, Yorktown Heights, NY
David Peleg	Dept. of Applied Mathematics, The Weizmann Institute, Rehovot 76100, Israel

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): 6, Downloads (12 Months): 23, Citation Count: 15

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/93385.93417 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.

	AAPS87	Yehuda Afek, Baruch Awerbueh, Serge A. Plotkin, and Michael Saks. Local management of a global resource in a communication network. In 28th Annual Symposium on Foundalions of Computer Science. IEEE, October 1987.
	ABNLP89	B. Awerbuch , A. Bar-Noy , N. Linial , D. Peleg, Compact distributed data structures for adaptive routing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.479-489, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73053]
	AGPV89	Baruch Awerbuch , Oded Goldreich , Ronen Vainish , David Peleg, A trade-off between information and communication in broadcast protocols, Journal of the ACM (JACM), v.37 n.2, p.238-256, April 1990 [doi>10.1145/77600.77618]
	ALSY88	Yehuda Afek , Gad M. Landau , Baruch Schieber , Moti Yung, The power of multimedia: combining point-to point and multi-access networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.90-104, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62564]
	AP89	Baruch Awerbuch and David Peleg. Routing with polynomial communicationspace trade-off. Technical Memo TM-411, MIT, Lab. for Computer Science, September 1989.
	Awe85a	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	Awe85b	Baruch Awerbuch. A new distributed depth-first-search algorithm. Info. Process. Letters, 20:147-150, April 1985.
	Awe87	B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
	Awe89	B. Awerbuch, Randomized distributed shortest paths algorithms, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.490-500, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73054]
	DS80	Edsger W. Dijkstra and C. S. Scholten. Termination detection for diffusing computations, lnfo. Process. Letters, 11(1):1- 4, August 1980.
	ER90	S. Even , S. Rajsbaum, The use of a synchronizer yields maximum computation rate in distributed networks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.95-105, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100227]
	Eve79	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	Gal82	Robert G. Galtager. Distributed minimum hop algorithms. Technical Report LIDS-P-1175, MIT, Lab. for Information and Decision Systems, January 1982.
	GHS83	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	GS86	Oded Goldreich , Liuba Shrira, The effects of link failures on computations in asynchronous rings, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.174-185, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10605]
	Jaf80	Jeffrey Jaffe. Using signalling messages instead of docks. Unpublished manuscript., 1980.
	Lam78	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	PU89	David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, SIAM Journal on Computing, v.18 n.4, p.740-747, Aug. 1989 [doi>10.1137/0218050]
	Seg83	Adrian Segall. Distributed network protocols. IEEE Trans. on Info. Theory, IT- 29(1):23-35, January 1983. Some details in technical report of same name, MIT Lab. for Info. and Decision Syst., LIDS- P-1015; Technion Dept. EE, Publ. 414, July 1981.

CITED BY 15

	Mehrdad Parsa , Qing Zhu , J. J. Garcia-Luna-Aceves, An iterative algorithm for delay-constrained minimum-cost multicasting, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.461-474, Aug. 1998
	Guy Kortsarz , David Peleg, Approximating shallow-light trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.103-110, January 05-07, 1997, New Orleans, Louisiana, United States
	Ashish Goel , Kamesh Munagala, Balancing Steiner trees and shortest path trees online, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.562-563, January 09-11, 2000, San Francisco, California, United States
	Vojtech Bálint, The non-approximability of bicriteria network design problems, Journal of Discrete Algorithms, v.1 n.3-4, p.339-355, June 2003
	Samir Khuller , Balaji Raghavachari , Neal Young, Balancing minimum spanning and shortest path trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.243-250, January 25-27, 1993, Austin, Texas, United States
	Kenneth D. Boese , Andrew B. Kahng , Gabriel Robins, High-performance routing trees with identified critical sinks, Proceedings of the 30th international conference on Design automation, p.182-187, June 14-18, 1993, Dallas, Texas, United States
	Pascal von Rickenbach , Roger Wattenhofer, Gathering correlated data in sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA
	Razvan Cristescu , Baltasar Beferull-Lozano , Martin Vetterli , Roger Wattenhofer, Network correlated data gathering with explicit communication: NP-completeness and algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.41-54, February 2006
	Yao-Wen Chang , Kai Zhu , D. F. Wong, Timing-driven routing for symmetrical array-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.433-450, July 2000
	Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation for the single sink edge installation problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.383-388, July 2001, Hersonissos, Greece
	Moses Charikar , Jon Kleinberg , Ravi Kumar , Sridhar Rajagopalan , Amit Sahai , Andrew Tomkins, Minimizing wirelength in zero and bounded skew clock trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.177-184, January 17-19, 1999, Baltimore, Maryland, United States
	Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States
	Esther M. Arkin , Michael A. Bender , Dongdong Ge, Improved approximation algorithms for the freeze-tag problem, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003