Communication on networks of finite automata: Three instances of wormhole routing

We address three problems involving wormhole routing on networks of finite automata. First we consider a generalization of the classic firing synchronization problem: How fast can an arbitrary strongly-connected directed network of automata globally synchronize? For an N node diameter D network we improve the best known time to {dollar}O(ND){dollar} from the previous {dollar}O(Nsp2).{dollar} Second: Can one host computer determine the topology of a wormhole-routed network by probing it with test messages? We prove the correctness of an algorithm of Mainwaring and Culler to do this. Third: How fast can we route a batch of messages across a greedy oblivious wormhole-routed network? We exhibit a simple randomized online algorithm to do this. Specifically, on the N-input butterfly under a random heavy load of long (network-depth) worms it routes in O (log{dollar}sp3{dollar} N log log N) time, improving the previous best of O (log{dollar}sp4 N).{dollar} We also show an almost-matching lower bound of {dollar}Omega({lcub}{lcub}rm log{rcub}sp3 Nover({lcub}rm log log{rcub} N)sp2{rcub}).{dollar} Our work shows that wormhole routing on butterflies is asymptotically less bandwidth efficient than packet routing.