The dispersion time of random walks on finite graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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
Pages103-113
Number of pages11
ISBN (Electronic)9781450361842
DOIs
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

Conference

Conference31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
CountryUSA United States
CityPhoenix
Period22/06/1924/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

Rivera, N., Stauffer, A., Sauerwald, T., & Sylvester, J. (2019). The dispersion time of random walks on finite graphs. In 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.

SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures. New York, U. S. A. : Association for Computing Machinery, 2019. p. 103-113.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Rivera, N, Stauffer, A, Sauerwald, T & Sylvester, J 2019, The dispersion time of random walks on finite graphs. in 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
Rivera N, Stauffer A, Sauerwald T, Sylvester J. The dispersion time of random walks on finite graphs. In SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures. New York, U. S. A.: Association for Computing Machinery. 2019. p. 103-113 https://doi.org/10.1145/3323165.3323204
Rivera, Nicolás ; Stauffer, Alexandre ; Sauerwald, Thomas ; Sylvester, John. / The dispersion time of random walks on finite graphs. SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures. New York, U. S. A. : Association for Computing Machinery, 2019. pp. 103-113
@inproceedings{4846f3c2979c47569a215d0e83a5afa9,
title = "The dispersion time of random walks on finite graphs",
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.",
keywords = "Interacting particle systems, Parallelization of random processes, Random Walks on Graphs",
author = "Nicol{\'a}s Rivera and Alexandre Stauffer and Thomas Sauerwald and John Sylvester",
year = "2019",
month = "6",
day = "17",
doi = "10.1145/3323165.3323204",
language = "English",
pages = "103--113",
booktitle = "SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures",
publisher = "Association for Computing Machinery",
address = "USA United States",

}

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 -