Name
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 łog n factor. Moreover, we derive asymptotic upper and lower bound on the dispersion time for several graph classes, such as cliques, cycles, binary trees, d-dimensional grids, hypercubes and expanders. Most of our bounds are tight up to a multiplicative constant.
|
Year | Venue | Keywords |
|---|---|---|
2018 | The 31st ACM on Symposium on Parallelism in Algorithms and Architectures | interacting particle systems, parallelization of random processes, random walks on graphs |
Field | DocType | Volume |
Discrete mathematics,Diffusion-limited aggregation,Combinatorics,Vertex (geometry),Multiplicative function,Upper and lower bounds,Random walk,Stochastic process,Mathematics,Hypercube,Bounded function | Journal | abs/1808.09219 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Rivera | 1 | 27 | 8.52 |
| Alexandre O. Stauffer | 2 | 130 | 11.34 |
| Thomas Sauerwald | 3 | 0 | 2.37 |
| John Sylvester | 4 | 11 | 8.59 |