A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

被引:26
作者
Cannon, Sarah [1 ]
Daymude, Joshua J. [2 ]
Randall, Dana [1 ]
Richa, Andrea W. [2 ]
机构
[1] Georgia Inst Technol, Atlanta, GA 30332 USA
[2] Arizona State Univ, Tempe, AZ USA
来源
PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'16) | 2016年
基金
美国国家科学基金会;
关键词
Self-organizing Particles; Compression; Markov Chains; AGGREGATION;
D O I
10.1145/2933057.2933107
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider programmable matter as a collection of simple computational elements (or particles) with limited (constant size) memory that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers 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 perimeter. 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 with no holes. The algorithm takes as input a bias parameter lambda, where lambda > 1 corresponds to particles favoring inducing more lattice triangles within the particle system. We show that for all lambda > 5, there is a constant alpha > 1 such that at stationarity with all but exponentially small probability the particles are alpha-compressed, meaning the perimeter of the system configuration is at most alpha . p(min), where p(min) is the minimum possible perimeter of the particle system. We additionally prove that the same algorithm can be used for expansion for small values of A lambda in particular, for all 0 < lambda < root 2 there is a constant beta < 1 such that at stationarity, with all but an ex ponentially small probability, the perimeter will be at least beta . p(max) where p(max) is the maximum possible perimeter.
引用
收藏
页码:279 / 288
页数:10
相关论文
共 20 条
[1]  
[Anonymous], 1996, Distributed algorithms
[2]  
Bampas E, 2010, LECT NOTES COMPUT SC, V6343, P297, DOI 10.1007/978-3-642-15763-9_28
[3]  
Borgs C., 1999, PROC IEEE FOCS, P218
[4]  
Camazine S., INSECTES SOCIAUX, V46, P348
[5]  
Chavoya A., GEN EV COMP C GECCO
[6]  
Derakhshandeh Zahra, 2015, DNA Computing and Molecular Programming. 21st International Conference, DNA 21. Proceedings 9211, P117, DOI 10.1007/978-3-319-21999-8_8
[7]  
Derakhshandeh Z., 2016, 28 ACM S PA IN PRESS
[8]  
Derakhshandeh Z, 2015, P 2 ANN INT C NAN CO
[9]  
Deutsch A., 2007, MODELING SIMULATION
[10]  
Dobrushin RL, 1968, FUNCT ANAL APPL, V2, P302, DOI DOI 10.1007/BF01075682