How to Compute Times of Random Walks based Distributed Algorithms

Computer Science – Distributed – Parallel – and Cluster Computing

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

18 pages

Scientific paper

Random walk based distributed algorithms make use of a token that circulates in the system according to a random walk scheme to achieve their goal. To study their efficiency and compare it to one of the deterministic solutions, one is led to compute certain quantities, namely the hitting times and the cover time. Until now, only bounds on these quantities were defined. First, this paper presents two generalizations of the notions of hitting and cover times to weighted graphs. Indeed, the properties of random walks on symmetrically weighted graphs provide interesting results on random walk based distributed algorithms, such as local load balancing. Both of these generalization are proposed to precisely represent the behaviour of these algorithms, and to take into account what the weights represent. Then, we propose an algorithm to compute the n^2 hitting times on a weighted graph of n vertices, which we improve to obtain a O(n^3) complexity. This complexity is the lowest up to now. This algorithm computes both of the generalizations that we propose for the hitting times on a weighted graph. Finally, we provide the first algorithm to compute the cover time (in both senses) of a graph. We improve it to achieve a complexity of O(n^3 2^n). The algorithms that we present are all robust to a topological change in a limited number of edges. This property allows us to use them on dynamic graphs.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

How to Compute Times of Random Walks based Distributed Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How to Compute Times of Random Walks based Distributed Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How to Compute Times of Random Walks based Distributed Algorithms will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-749

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.