Projects per year
Abstract
We study two random processes on an nvertex 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 SequentialIDLA, a single particle moves until settling and only then does the next particle start whereas in the second process, called ParallelIDLA, all unsettled particles move simultaneously. The second process is akin to running the first in parallel. Our main goal is to analyze the socalled 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 ParallelIDLA stochastically dominates that of the SequentialIDLA; 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 ParallelIDLA is bounded in expectation by dispersion time of the SequentialIDLA 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 language  English 

Title of host publication  SPAA 2019  Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures 
Place of Publication  New York, U. S. A. 
Publisher  Association for Computing Machinery 
Pages  103113 
Number of pages  11 
ISBN (Electronic)  9781450361842 
DOIs  
Publication status  Published  17 Jun 2019 
Event  31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019  Phoenix, USA United States Duration: 22 Jun 2019 → 24 Jun 2019 
Conference
Conference  31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 

Country/Territory  USA United States 
City  Phoenix 
Period  22/06/19 → 24/06/19 
Keywords
 Interacting particle systems
 Parallelization of random processes
 Random Walks on Graphs
ASJC Scopus subject areas
 Hardware and Architecture
 Software
 Theoretical Computer Science
Fingerprint
Dive into the research topics of 'The dispersion time of random walks on finite graphs'. Together they form a unique fingerprint.Projects
 1 Finished

Early Career Fellowship  Mathematical Analysis of Strongly Correlated Processes on Discrete Dynamic Structures
Stauffer, A.
Engineering and Physical Sciences Research Council
1/04/16 → 30/09/22
Project: Research council