Understanding the importance of Atomicity property in Asynchronous Cellular Automata

Understanding the importance of Atomicity property in Asynchronous Cellular Automata | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Understanding the importance of Atomicity property in Asynchronous Cellular Automata Souvik Roy This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6374852/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 9 You are reading this latest preprint version 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 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. Asynchronous Cellular Automata (ACA) Atomicity property Fully ACA Skew-ACA Phase transition Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Editorial decision: Revision requested 07 Aug, 2025 Reviews received at journal 07 Aug, 2025 Reviews received at journal 14 Jun, 2025 Reviewers agreed at journal 09 May, 2025 Reviewers agreed at journal 09 May, 2025 Reviewers invited by journal 08 May, 2025 Editor assigned by journal 05 Apr, 2025 Submission checks completed at journal 05 Apr, 2025 First submitted to journal 04 Apr, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-6374852","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":454348253,"identity":"49cf1d18-f438-4893-a302-c72ee6a17ce0","order_by":0,"name":"Souvik Roy","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA+0lEQVRIiWNgGAWjYLCChAMgkvkAMwMbAwgxSIARYS1sCSRoYQBr4TEAa2FgIKBevr3HTOLBGYZ8fomcj58Lyg7n8TEwH7zNw2CRh0uLwZkzZhIJNxgsZ87I3Sw949zhYjYGtmRrHgaJYpxaJHKMDRI+MBgY3MjdIM3bdjixjYHHTBqoJbEBl8NmwLXkPP4N0cL/Da8Whhs5hg+ADgNpYYPZwoZXi8GZY4UPEs5IGEj2PDOz5jmXntjGzGZsOccAj8Pamzcc/HHMxoCfPfnxbZ4y68T57c0Pb7ypqMPtMAgARoRAApTNDLYdv3oI4D9AjKpRMApGwSgYiQAAv0BP+1te2MMAAAAASUVORK5CYII=","orcid":"","institution":"Ahmedabad University","correspondingAuthor":true,"prefix":"","firstName":"Souvik","middleName":"","lastName":"Roy","suffix":""}],"badges":[],"createdAt":"2025-04-04 09:23:17","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6374852/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6374852/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":82627580,"identity":"6d73638d-dbcc-4ccb-8e82-c9486e0cb08f","added_by":"auto","created_at":"2025-05-13 13:13:46","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":2314918,"visible":true,"origin":"","legend":"","description":"","filename":"NaturalComputingROY.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6374852/v1_covered_3e52718d-e972-4e03-b058-a9ae081f73bf.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Understanding the importance of Atomicity property in Asynchronous Cellular Automata","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"natural-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"naco","sideBox":"Learn more about [Natural Computing](http://link.springer.com/journal/11047)","snPcode":"11047","submissionUrl":"https://submission.nature.com/new-submission/11047/3","title":"Natural Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Asynchronous Cellular Automata (ACA), Atomicity property, Fully ACA, Skew-ACA, Phase transition","lastPublishedDoi":"10.21203/rs.3.rs-6374852/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6374852/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"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.","manuscriptTitle":"Understanding the importance of Atomicity property in Asynchronous Cellular Automata","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-05-13 13:05:37","doi":"10.21203/rs.3.rs-6374852/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-08-07T15:07:01+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-08-07T13:39:40+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-06-14T12:18:09+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"47640901969305204202034998733799537168","date":"2025-05-09T13:13:54+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"75405403308170229527434222080657440571","date":"2025-05-09T04:30:44+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-05-08T08:36:13+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-04-05T19:28:46+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-04-05T09:48:59+00:00","index":"","fulltext":""},{"type":"submitted","content":"Natural Computing","date":"2025-04-04T09:14:23+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"natural-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"naco","sideBox":"Learn more about [Natural Computing](http://link.springer.com/journal/11047)","snPcode":"11047","submissionUrl":"https://submission.nature.com/new-submission/11047/3","title":"Natural Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"50ef685e-d682-450a-8f4f-06e164e98354","owner":[],"postedDate":"May 13th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-05-18T09:25:39+00:00","versionOfRecord":[],"versionCreatedAt":"2025-05-13 13:05:37","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-6374852","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6374852","identity":"rs-6374852","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}