Concurrency vs. sequential interleavings in 1-D threshold cellular automata

Predrag Tosic, Gul A Agha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 non-trivial, 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.

Original languageEnglish (US)
Title of host publicationProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Pages2539-2546
Number of pages8
StatePublished - Dec 1 2004
EventProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM) - Santa Fe, NM, United States
Duration: Apr 26 2004Apr 30 2004

Publication series

NameProceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Volume18

Other

OtherProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
CountryUnited States
CitySanta Fe, NM
Period4/26/044/30/04

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Concurrency vs. sequential interleavings in 1-D threshold cellular automata'. Together they form a unique fingerprint.

Cite this