A Markov chain algorithm for compression in self-organizing particle systems

DOI10.1145/2933057.2933107MaRDI QIDQ5361946zbMATH OpenOpenAlexFDO

Authors Sarah Cannon, Joshua J. Daymude, Dana Randall, Andrea Richa

Publication date 29 September 2017

Published in Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.07991

zbMATH Keywords

compressionMarkov chainsself-organizing particles

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)

Abstract: In systems of programmable matter, we are given a collection of simple computation elements (or particles) with limited (constant-size) memory. We are interested in when they can self-organize to solve system-wide problems of movement, configuration and coordination. Here, we initiate a stochastic approach to developing robust distributed algorithms for programmable matter systems using Markov chains. We are able to leverage the wealth of prior work in Markov chains and related areas to design and rigorously analyze our distributed algorithms and show that they have several desirable properties. We study the compression problem, in which a particle system must gather as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. More specifically, we seek fully distributed, local, and asynchronous algorithms that lead the system to converge to a configuration with small boundary. We present a Markov chain-based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration. The algorithm takes as input a bias parameter $lambda$, where $lambda>1$ corresponds to particles favoring having more neighbors. We show that for all $lambda>2+sqrt2$, there is a constant $alpha>1$ such that eventually with all but exponentially small probability the particles are $alpha$-compressed, meaning the perimeter of the system configuration is at most $alphacdot{p}_{min}$, where $p_{min}$ is the minimum possible perimeter of the particle system. Surprisingly, the same algorithm can also be used for expansion when $0<lambda<2.17$, and we prove similar results about expansion for values of $lambda$ in this range. This is counterintuitive as it shows that particles preferring to be next to each other ($lambda>1$) is not sufficient to guarantee compression.

Recommendations

• Shape formation by programmable particles
• Shape formation by programmable particles
• Leader election and shape formation with self-organizing programmable matter
• Improved Leader Election for Self-organizing Programmable Matter

Cited in

(13)

• Shape formation by programmable particles
• Shape formation by programmable particles
• A Compression Algorithm for Probability Transition Matrices
• Improved Leader Election for Self-organizing Programmable Matter
• scientific article; zbMATH DE number 7561256 (Why is no real title available?)
• The Synergy of Finite State Machines
• Deterministic Leader Election in Programmable Matter
• scientific article; zbMATH DE number 7650121 (Why is no real title available?)
• The canonical amoebot model: algorithms and concurrency control
• Existence of a phase transition in harmonic activation and transport
• Irreducibility of recombination Markov chains in the triangular lattice
• Stationary and deterministic leader election in self-organizing particle systems
• Adaptive collective responses to local stimuli in anonymous dynamic networks

This page was built for publication: A Markov chain algorithm for compression in self-organizing particle systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361946)