A set of identical particles is deployed on an infinite line. Each particle moves freely on the line at arbitrary but constant speed. When two particles come into contact they bounce acquiring new velocities according to the law of mechanics for elastic collisions. Each particle initially holds a piece of information. The meeting particles automatically transmit to each other their entire currently possessed information (i.e., the initial one and the one accumulated by means of previous collisions). Due to the fact that the number of collisions in this setting is finite [1] communication cannot last forever. This raises some interesting questions which we address in this paper: Will particle p j ever obtain the initial information of p i ? Are colliding particles able to perform broadcasting, convergecast, or gossiping? We establish necessary and sufficient conditions for any pair of particles to communicate as well as those needed to achieve gossiping, convergecast, and broadcasting. Although these conditions clearly depend on the initial ordering of the particles along the line, we prove that they are independent of their starting positions. Further, we show how to efficiently decide whether some of the aforementioned communication primitives can take place. Finally we explain how to compute the necessary time to carry out all these communication protocols and we describe a relationship between our problem and an important, longstanding open question in computational geometry.

Additional Metadata
Keywords Broadcasting, Communication, Convergecast, Elastic collisions, Gossiping, Mobile agents, Particles, Passive mobility, Synchronous systems
Persistent URL dx.doi.org/10.1007/978-3-319-25258-2_20
Citation
Czyzowicz, J. (Jurek), Kranakis, E, Pacheco, E. (Eduardo), & Pająk, D. (Dominik). (2015). Information spreading by mobile particles on a line. doi:10.1007/978-3-319-25258-2_20