Understanding the importance of skew-asynchronous cellular automata

Abstract

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 the 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 that 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 cell and its right neighbour. According to the initial experimental results, some convergent fully asynchronous elementary CA (ECA) systems show non-convergent (i.e., divergent) dynamics under skewed update. Moreover, some reversible ECA systems under fully asynchronous update show 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,, and. This study also reports the theory behind the convergent skewed systems after considering homogeneous fixed points 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. © The Author(s), under exclusive licence to Springer Nature B.V. 2026.