Faster Computation on Directed Networks of Automata
Author | : International Computer Science Institute |
Publisher | : |
Total Pages | : 26 |
Release | : 1994 |
Genre | : Computer network architectures |
ISBN | : |
Download Faster Computation on Directed Networks of Automata Book in PDF, ePub and Kindle
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(N2) algorithms of Even, Litman and Winkler [ELW-90] for all these problems."