Faster Computation On Directed Networks of Automata
Rafail Ostrovsky, Daniel Wilkerson
Abstract: We show how an arbitrary strongly-connected {\em 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 |