On Two Phase Transitions of Relaxation Times in the Epidemic Data Gathering with Mobile Peers on Graphs

We consider an epidemic routing based data dissemination model with mobile peers performing close-range wireless communications each other. We focus on data gathering times of peers randomly wandering on graphs and investigated their probability distributions. We deal with the model mainly on finite and partially deformed two-dimensional square lattices by removing or adding edges. In finite graphs, the probability distribution obeys an exponential distribution whose decay speed is characterised by a relaxation time. We find that it universally appears two phase transitions of the relaxation time, meaning that the value of relaxation time varies drastically at a point with controlling the number of edges. We also find the approximate proportionality relationship between the relaxation times and diameters of the graphs.