Shape formation has been recently studied in distributed systems of programmable particles. In this paper we consider the shape recovery problem of restoring the shape when f of the n particles have crashed. We focus on the basic line shape, used as a tool for the construction of more complex configurations. We present a solution to the line recovery problem by the nonfaulty anonymous particles; the solution works regardless of the initial distribution and number f < n4 of faults, of the local orientations of the non-faulty entities, and of the number of non-faulty entities activated in each round (i.e., semi-synchronous adversarial scheduler).

Additional Metadata
Keywords Fault Tolerance, Mobile Agents, Programmable Matter
Persistent URL dx.doi.org/10.1145/3154273.3154309
Conference 19th International Conference on Distributed Computing and Networking, ICDCN 2018
Citation
Luna, G.A.D. (Giuseppe Antonio Di), Flocchini, P. (Paola), Prencipe, G. (Giuseppe), Santoro, N, & Viglietta, G. (Giovanni). (2018). Line recovery by programmable particles. In ACM International Conference Proceeding Series. doi:10.1145/3154273.3154309