Abstract
In this paper, we revisit the problem of classical meeting times of random walks in graphs. In the process that two tokens (called agents) perform random walks on an undirected graph, the meeting times are defined as the expected times until they meet when the two agents are initially located at different vertices. A key feature of the problem is that, in each discrete time-clock (called round) of the process, the scheduler selects only one of the two agents, and the agent performs one move of the random walk. In the adversarial setting, the scheduler utilizes the strategy that intends to maximizing the expected time to meet. In the seminal papers [5, 11, 18], for the random walks of two agents, the notion of atomicity is implicitly considered. That is, each move of agents should complete while the other agent waits. In this paper, we consider and formalize the meeting time of non-atomic random walks. In the non-atomic random walks, we assume that in each round, only one agent can move but the move does not necessarily complete in the next round. In other words, we assume that an agent can move at a round while the other agent is still moving on an edge. For the non-atomic random walks with the adversarial schedulers, we give a polynomial upper bound on the meeting times.
This paper was supported by ANR project SAPPORO (Ref. 2019-CE25-0005-1). The full version of this article is available on arXiv.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bampas, E., et al.: On asynchronous rendezvous in general graphs. Theoret. Comput. Sci. 753, 80–90 (2019). https://doi.org/10.1016/j.tcs.2018.06.045
Brightwell, G., Winkler, P.: Maximum hitting time for random walks on graphs. Random Struct. Algorithms 1(3), 263–276 (1990). https://doi.org/10.1002/rsa.3240010303
Bshouty, N.H., Higham, L., Warpechowska-Gruca, J.: Meeting times of random walks on graphs. Inf. Process. Lett. 69(5), 259–265 (1999). https://doi.org/10.1016/S0020-0190(99)00017-4
Cooper, C., Elsässer, R., Ono, H., Radzik, T.: Coalescing random walks and voting on connected graphs. SIAM J. Discret. Math. 27(4), 1748–1758 (2013). https://doi.org/10.1137/120900368
Coppersmith, D., Tetali, P., Winkler, P.: Collisions among random walks on a graph. SIAM J. Discret. Math. 6(3), 363–374 (1993). https://doi.org/10.1137/0406029
Czyzowicz, J., Pelc, A., Labourel, A.: How to meet asynchronously (almost) everywhere. ACM Trans. Algorithms 8(4), 1–14 (2012). https://doi.org/10.1145/2344422.2344427
De Marco, G., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. In: Jȩdrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 271–282. Springer, Heidelberg (2005). https://doi.org/10.1007/11549345_24
Feige, U.: A tight upper bound on the cover time for random walks on graphs. Random Struct. Algorithms 6(1), 51–54 (1995). https://doi.org/10.1002/rsa.3240060106
Guilbault, S., Pelc, A.: Asynchronous rendezvous of anonymous agents in arbitrary graphs. In: Fernàndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol. 7109, pp. 421–434. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25873-2_29
Hassin, Y., Peleg, D.: Distributed probabilistic polling and applications to proportionate agreement. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 402–411. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48523-6_37
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, pp. 119–131 (1990)
Kahn, J.D., Linial, N., Nisan, N., Saks, M.E.: On the cover time of random walks on graphs. J. Theor. Probab. 2, 121–128 (1989)
Kanade, V., Mallmann-Trenn, F., Sauerwald, T.: On coalescence time in graphs-when is coalescing as fast as meeting? ACM Trans. Algorithms 19(2), 1–46 (2023). https://doi.org/10.1145/3576900
Lovász, L.: Random walks on graphs. Comb. Paul Erdos Eighty 2, 1–46 (1993)
Oliveira, R.I., Peres, Y.: Random walks on graphs: new bounds on hitting, meeting, coalescing and returning. In: 2019 Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, pp. 119–126 (2019). https://doi.org/10.1137/1.9781611975505.13
Tetali, P.: Random walks and the effective resistance of networks. J. Theor. Probab. 4, 101–109 (1991)
Tetali, P., Winkler, P.: On a random walk problem arising in self-stabilizing token management. In: Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, pp. 273–280. Association for Computing Machinery (1991). https://doi.org/10.1145/112600.112623
Tetali, P., Winkler, P.: Simultaneous reversible Markov chains. Comb. Paul Erdos Eighty 1 (1993)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Eguchi, R., Ooshita, F., Inoue, M., Tixeuil, S. (2023). Meeting Times of Non-atomic Random Walks. In: Dolev, S., Schieber, B. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2023. Lecture Notes in Computer Science, vol 14310. Springer, Cham. https://doi.org/10.1007/978-3-031-44274-2_22
Download citation
DOI: https://doi.org/10.1007/978-3-031-44274-2_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-44273-5
Online ISBN: 978-3-031-44274-2
eBook Packages: Computer ScienceComputer Science (R0)