SELF-STABILIZING DEPTH-FIRST MULTI-TOKEN CIRCULATION IN TREE NETWORKS

References

• Afek , Y. , Dolev , D. , Gafni , E. , Merritt , M. and Shavit , N. , A bounded first in first enabled solution to the l-exclusion problem. In: Proceedings of the 4th International Workshop on Distributed Algorithms, Lecture Notes in Computer Science , 486 , 422 – 431 , September , 1990 .
   Google Scholar
• Arora , A. , Dolev , S. and Gouda , M. ( 1992 ). Maintaining digital clocks in step. Parallel Processing Letters , 1 ( 1 ), 11 – 18 .
   Google Scholar
• Afek , Y. , Dolev , D. , Gafni , E. , Merritt , M. and Shavit , N. , A bounded first-in, firstenabled solution to the i-exclusion problem. ACM Trans. on Programming Languages and Systems , 16 ( 3 ), 939 – 953 , May , 1994 .
   Web of Science ®Google Scholar
• Brown , G. M. , Gouda , M. G. and Wu , C. L. , Token systems that self-stabilize. IEEE Trans. Comput. , 38 ( 6 ), 845 – 852 , June , 1989 .
   Web of Science ®Google Scholar
• Beauquier , J. and Johnen , C. ( 1995 ). Space efficient distributed self-stabilizing depth first token circulation. In: Proceedings of the 2nd Workshop on Self Stabilizing Systems , pp. 4.1 – 4.15 .
   Google Scholar
• Burns , J. and Pachl , J. ( 1989 ). Uniform stabilizing rings. ACM Transactions on Programming Languages and Systems , 11 ( 2 ), 330 – 344 .
   Web of Science ®Google Scholar
• Collin , Z. and Dolev , S. (1994). Self-stabilizing depth-first search. Information Processing Letters , 49, 297–301.
   Google Scholar
• Chandrasekar , S. and Srimani , P. K. ( 1994 ). A self-stabilizing distributed algorithm for all-pairs shortest path problem. Parallel Algorithms and Applications , 4 ( 1 & 2 ), 125 – 137 .
   Google Scholar
• Dolev , D. , Gafni , E. and Shavit , N. , Toward a non atomic era: l-exclusion as a test case. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing , pp. 78 – 92 , May , 1988 .
   Google Scholar
• Dijkstra , E. W. , Self-stabilizing systems in spite of distributed control. Communications of the ACM. , 17 ( 11 ), 643 – 644 , November , 1974 .
   Web of Science ®Google Scholar
• Dijkstra , E. W. ( 1986 ). A belated proof of self-stabilization. Distributed Computing , 1 ( 1 ), 5 – 6 .
   Web of Science ®Google Scholar
• Dolev , S. , Israeli , A. and Moran , S. ( 1993 ). Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing , 7 , 3 – 16 .
   Google Scholar
• Dolev , S. , Israeli , A. and Moran , S. , Resource bounds for self-stabilizing message driven protocols. SIAM J. Computing , 26 ( 1 ), 273 – 290 , February , 1997 .
   Web of Science ®Google Scholar
• Dolev , S. , Israeli , A and Moran , S. , Uniform dynamic self-stabilizing leader election. IEEE Trans. Parallel and Distributed Systems , 8 ( 4 ), 424 – 440 , April , 1997 .
   Web of Science ®Google Scholar
• Flatebo , M. and Datta , A. K. , Two state self stabilizing algorithms for token rings. IEEE Transactions on Software Engineering , 20 ( 6 ), 500 – 504 , June , 1994 .
   Web of Science ®Google Scholar
• Flatebo , M. , Datta , A. K. and Schoone , A. A. ( 1994 ). Self-stabilizing multi-token rings. Distributed Computing , 8 , 133 – 142 .
   Google Scholar
• Fischer , M. , Lynch , N. , Burns , I. and Borodin , A. , Distributed FIFO allocation of identical resources using small shared space. ACM Transactions on Programming Languages and Systems , 11 ( 1 ), 90 – 114 , January , 1989 .
   Web of Science ®Google Scholar
• Gouda , M. and Herman , T. ( 1990 ). Stabilizing unison. Inf Processing Letters , 35 ( 4 ), 171 – 175 .
   Web of Science ®Google Scholar
• Gouda , M. G. ( 1995 ). The triumph and tribulation of system stabilization. In: Proceedings of the Workshop on Distributed Algorithms and Graphs , pp. 1 – 18 .
   Google Scholar
• Huang , S. T. and Chen , N. S. ( 1993 ). Self-stabilizing depth-first token circulation on networks. Distributed Computing.
   Google Scholar
• Huang , S. T. and Wuu , L. -C. ( 1997 ). Self-stabilizing token circulation in uniform networks. Distributed Computing , 10 , 181 – 187 .
   Google Scholar
• Johnen , c. , Alari , G. , Beauquier , J. and Datta , A. K. ( 1997 ). Self-stabilizing depth-first token passing on rooted networks. In: Proceedings oj WDAG-97. ,
   Google Scholar
• Katz , S. and Perry , K. J. ( 1993 ). Self-stabilizing extensions for message passing systems. Distributed Computing , 7 ( 1 ), 17 – 26 .
   Web of Science ®Google Scholar
• Kruijer , H. S. M. ( 1979 ). Self-stabilization (in spite of distributed control) in treestructured systems. Inf, Processing Letters , 8 ( 2 ), 91 – 95 .
   Web of Science ®Google Scholar
• Lamport , L. ( 1984 ). Solved problems, unsolved problems, and non-problems in concurrency. In: Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing , pp. 1 – 11 .
   Google Scholar
• Peterson , G. , Observations on l-exclusion. In: Proceedings oj the 28th Allerton Conference on Communication, Control, and Computing , pp. 568 – 577 , October , 1990 .
   Google Scholar
• Schneider , M. , Self-stabilization. ACM Computing Surveys , 25 ( 1 ), 45 – 67 , March , 1993 .
   Web of Science ®Google Scholar
• Corresponding author. Tel.: (970) 491–7097, Fax: (970) 491-2466, e-mail: sritnani@cs. colostate.edu
   Google Scholar