# Technical Report CS0853

 TR#: CS0853 Class: CS Title: COMPUTING WITH SNAKES IN DIRECTED NETWORKS OF AUTOMATA. Authors: S. Even, A. Litman and P. Winkler PDF CS0853.pdf Abstract: We consider directed, strongly connected networks of identical finite-state automata, of bounded in- and out-degree but unknown topology and unbounded size $n$. Protocols which are quadratic or linear in $n$ are provided which accomplish the following tasks: wake-up and report when done; construct spanning trees out from the root and into the root; conduct breadth-first and depth-first searches; send a message from the end-point of a (directed) edge to its start-point; run a slow clock; and solve the firing squad synchronization problem. Our protocols are highly parallel and use a new technique - a special kind of moving data structures we call {\em snakes}. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0853), rather than to the URL of the PDF files directly. The latter URLs may change without notice.