2018/05/11 by Sarah Cannon, Cannon, Sarah, Joshua J. Daymude +7 · 1 citation
Mathematics · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #Distributed #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Mathematical Physics (math-ph) #Parallel #Random Matrices and Applications #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1805.04599
openalex publication_date 2018/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present and rigorously analyze the behavior of a distributed, stochastic\nalgorithm for separation and integration in self-organizing particle systems,\nan abstraction of programmable matter. Such systems are composed of individual\ncomputational particles with limited memory, strictly local communication\nabilities, and modest computational power. We consider heterogeneous particle\nsystems of two different colors and prove that these systems can collectively\nseparate into different color classes or integrate, indifferent to color. We\naccomplish both behaviors with the same fully distributed, local, stochastic\nalgorithm. Achieving separation or integration depends only on a single global\nparameter determining whether particles prefer to be next to other particles of\nthe same color or not; this parameter is meant to represent external,\nenvironmental influences on the particle system. The algorithm is a\ngeneralization of a previous distributed, stochastic algorithm for compression\n(PODC '16), which can be viewed as a special case of separation where all\nparticles have the same color. It is significantly more challenging to prove\nthat the desired behavior is achieved in the heterogeneous setting, however,\neven in the bichromatic case we focus on. This requires combining several new\ntechniques, including the cluster expansion from statistical physics, a new\nvariant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11),\nthe high-temperature expansion of the Ising model, and careful probabilistic\narguments.\n