Computing with Snakes in Directed Networks of Automata

✍ Scribed by Shimon Even; Ami Litman; Peter Winkler

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 146 KB
• Volume: 24
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0840

✦ Synopsis

We consider unidirectional, 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 in to the root; conduct breadth-first and depth-first searches; Ž . send a message from the end-point of an unidirectional arc 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 structure we call a snake.