Rivera, Nicolas, Sauerwald, Thomas, Stauffer, Alexandre and Sylvester, John 
ORCID: 0000-0002-6543-2934
(2019)
The Dispersion Time of RandomWalks on Finite Graphs.
In: SPAA '19: 31st ACM Symposium on Parallelism in Algorithms and Architectures.
|
Text
Dispersion.pdf - Author Accepted Manuscript Download (817kB) | Preview |
Abstract
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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | Random Walks on Graphs, Parallelization of random processes, Interacting particle systems |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 14 Mar 2023 10:41 |
| Last Modified: | 14 Oct 2023 08:37 |
| DOI: | 10.1145/3323165.3323204 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3169003 |
Dimensions
Dimensions
