Self-Stabilizing Algorithms in DAG Structured Networks

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Sajal K. Das Articles by Ajoy K. Datta Articles by Sebastien Tixeuil

1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99)

Fremantle, Australia

June 23-June 25

ISBN: 0-7695-0231-8

	ASCII Text	x
	Sajal K. Das, Ajoy K. Datta, Sebastien Tixeuil, "Self-Stabilizing Algorithms in DAG Structured Networks," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 190, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999.

	BibTex	x
	@article{ 10.1109/ISPAN.1999.778938, author = {Sajal K. Das and Ajoy K. Datta and Sebastien Tixeuil}, title = {Self-Stabilizing Algorithms in DAG Structured Networks}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1999}, issn = {1087-4089}, pages = {190}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778938}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - Self-Stabilizing Algorithms in DAG Structured Networks SN - 1087-4089 SP EP A1 - Sajal K. Das, A1 - Ajoy K. Datta, A1 - Sebastien Tixeuil, PY - 1999 KW - Distributed systems KW - self-stabilization KW - directed acyclic graphs KW - fault-tolerance VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Sajal K. Das, University of North Texas

Ajoy K. Datta, University of Nevada at Las Vegas

Sebastien Tixeuil, Universite de Paris Sud

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778938

This paper describes a parameterized protocol applicable to directed acyclic graph (DAG) topologies. The function parameter of the protocol is instantiated twice to design two protocols: (i) The topological sorting of the successor list at every node, and (ii) A shortest path routing table construction. Both protocols are self-stabilizing and thus they are resilient to transient failures and guarantee system recovery in a finite time linear in the network diameter. From the fact that a DAG topology can be imposed on a more general topology through graph labeling protocols, the solutions presented in this paper are expected to be quite useful for a large class of distributed systems, where an optimal routing along with the robustness and fault tolerance are key factors.

Index Terms:

Distributed systems, self-stabilization, directed acyclic graphs, fault-tolerance

Citation:

Sajal K. Das, Ajoy K. Datta, Sebastien Tixeuil, "Self-Stabilizing Algorithms in DAG Structured Networks," ispan, pp.190, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.