#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"
}