Time Optimal Self-Stabilizing Spanning Tree 
				Algorithms


	 	   Sudhanshu Aggarwal   and   Shay Kutten  
 	    
 	MIT Laboratory for Computer Science and IBM T.J. Watson Research Center

		 IBM T.J. Watson Research Center



	Abstract
   


	In this paper we present time-optimal self-stabilizing algorithms for asynchronous
distributed spanning tree computation in networks. We present both a randomized algorithm for 
anonymous networks as well as a deterministic version for ID-based networks. Our protocols are
the first to be time-optimal (i.e. stabilize in time O(diameter)) without any prior knowledge 
of the network size or diameter, assuming we are allowed messages of size O(ID). Both results 
are achieved through a new technique of symmetry breaking that may be of independent interest.