Computing with Snakes in Directed Networks of Automata (Extended Abstract)
Shimon Even, Ami Litman, Peter M. Winkler · Foundations of Computer Science · 1990
we consider directed, strongly connected netwoks of finite-state automata, of bounded in- and out-dep 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: constxuct smart spanning trees out from the root and in to the root; conduct breadth-fixst and depth-first searches: send a message from the end-point of a (directed) edge to its star-point; run a slow clock and sdve the firing squad synchronization problem. Our protocols are highly pdel and entail the use of sequences of signals which we call snakes. All of the tasks are accomplished in less time than is possible with any previously known techniques. The firing squad problem, in pmticular, was previously solvable only in exponential time; and backwards communication, by means of which undirected compuations can be simulated, was not known to be possible at all. In addition, we have protocols which will solve these problems for the first time in the case where the automata have no prior knowledge of which of their out-ports are connected to other automata and which are dummies, provided they have this knowledge about their in-ports.