#Number
TR-PDS-2001-005

#Title
A Rigorous Proof of $O(n^2)$ Bound on the Number of Moves 
for Stabilization of Dijkstra's 3-State Algorithm

#Author
Neeraj Mittal,
Vijay K. Garg

#Abstract 
We give a rigorous proof of $O(n^2)$ bound on the number of moves
Dijkstra's 3-state self-stabilizing algorithm for token-ring takes to
reach a legal state.  To our knowledge, ours is the first formal
proof of the $O(n^2)$ bound.

	
#Bib
@techreport{TR-PDS-2001-005,
  author = 	 "Neeraj Mittal and Vijay K. Garg",
  title = 	 "A Rigorous Proof of $O(n^2)$ Bound on the Number of
                  Moves for Stabilization of Dijkstra's 3-State Algorithm",
  instituition = "The University of Texas at Austin",
  year = 	 "2001",
  number =	 "TR-PDS-2001-005",
  note =	 "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-2001-005"
}