Understanding the importance of Atomicity property in Asynchronous Cellular Automata

To model distributed and concurrent systems, cellular automata (CA) researchers have introduced the notion of fully asynchronous cellular automata (ACA) with atomicity property where the automata system does not allow simultaneous update of two neighbouring cells. Moreover, this fully ACA also breaks the traditional notion of global clock in cellular automata. In this article, we introduce the notion of skew-asynchronous CA which questions the presence of atomicity property. That is, in the proposed skewed system, we allow simultaneous update of two-neighbouring cells. In fact, in the skewed system, we randomly choose one cell during each step of evolution, and update the corresponding chosen cell and its right neighbour. According to the initial experimental results, some con-vergent fully asynchronous elementary CA (ECA) systems show non-convergent (i.e., divergent) dynamics for skewed update. Moreover, some reversible ECA systems under fully asynchronous update reflect convergent dynamics under skewed update. This study also displays the brutal change in system dynamics for changing updating schemes (i.e., fully to skewed, or vice-versa) where the lattice size (say, n) plays a critical role, specifically, n ∈ 2N, n ∈ 3N and n ∈ 4N. This study also reports the theory behind the convergent skewed systems after considering homogeneous point attractors all 0 and all 1. For the non-convergent skewed systems, we report the communication class properties of reversible ECA 58-HGEDCB and semi-reversible ECA 26-HGECB as a case study. Lastly, we introduce the notion of correlated skew-asynchronous updating scheme to understand the microscopic details of the skewed systems which show important continuous (second-order) phase transition dynamics for many ECA rules.