loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 7
Concurrency vs. Sequential Interleavings in 1-D Threshold Cellular Automata
Santa Fe, New Mexico
April 26-April 30
ISBN: 0-7695-2132-0
Predrag Tosic, University of Illinois at Urbana-Champaign
Gul Agha, University of Illinois at Urbana-Champaign
Cellular automata (CA) are an abstract model of fine-grain parallelism, as the node update operations are rather simple, and therefore comparable to the basic operations of the computer hardware. In a classical CA, all the nodes execute their operations in parallel, that is, (logically) simultaneously. We consider herewith the sequential version of CA, or SCA, and compare it with the classical, parallel CA. In particular, we show that there are 1-D CA with very simple node state update rules that cannot be simulated by any comparable SCA, irrespective of the node update ordering. While the result is trivial if one considers a single computation on a chosen input, we find it both nontrivial, and having some important and far-reaching implications when applied to all possible inputs and, moreover, to the entire nontrivial classes of CA (SCA). We also share some thoughts on how to extend our results herein, and we try motivate the study of genuinely asynchronous cellular automata.
Citation:
Predrag Tosic, Gul Agha, "Concurrency vs. Sequential Interleavings in 1-D Threshold Cellular Automata," ipdps, vol. 8, pp.179b, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 7, 2004
Usage of this product signifies your acceptance of the Terms of Use.