Abstract
We consider the rotor-router mechanism for distributing particles in an undirected graph. If the last particle passing through a vertex v took an edge (v,u), then the next time a particle is at v, it will leave v along the next edge (v,w) according to a fixed cyclic order of edges adjacent to v. The system works in synchronized steps and when two or more particles meet at the same vertex, they coalesce into one particle. A k-particle configuration of such a system is stable, if it does not lead to any coalescing. For 2 ≤ k ≤ n, we give the full characterization of stable k-particle configurations for cycles. We also show sufficient conditions for regular graphs with n vertices to admit n-particle stable configurations.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aldous, D., Fill, J.A.: Reversible markov chains and random walks on graphs 2002. Unfinished monograph, recompiled (2014). http://www.stat.berkeley.edu/~aldous/RWG/book.html
Aldous, D.J.: Meeting times for independent markov chains. Stochastic Processes and their Applications 38(2), 185–193 (1991)
Alon, N., Avin, C., Koucky, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. In: Proc. 20th Annual Symposium on Parallelism in Algorithms and Architectures, SPAA 2008, pp. 119–128. ACM (2008)
Bampas, E., Gąsieniec, L., Hanusse, N., Ilcinkas, D., Klasing, R., Kosowski, A.: Euler tour lock-in problem in the rotor-router model. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 423–435. Springer, Heidelberg (2009)
Bampas, E., Gasieniec, L., Klasing, R., Kosowski, A., Radzik, T.: Robustness of the rotor-router mechanism. In: Abdelzaher, T., Raynal, M., Santoro, N. (eds.) OPODIS 2009. LNCS, vol. 5923, pp. 345–358. Springer, Heidelberg (2009)
Bhatt, S.N., Even, S., Greenberg, D.S., Tayar, R.: Traversing directed eulerian mazes. J. Graph Algorithms Appl. 6(2), 157–173 (2002)
Chalopin, J., Das, S., Gawrychowski, P., Kosowski, A., Labourel, A., Uznanski, P.: Lock-in problem for parallel rotor-router walks. CoRR, abs/1407.3200 (2014)
Cooper, C., Elsässer, R., Ono, H., Radzik, T.: Coalescing random walks and voting on connected graphs. SIAM J. Discrete Math. 27(4), 1748–1758 (2013)
Cooper, C., Frieze, A.M., Radzik, T.: Multiple random walks in random regular graphs. SIAM J. Discrete Math. 23(4), 1738–1761 (2009)
Dereniowski, D., Kosowski, A., Pajak, D., Uznanski, P.: Bounds on the cover time of parallel rotor walks. In: 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014, pp. 263–275 (2014)
Efremenko, K., Reingold, O.: How well do random walks parallelize? In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol. 5687, pp. 476–489. Springer, Heidelberg (2009)
Elsässer, R., Sauerwald, T.: Tight bounds for the cover time of multiple random walks. Theor. Comput. Sci. 412(24), 2623–2641 (2011)
Israeli, A., Jalfon, M.: Token management schemes and random walks yield self-stabilizing mutual exclusion. In: Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, PODC 1990, pp. 119–131. ACM (1990)
Kosowski, A., Pająk, D.: Does adding more agents make a difference? A case study of cover time for the rotor-router. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 544–555. Springer, Heidelberg (2014)
Lovász, L., Plummer, D.: Matching Theory. AMS Chelsea Publishing Series. American Mathematical Soc. (2009)
Oliveira, R.: On the coalescence time of reversible random walks. Trans. Amer. Math. Soc. 364, 2109–2128 (2012)
Priezzhev, V.B., Dhar, D., Dhar, A., Krishnamurthy, S.: Eulerian walkers as a model of self-organized criticality. Phys. Rev. Lett. 77, 5079–5082 (1996)
Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Smell as a computational resource - A lesson we can learn from the ant. In: ISTCS, pp. 219–230 (1996)
Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Distributed covering by ant-robots using evaporating traces. IEEE T. Robotics and Automation 15(5), 918–933 (1999)
Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A distributed ant algorithm for efficiently patrolling a network. Algorithmica 37(3), 165–186 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Cooper, C., Radzik, T., Rivera, N., Shiraga, T. (2015). Coalescing Walks on Rotor-Router Systems. In: Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2015. Lecture Notes in Computer Science(), vol 9439. Springer, Cham. https://doi.org/10.1007/978-3-319-25258-2_31
Download citation
DOI: https://doi.org/10.1007/978-3-319-25258-2_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25257-5
Online ISBN: 978-3-319-25258-2
eBook Packages: Computer ScienceComputer Science (R0)