An alternative solution to a problem on self-stabilization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An alternative solution to a problem on self-stabilization

Full text

Pdf (519 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 15 , Issue 4 (September 1993) table of contents

Pages: 735 - 742

Year of Publication: 1993

ISSN:0164-0925

Author

Sukumar Ghosh

The Univ. of Iowa, Iowa, IA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 38, 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/155183.155228 What is a DOI?

ABSTRACT

Dijkstra [4, 5] introduced the problem of self-stabilization in distributed systems as an interesting exercise for achieving global convergence through local actions. In [4] he presented three solutions to a specific version of the self-stabilization problem, one of which was proved in [6]. This paper presents an alternative solution of his self-stabilization problem with four-state machines.

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	Geoffrey M. Brown , Mohamed G. Gouda , Chuan-Lin Wu, Token Systems That Self-Stabilize, IEEE Transactions on Computers, v.38 n.6, p.845-852, June 1989 [doi>10.1109/12.24293]
	2	BURNS, J. E., GOUDA, M., AND MILLER, R. On relaxing interleaving assumptions. In Proceedings of the MCC Workshop on Self-Stab~lization (Austin, Tex., Nov. 10). MCC, Austin, Tex., 1989.
	3	Ernest J. H. Chang , Gaston H. Gonnet , Doron Rotem, On the costs of self-stabilization, Information Processing Letters, v.24 n.5, p.311-316, 16 March 1987 [doi>10.1016/0020-0190(87)90155-4]
	4	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]
	5	DIJKSTRA, E. W. Self-stablbzafion in spire of distributed control In Selected Wrzt~ng on Computers: A Personql Perspective. Springer-Verlag, New York, 1982, 41-45.
	6	Edsger W. Dijkstra, A belated proof of self-stabilization, Distributed Computing, v.1 n.1, p.5-6, Jan. 1986 [doi>10.1007/BF01843566]
	7	J. L. W. Kessels, An exercise in proving self-stabilization with a variant function, Information Processing Letters, v.29 n.1, p.39-42, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90131-7]
	8	KauIJE~, H. S. M. Self-stabilization (inspire of distributed control) m tree-structured systeins. Inf. Process. Lett. 8, 2 (Feb. 1979), 91 95.
	9	TCHUENTE, M.Sur l'auto-stabilisation dans un reseau d'ordinateurs. RAIRO Inf. Theor. 15, 1 (1981), 47-66.

CITED BY 3

	Ajoy K. Datta , Colette Johnen , Franck Petit , Vincent Villain, Self-stabilizing depth-first token circulation in arbitrary rooted networks, Distributed Computing, v.13 n.4, p.207-218, November 2000
	J. Beauquier , B. Bérard , L. Fribourg , F. Magniette, Proving convergence of self-stabilizing systems using first-order rewriting and regular languages, Distributed Computing, v.14 n.2, p.83-95, April 2001
	Alain Cournier , Ajoy K. Datta , Franck Petit , Vincent Villain, Optimal snap-stabilizing PIF algorithms in un-oriented trees, Journal of High Speed Networks, v.14 n.2, p.185-200, April 2005