**
Faster Computation On Directed Networks of Automata
**

*
Rafail Ostrovsky, Wilkarson
*

**
Abstract:
**

We show how an arbitrary strongly-connected *directed* network of
synchronous finite-state automata (with bounded in- and out-degree)
can accomplish a number of basic distributed network tasks in
O(ND) time, where D is the diameter of the network and N is the
number of processors. The tasks include (among others) the Firing
*Synchronization* Problem; Network Search and Traversal; building
outgoing and incoming Spanning Trees; Wake-up and Report When Done;
and simulating a step of an undirected network protocol for the
underlying graph of the directed network. Our approach compares
favorably to the best previously known O(N^{2}) algorithms of Even,
Litman and Winkler [ELW-90] for all these problems.

**comment:**
Preliminary version appeared in the
Proceedings of Fourteenth Annual ACM Symposium on
Principles of Distributed Computing
(PODC-95)
Journal version accepted to Journal of Algorithms, to appear.

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |