Memory-efficient and self-stabilizing network RESET (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Memory-efficient and self-stabilizing network RESET (extended abstract)

Full text

Pdf (1.02 MB)

Source

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

Los Angeles, California, United States

Pages: 254 - 263

Year of Publication: 1994

ISBN:0-89791-654-9

Authors

Baruch Awerbuch	Johns Hopkins University, Baltimore, MD and MIT Lab. for Computer Science
Rafail Ostrovsky	U.C. Berkeley and ICSI

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): 1, Downloads (12 Months): 21, Citation Count: 11

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

	AAG87	Y. Afek, B. Awerbuch, and E. Gafni. Applying static network protocols to dynamic networks. in Proc. ~8th IEEE Syrup. on Foundations of Computer Science, October 1987.
	AB89	Y. Afek and G. Brown. Self-stabilization of the alternating bit protocol. In Proceedings of the 8th IEEE Symposium on Reliable Distributed Systems, pages 80-83, 1989.
	ACG+90	Baruch Awerbuch , Israel Cidon , Inder Gopal , Marc Kaplan , Shay Kutten, Distributed control for PARIS, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.145-159, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93412]
	AG90	Anish Arora , Mohamed Gouda, Distributed reset (extended abstract), Proceedings of the tenth conference on Foundations of software technology and theoretical computer science, p.316-331, November 1990, Bangalore, India
	AKM+93	Baruch Awerbuch , Shay Kutten , Yishay Mansour , Boaz Patt-Shamir , George Varghese, Time optimal self-stabilizing synchronization, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.652-661, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167256]
	APV91	Baruch Awerbuch , Boaz Patt-Shamir , George Varghese, Self-stabilization by local checking and correction (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.268-277, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185378]
	AV91	Baruch Awerbuch , George Varghese, Distributed program checking: a paradigm for building self-stabilizing distributed protocols (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.258-267, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185377]
	AIO92	B. Awerbuch, G. itkis and R. Ostrovsky Hardware-Based Self-Stabilization, unpublished manuscript, April 29, 1992.
	AKY90	Yehuda Afek , Shay Kutten , Moti Yung, Memory-efficient self stabilizing protocols for general networks, Proceedings of the 4th international workshop on Distributed algorithms, p.15-28, June 1991, Bari, Italy
	BGJ+85	A. Baratz, J. Gray, P. Green Jr., J. Jaffe, and D. Pozefski.~ SNA networks of small systems. IEEE Journal on Selected Areas in Communications, SAC-3(3):416-426, May 1985.
	BGW87	G. Brown, M. Gouda and C.Wu A selfstabilizing token system. In ~O'th Hawaii International Confcr~nvv on $yatvra $ci~r~c~a, 1987.
	CG88	I. Cidon and I. S. Gopal. Paris: An approach to integrated high-speed private networks, international Journal of Digital 8 Analog Cabled Systems, 1(2):77-86, April-June 1988.
	CO89	I. Cidon and Y. Ofek. Metaring- a full-duplex ring with fairness and spatial reuse. Research Report RC 14961, IBM, Sept. 1989. Also IN- FOCOM 9O.
	CL85	K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
	Dij74	Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
	DIM90	Shlomo Dalev , Amos Israeli , Shlomo Moran, Self-stabilization of dynamic systems assuming only read/write atomicity, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.103-117, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93407]
	DIM91	Shlomi Dolev , Amos Israeli , Shlomo Moran, Resource bounds for self stabilizing message driven protocols, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.281-293, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112624]
	Fin79	S. Finn. Resynch procedures and a fail-safe network protocol. IEEE Trans. on Commun., COM-27(6):840-845, June 1979.
	KP90	Shmuel Katz , Kenneth Perry, Self-stabilizing extensions for message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.91-101, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93405]
	IJ90	Amos Israeli , Marc Jalfon, Token management schemes and random walks yield self-stabilizing mutual exclusion, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.119-131, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93409]
	LT89	N. Lynch and M. Turtle. An introduction to input/output automata. CWI Quarterly, 2(3), September 1989.
	MW86	Shlomo Moran , Manfred Warmuth, Gap theorems for distributed computing, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.131-150, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10602]
	MOOY92	Alain Mayer , Yoram Ofek , Rafail Ostrovsky , Moti Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.667-678, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129777]
	MRR80	J. McQuillan, I. Richer, and E. Rosen. The new routing algorithm for the arpanet. IEEE Trans. on Commun., 28(5):711-719, May 1980.
	OY90	Yoram Ofek , Moti Yung, Principle for high speed network control: congestion-and deadlock-freeness, self-routing, and a single buffer per link, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.161-175, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93414]
	Per83	R. Perlman. Fault-tolerant broadcast of routing information. Computer Networks, 7:395- 405.
	Per85	Radia Perlman, An algorithm for distributed computation of a spanningtree in an extended LAN, Proceedings of the ninth symposium on Data communications, p.44-53, September 1985, Whistler Moutain, British Columbia, Canada
	Wec80	S. Wecker. DNA: the digital network architecture. IEEE Transactions on Communication, COM-28:510-526, April 1980.
	Var-92	George Varghese, Self-stabilization by local checking and correction, Massachusetts Institute of Technology, Cambridge, MA, 1993

CITED BY 11

	Rafail Ostrovsky , Daniel Shawcross Wilkerson, Faster computation on directed networks of automata, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.38-46, August 20-23, 1995, Ottowa, Ontario, Canada
	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
	Darin Goldstein , Nick Meyer, The wake up and report problem is time-equivalent to the firing squad synchronization problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.578-587, January 06-08, 2002, San Francisco, California
	Joffroy Beauquier , Maria Gradinariu , Colette Johnen, Memory space requirements for self-stabilizing leader election protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.199-207, May 04-06, 1999, Atlanta, Georgia, United States
	Alain Mayer , Rafail Ostrovsky , Moti Yung, Self-stabilizing algorithms for synchronous unidirectional rings, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.564-573, January 28-30, 1996, Atlanta, Georgia, United States
	Joffroy Beauquier , Maria Gradinariu , Colette Johnen , Jérôme Durand-Lose, Token-based self-stabilizing uniform algorithms, Journal of Parallel and Distributed Computing, v.62 n.5, p.899-921, May 2002
	Shlomi Dolev , Mohamed G. Gouda , Marco Schneider, Memory requirements for silent stabilization, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.27-34, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Albert Mo Kim Cheng , Seiya Fujii, Self-Stabilizing Real-Time OPS5 Production Systems, IEEE Transactions on Knowledge and Data Engineering, v.16 n.12, p.1543-1554, December 2004
	Darin Goldstein , Nick Meyer, The wake up and report problem is time-equivalent to the firing squad synchronization problem, Distributed Computing, v.17 n.1, p.21-31, February 2004
	David Pritchard , Santosh Vempala, Symmetric network computation, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Baruch Awerbuch , Shay Kutten , Yishay Mansour , Boaz Patt-Shamir , George Varghese, A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock, IEEE Transactions on Dependable and Secure Computing, v.4 n.3, p.180-190, July 2007