The dispersion time of random walks on finite graphs

Nicolás Rivera, Alexandre Stauffer, Thomas Sauerwald, John Sylvester

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

2 Citations (SciVal)


We study two random processes on an n-vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. These processes can also be regarded as protocols for allocating jobs in a distributed network of servers. In both processes n particles start from an arbitrary but fixed origin. Each particle performs a simple random walk until it first encounters an unoccupied vertex, at which point the vertex becomes occupied and the random walk terminates. In one of the processes, called Sequential-IDLA, a single particle moves until settling and only then does the next particle start whereas in the second process, called Parallel-IDLA, all unsettled particles move simultaneously. The second process is akin to running the first in parallel. Our main goal is to analyze the so-called dispersion time of these processes, which is the maximum number of steps performed by any of the n particles. In order to compare the two processes, we develop a coupling which shows the dispersion time of the Parallel-IDLA stochastically dominates that of the Sequential-IDLA; however, the total number of steps performed by all particles has the same distribution in both processes. This coupling also gives us that dispersion time of Parallel-IDLA is bounded in expectation by dispersion time of the Sequential-IDLA up to a multiplicative log n factor. Moreover, we derive asymptotic upper and lower bound on the dispersion time for several graph classes, such as cliques, cycles, binary trees, ddimensional grids, hypercubes and expanders. Most of our bounds are tight up to a multiplicative constant.

Original languageEnglish
Title of host publicationSPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures
Place of PublicationNew York, U. S. A.
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)9781450361842
Publication statusPublished - 17 Jun 2019
Event31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 - Phoenix, USA United States
Duration: 22 Jun 201924 Jun 2019


Conference31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
Country/TerritoryUSA United States


  • Interacting particle systems
  • Parallelization of random processes
  • Random Walks on Graphs

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software
  • Theoretical Computer Science


Dive into the research topics of 'The dispersion time of random walks on finite graphs'. Together they form a unique fingerprint.

Cite this