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
Conference 19th International Conference on Distributed Computing and Networking, ICDCN 2018
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