Technical Report CS0853

TR#:CS0853
Class:CS
Title: COMPUTING WITH SNAKES IN DIRECTED NETWORKS OF AUTOMATA.
Authors: S. Even, A. Litman and P. Winkler
PDFCS0853.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}.
CopyrightThe 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.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion
admin