•  
  •  
 

Author ORCID Identifier

https://orcid.org/0000-0002-1814-7612

DOI

10.22191/nejcs/vol7/iss1/9

Abstract

This paper explores the computational ability of ``distributed ghost" cellular automata (CA) \cite{10.1162/artl_e_00450} 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.

Download

Share

COinS