COMPUTING WITH SNAKES IN DIRECTED NETWORKS OF AUTOMATA

We consider unidirectional, strongly connected networks of identical f inite-state automata, of bounded in- and out-degree but unknown topolo gy 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 in to the ro ot; conduct breadth-first and depth-first searches; send a message fro m the end-point of an (unidirectional) are to its start-point; run a s low clock; and solve the firing squad synchronization problem. Our pro tocols are highly parallel and use a new technique-a special kind of m oving data structure we call a snake. (C) 1997 Academic Press.