Faster Computation On Directed Networks of Automata
Title | Faster Computation On Directed Networks of Automata |
Publication Type | Technical Report |
Year of Publication | 1994 |
Authors | Ostrovsky, R., & Wilkerson D. |
Other Numbers | 907 |
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 for all these problems. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-037.pdf |
Bibliographic Notes | ICSI Technical Report TR-94-037 |
Abbreviated Authors | R. Ostrovsky and D. Wilkerson |
ICSI Publication Type | Technical Report |