The "Distributed Ghost" with independence - a study on computational ability of skewed asynchronous cellular automata

This paper explores the computational ability of “distributed ghost” cellular automata (CA) [14] after introducing independence in the updating scheme. Traditionally, the CA system dictates all cells to update together following the concept of the global clock. To introduce independence in the system, CA researchers have introduced the notion of fully asynchronous updating scheme with atomicity property where, again, the CA system dictates two neighbouring cells not to update together. In this study, we explore the skewed asynchronous system after breaking the atomicity property. Specifically, we study the computational ability of the proposed skewed asynchronous system in the context of the density classification problem. In this direction, the first theoretical study includes identification of two attractor (all 0 and all 1) skewed asynchronous system (here, 13 candidate ECA rules) after considering the problem statement of density classification. Next, following the basins of attraction dynamics of the two attractor systems, we consider ECA rules 170, 178 and 184 as candidates for this distributed consensus problem. Finally, we demonstrate the computational ability (i.e., efficiency) of the proposed cellular system with independence during density classification.