TY - GEN
T1 - On the runtime of universal coating for programmable matter
AU - Derakhshandeh, Zahra
AU - Gmyr, Robert
AU - Porter, Alexandra
AU - Richa, Andrea
AU - Scheideler, Christian
AU - Strothmann, Thim
N1 - Funding Information:
Z.Derakhshandeh, A.Porter and A.W.Richa?Supported in part by NSF grants CCF-1353089, CCF-1422603, and REU?026935.R.Gmyr, C.Scheideler and T.Strothmann?Supported in part by DFG grant SCHE 1592/3-1.
Publisher Copyright:
© Springer International Publishing Switzerland 2016.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2016
Y1 - 2016
N2 - Imagine coating buildings and bridges with smart particles (also coined smart paint) that monitor structural integrity and sense and report on traffic and wind loads, leading to technology that could do such inspection jobs faster and cheaper and increase safety at the same time.In this paper, we study the problem of uniformly coating objects of arbitrary shape in the context of self-organizing programmable matter, i.e., the programmable matter consists of simple computational elements called particles that can establish and release bonds and can actively move in a self-organized way.Particles are anonymous, have constant-size memory and utilize only local interactions in order to coat an object.We continue the study of our Universal Coating algorithm by focusing on its runtime analysis, showing that our algorithm terminates within a linear number of rounds with high probability.We also present a matching linear lower bound that holds with high probability.We use this lower bound to show a linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information, which implies that our algorithm is also optimal in a competitive sense.Simulation results show that the competitive ratio of our algorithm may be better than linear in practice.
AB - Imagine coating buildings and bridges with smart particles (also coined smart paint) that monitor structural integrity and sense and report on traffic and wind loads, leading to technology that could do such inspection jobs faster and cheaper and increase safety at the same time.In this paper, we study the problem of uniformly coating objects of arbitrary shape in the context of self-organizing programmable matter, i.e., the programmable matter consists of simple computational elements called particles that can establish and release bonds and can actively move in a self-organized way.Particles are anonymous, have constant-size memory and utilize only local interactions in order to coat an object.We continue the study of our Universal Coating algorithm by focusing on its runtime analysis, showing that our algorithm terminates within a linear number of rounds with high probability.We also present a matching linear lower bound that holds with high probability.We use this lower bound to show a linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information, which implies that our algorithm is also optimal in a competitive sense.Simulation results show that the competitive ratio of our algorithm may be better than linear in practice.
UR - http://www.scopus.com/inward/record.url?scp=84984919792&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84984919792&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-43994-5_10
DO - 10.1007/978-3-319-43994-5_10
M3 - Conference contribution
AN - SCOPUS:84984919792
SN - 9783319439938
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 148
EP - 164
BT - DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings
A2 - Rondelez, Yannick
A2 - Woods, Damien
PB - Springer Verlag
T2 - 22nd International Conference on Computing and Molecular Programming, DNA 2016
Y2 - 4 September 2016 through 8 September 2016
ER -