### 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.

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 | 103-113 |

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 | 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

### Cite this

*SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures*(pp. 103-113). New York, U. S. A.: Association for Computing Machinery. https://doi.org/10.1145/3323165.3323204

**The dispersion time of random walks on finite graphs.** / Rivera, Nicolás; Stauffer, Alexandre; Sauerwald, Thomas; Sylvester, John.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures.*Association for Computing Machinery, New York, U. S. A., pp. 103-113, 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, USA United States, 22/06/19. https://doi.org/10.1145/3323165.3323204

}

TY - GEN

T1 - The dispersion time of random walks on finite graphs

AU - Rivera, Nicolás

AU - Stauffer, Alexandre

AU - Sauerwald, Thomas

AU - Sylvester, John

PY - 2019/6/17

Y1 - 2019/6/17

N2 - 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.

AB - 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.

KW - Interacting particle systems

KW - Parallelization of random processes

KW - Random Walks on Graphs

UR - http://www.scopus.com/inward/record.url?scp=85068656302&partnerID=8YFLogxK

U2 - 10.1145/3323165.3323204

DO - 10.1145/3323165.3323204

M3 - Conference contribution

SP - 103

EP - 113

BT - SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

CY - New York, U. S. A.

ER -