Document Open Access Logo

A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems

Authors Sarah Cannon , Joshua J. Daymude , Cem Gökmen , Dana Randall, Andréa W. Richa

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.54.pdf
  • Filesize: 1.89 MB
  • 22 pages

Document Identifiers

Author Details

Sarah Cannon
  • Claremont McKenna College, Claremont, CA, USA
Joshua J. Daymude
  • Computer Science, CIDSE, Arizona State University, Tempe, AZ, USA
Cem Gökmen
  • Georgia Institute of Technology, Atlanta, GA, USA
Dana Randall
  • Georgia Institute of Technology, Atlanta, GA, USA
Andréa W. Richa
  • Computer Science, CIDSE, Arizona State University, Tempe, AZ, USA

Funding

  • Cannon, Sarah: Supported by National Science Foundation (NSF) award DMS-1803325.
  • Daymude, Joshua J.: Supported by NSF awards CCF-1422603, CCF-1637393, and CCF-1733680.
  • Gökmen, Cem: Supported by NSF award CCF-1733812.
  • Randall, Dana: Supported by NSF awards CCF-1526900, CCF-1637031, and CCF-1733812.
  • Richa, Andréa W.: Supported by NSF awards CCF-1422603, CCF-1637393, and CCF-1733680.

Cite AsGet BibTex

Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.54

Abstract

We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16) that can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Stochastic processes
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Self-organization
Keywords
  • Markov chains
  • Programmable matter
  • Cluster expansion

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Leonard M. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266(5187):1021-1024, 1994. Google Scholar
  2. Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A Stochastic Approach to Shortcut Bridging in Programmable Matter. Natural Computing, 17(4):723-741, 2018. Google Scholar
  3. Alexander I. Barvinok. Combinatorics and complexity of partition functions, volume 30 of Algorithms and Combinatorics. Springer International Publishing, 2016. Google Scholar
  4. Alexander I. Barvinok and Pablo Soberón. Computing the partition function for graph homomorphisms with multiplicities. Journal of Combinatorial Theory, Series A, 137:1-26, 2016. Google Scholar
  5. Prateek Bhakta, Sarah Miracle, and Dana Randall. Clustering and mixing times for segregation models on ℤ². In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 327-340, 2014. Google Scholar
  6. Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. A Markov chain algorithm for compression in self-organizing particle systems. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 279-288, Chicago, IL, USA, 2016. ACM. A significantly updated version is available at URL: https://arxiv.org/abs/1603.07991.
  7. David Correa, Athina Papadopoulou, Christophe Guberan, Nynika Jhaveri, Steffen Reichert, Achim Menges, and Skylar Tibbits. 3D-Printed Wood: Programming Hygroscopic Material Transformations. 3D Printing and Additive Manufacturing, 2(3):106-116, 2015. Google Scholar
  8. Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler. Computing by Programmable Particles. In Distributed Computing by Mobile Entities: Current Research in Moving and Computing, pages 615-681. Springer, Cham, 2019. Google Scholar
  9. Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: amoebot - a new model for programmable matter. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '14, pages 220-222, New York, NY, USA, 2014. ACM. Google Scholar
  10. Moon Duchin and Bridget E. Tenner. Discrete geometry for electoral geography. Preprint available online at https://arxiv.org/abs/1808.05860, 2018.
  11. William Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, New York, 1968. Google Scholar
  12. Sacha Friedli and Yvan Velenik. Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction. Cambridge University Press, Cambridge, 2018. Google Scholar
  13. Wilfred K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika, 57(1):97-109, 1970. Google Scholar
  14. Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov-Sinai Theory. In Proceedings of the 51st ACM Symposium on Theory of Computing, STOC '19. ACM, 2019. Google Scholar
  15. Gregory Herschlag, Han Sung Kang, Justin Luo, Christy V. Graves, Sachet Bangia, Robert Ravier, and Jonathan C. Mattingly. Quantifying Gerrymandering in North Carolina. Preprint available online at https://arxiv.org/abs/1801.03783, 2018.
  16. Michael A. Hogg and John C. Turner. Interpersonal attraction, social identification and psychological group formation. European Journal of Social Psychology, 15(1):51-66, 1985. Google Scholar
  17. Nicole Immorlica, Robert Kleinberg, Brendan Lucier, and Morteza Zadomighaddam. Exponential Segregation in a Two-dimensional Schelling Model with Tolerant Individuals. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 984-993, 2017. Google Scholar
  18. Ernst Ising. Beitrag zur theorie des ferromagnetismus [Contribution to the Theory of Ferromagnetism]. Zeitschrift für Physik, 31(1):253-258, 1925. Google Scholar
  19. Matthew Jenssen, Peter Keevash, and Will Perkins. Algorithms for #BIS-hard problems on expander graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 2235-2247, 2019. Google Scholar
  20. Brian R. Johnson, Ellen van Wilgenburg, and Neil D. Tsutsui. Nestmate recognition in social insects: overcoming physiological constraints with collective decision making. Behavioral Ecology and Sociobiology, 65(5):935-944, 2011. Google Scholar
  21. Roman Kotecký and David Preiss. Cluster Expansion for Abstract Polymer Models. Communications in Mathematical Physics, 103:491-498, 1986. Google Scholar
  22. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, Providence, RI, USA, 2009. Google Scholar
  23. Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. Counting independent sets and colorings on random regular bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, 2019. Google Scholar
  24. Eyal Lubetzky, Fabio Martinelli, Alan Sly, and Fabio Lucio Toninelli. Quasi-polynomial mixing of the 2D stochastic Ising model with "plus" boundary up to criticality. Journal of the European Mathematical Society (JEMS), 15(2):339–-386, 2013. Google Scholar
  25. Nancy Lynch. Distributed Algorithms. Morgan Kauffman, San Francisco, CA, USA, 1996. Google Scholar
  26. Fabio Martinelli and Fabio Lucio Toninelli. On the Mixing Time of the 2D Stochastic Ising Model with "Plus” Boundary Conditions at Low Temperature. Communications in Mathematical Physics, 296(1):175-213, 2010. Google Scholar
  27. Joseph E. Mayer. The Statistical Mechanics of Condensing Systems. I. The Journal of Chemical Physics, 5:67-73, 1937. Google Scholar
  28. Sarah Miracle, Dana Randall, and Amanda Pascoe Streib. Clustering in Interfering Binary Mixtures. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2011, pages 652-663, 2011. Google Scholar
  29. Hamed Omidvar and Massimo Franceschetti. Self-organized Segregation on the Grid. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC '17, pages 401-410, New York, NY, USA, 2017. ACM. Google Scholar
  30. T'ai H. Roulston, Grzegorz Buczkowski, and Jules Silverman. Nestmate discrimination in ants: effect of bioassay on aggressive behavior. Insectes Sociaux, 50(2):151-159, 2003. Google Scholar
  31. Michael Rubenstein, Alejandro Cornejo, and Radhika Nagpal. Programmable self-assembly in a thousand-robot swarm. Science, 345(6198):795-799, 2014. Google Scholar
  32. William Savoie, Sarah Cannon, Joshua J. Daymude, Ross Warkentin, Shengkai Li, Andréa W. Richa, Dana Randall, and Daniel I. Goldman. Phototactic Supersmarticles. Artificial Life and Robotics, 23(4):459-468, 2018. Google Scholar
  33. Thomas C. Schelling. Models of Segregation. The American Economic Review, 59(2):488-493, 1969. Google Scholar
  34. Thomas C. Schelling. Dynamic models of segregation. The Journal of Mathematical Sociology, 1(2):143-186, 1971. Google Scholar
  35. Philip S. Stewart and Michael J. Franklin. Physiological heterogeneity in biofilms. Nature Reviews Microbiology, 6:199-210, 2008. Google Scholar
  36. Rohan Thakker, Ajinkya Kamat, Sachin Bharambe, Shital Chiddarwar, and K. M. Bhurchandi. ReBiS - reconfigurable bipedal snake robot. In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 309-314, 2014. Google Scholar
  37. John C. Turner. Towards a cognitive redefinition of the social group. Cahiers de Psychologie Cognitive/Current Psychology of Cognition, 1(2):93-118, 1981. Google Scholar
  38. Dejan Vinković and Alan Kirman. A physical analogue of the Schelling model. Proceedings of the National Academy of Sciences, 103(51):19261-19265, 2006. Google Scholar
  39. Guopeng Wei, Connor Walsh, Irina Cazan, and Radu Marculescu. Molecular Tweeting: Unveiling the Social Network Behind Heterogeneous Bacteria Populations. In Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics, BCB '15, pages 366-375, New York, NY, USA, 2015. ACM. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact