A quantitative approach to dynamic networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A quantitative approach to dynamic networks

Full text

Pdf (1.55 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: 189 - 203

Year of Publication: 1990

ISBN:0-89791-404-X

Authors

Baruch Awerbuch	Department of Mathematics and Laboratory for Computer Science, MIT, Cambridge, MA
Oded Godlreich	Department of Computer Science, Technion, Haifa, Israel
Amir Herzberg	Department of Computer Science, Technion, Haifa, 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): 0, Downloads (12 Months): 11, Citation Count: 9

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

	1	Yehuda Afek, Baruch Awerbuch, and Eli Gafili. Applying static network protocols to dynamic networks, in 28th Annual Symposium on Foundations of Computer Science, IEEE, October 1987.
	2	Yehuda Afek and Eli Gafni. Bootstrap network resynchronization: an efficient technique for end-to-end communication. October 1989. Manuscript.
	3	Eli Gafni , Yehuda Afek, End-to-end communication in unreliable networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.131-148, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62570]
	4	Yehuda Afek, Eli Gafni, and Adi Rosen. Slide - a technique for communication in unreliable networks. January 1990. Extended Abstract.
	5	IIagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the time to reach agreement in the presence of tinting uncertainty. 1990. In preparation.
	6	IIagit Attiya and Nancy Lynch. Time bounds for real-time process control in the presence of tinting uncertainty. In Procecdings of the l Oth IEEE Real-Time Systems Symposium, pages 268-284, December 1989. Expanded version in MIT/LCS/TM-403.
	7	Barueh Awerbueh, Israel Cidon, and Shay Kutten. Communication-optimal maintenance of dynamic trees. January 1990. Manuscript.
	8	Baruch Awerbuch and Shimon Even. Reliable broadcast protocols in unreliable networks. Networks, 16(4):381-396, Winter 1986.
	9	Baruch Awerbuch, Oded Goldreich, and Amir tlerzberg. A Quantitative Approach to Dynamic Networks (version without global time). Technical Report 624, Computer Science Dept., Technion, May 1989.
	10	Baruch Awerbuch and Yishay Mansour. Efficient topology update algorithms. 1988. Manuscript.
	11	Baruch Awerbuch, Yishay Mansour, and Nir Shavit. Polynomial end-to-end communication. In Proc. of the 30th IEEE Symp. on Foundations of Computer Science, pages 358-363, October 1989.
	12	Baruch Awerbuch and Adrian Segall. A reliable broadcast protocol. 1EEE Trans. Comm., COM-31:896-901, July 1983.
	13	A. E. Baratz, d. P. Gray, P. E. Green :It., J. M. Jaffe, and D. P. Pozefsky. SNA networks of small systems. IEEE Trans. on Selected Areas iu Comm., SAC-3(3):416-426, May 1985.
	14	Alan E. Baratz , Inder S. Gopal , Adrian Segall, Fault Tolerant Queries in Computer Networks, Proceedings of the 2nd International Workshop on Distributed Algorithms, p.30-40, July 08-10, 1987
	15	Alan E. Baratz and Adrian Segall. Reliable link initialization procedures. IEEE Trans. on Communication, COM-36:144-152, February 1988.
	16	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]
	17	S. G. Finn. Resynch procedures and a failsafe network protocol. IEEE Tran. Comm., COM- 27(6):840-846, June 1979.
	18	Robert G. Gallager. A shortest path routing algorithm with automatic resynch. March 1976. Manuscript.
	19	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 [doi>10.1145/72981.72987]
	20	Amir Iterzberg. Network management in the presence of faults, in Ninth International Conference on Computers and Communication (ICCC), October 1988.
	21	A. Herzberg , S. Kutten, Fast isolation of arbitrary forwarding faults, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.339-353, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73006]
	22	P. A. Humblet , S. R. Soloway, Topology broadcast algorithms, Computer Networks and ISDN Systems, v.16 n.3, p.179-186, Jan. 1989 [doi>10.1016/0169-7552(89)90066-4]
	23	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]
	24	John M. McQuillan, Ira Richer, and Eric C. Rosen. The new routing algorithm for the ARPANET. IEEE Trans. Comm., 28(5):711- 719, hlay 1980.
	25	Mike Merritt, F. Modugno, and Mark Tutlle. Time constrained automata. November 1988. Manuscript.
	26	Radia Pcrlman. Fault tolerant broadcast of routing information. Computer Networks, December 1983.
	27	Eric C. Rosen, Vulnerabilities of network control protocols: an example, ACM SIGCOMM Computer Communication Review, v.11 n.3, p.10-16, July 1981 [doi>10.1145/1015591.1015592]
	28	Adrian Segall. Distributed network protocols. 1EEE Trans, Iufo. Theory, IT-29(I):23-35, January 1983.
	29	John M. Spinelli and Robert G. Gallager. Broadcasting topology information in computer networks. IEEE Trans. Comm., COM- 37(5):468-474, May 1989.
	30	A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	31	H. Zimmerman. OSI reference model- the ISO model of architecture for open systems interconnection. IEEE Trans. Comm., 28:425-432, 1980.

CITED BY 9

	Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Log-space polynomial end-to-end communication, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.559-568, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Yehuda Afek , Eli Gafni , Adi Rosén, The slide mechanism with applications in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.35-46, August 10-12, 1992, Vancouver, British Columbia, Canada
	Amir Herzberg, Connection-based communication in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.13-24, August 10-12, 1992, Vancouver, British Columbia, Canada
	James P. G. Sterbenz , Rajesh Krishnan , Regina Rosales Hain , Alden W. Jackson , David Levin , Ram Ramanathan , John Zao, Survivable mobile wireless networks: issues, challenges, and research directions, Proceedings of the 3rd ACM workshop on Wireless security, p.31-40, September 28-28, 2002, Atlanta, GA, USA
	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
	Shlomi Dolev , Jennifer L. Welch, Crash Resilient Communication in Dynamic Networks, IEEE Transactions on Computers, v.46 n.1, p.14-26, January 1997
	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
	Michael Elkin, A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Baruch Awerbuch , Israel Cidon , Shay Kutten, Optimal maintenance of a spanning tree, Journal of the ACM (JACM), v.55 n.4, p.1-45, September 2008