How to Compute Times of Random Walks based Distributed Algorithms

• Autorzy: Bui A. , Sohier D.
• Języki publikacji: EN

Abstrakty

EN

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 known. 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 generalizations 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 n2 hitting times on a weighted graph of n vertices, which we improve to obtain a O(n3) 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(n32n). 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.

Słowa kluczowe

EN

distributed algorithms

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 4
• Strony: 363--378
• Opis fizyczny: bibliogr. 18 poz., rys.

Twórcy

autor

Bui A.

autor

Sohier D.

• SysCom-CReSTIC, Department de Mathematiques et Informatique, Université de Remis Champagne-Ardenne, BP1039 F-51687 Remis cedex, France,

Bibliografia

• [1] Aldous, D. J.: The random walk construction of uniform spanning trees and uniform labelled trees, SIAM Journal on Discrete Mathematics, 3(4), 1990, 450-465.
• [2] Bernard, T., Bui, A., Bui, M., Sohier, D.: A new method to automatically compute processing times for RandomWalks based Distributed Algorithms, International Symposium on Parallel and Distributed Computing, IEEE Comp. Soc. Press, 2003.
• [3] Bernard, T., Bui, A., Flauzac, O.: Topological adaptability for the distributed token circulation paradigm in faulty environment, International Symposium on Parallel and Distributed Processing and Applications, Lecture Notes on Computer Science 3358, Springer, 2004.
• [4] Bollobas, B.: Modern Graph Theory, Springer, 1998.
• [5] Brightwell, G., Winkler, P.: Maximum hitting Time for Random Wlaks on Graphs, J. Random Structures and Algorithms, 1(3), 1990, 263-276.
• [6] Bui, M., Das, S. K., Datta, A. K., Nguyen, D. T.: Randomized Mobile Agent Based Routing in Wireless Networks, International Journal of Foundations of Computer Science, 12(3), 2001, 365-384.
• [7] Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., Tiwari, P.: The Electrical Resistance of a Graph Captures its Commute and Cover Times, Computational Complexity, 6(4), 1997.
• [8] Coppersmith, D., Feige, U., Shearer, J.: Random Walks on Regular and Irregular Graphs, SIAM Journal on Discrete Mathematics, 9(2), 1996, 301-308.
• [9] Doyle, P. G., Snell, J. L.: Random Walks and Electric Networks, (first edition in 1984 by the Mathematical Association of America), 2000.
• [10] Feige, U.: A tight lower bound for the cover time of random walks on graphs, Random structures and algorithms, 6(4), 1995, 433-438.
• [11] Feige, U.: A tight upper bound for the cover time of random walks on graphs, Random structures and algorithms, 6(1), 1995, 51-54.
• [12] Feige, U., Rabinovich, Y.: Deterministic Approximation of the Cover Time, Random Structures and Algorithms, 23(1), 2003, 1-22.
• [13] Israeli, A., Jalfon,M.: Tokenmanagement schemes and randomwalks yield self-stabilizingmutual exclusion, 9th ACM symposium on Principles Of Distributed Computing, 1990.
• [14] Kahn, J., Kim, J. H., Lovász, L., Vu, V. H.: The Cover Time, the Blanket Time, and the Matthews Bound, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000.
• [15] Kemeny, J. G., Snell, J. L.: Finite Markov Chains, Springer-Verlag, 1976.
• [16] Lovász, L.: Random Walks on Graphs: A Survey, Combinatorics: Paul Erdos is Eighty (vol. 2) (T. S. ed. D. Miklós, V. T. Sós, Ed.), János Bolyai Mathematical Society, 1993.
• [17] Lv, Q., Caho, P., Cohen, E., Li, K., Shenker, S.: Search and Replication in Unstructured Peer-to-Peer Networks, International Conference on Supercomputing, 2002.
• [18] Tetali, P.: Random walks and effective resistance of networks, J. Theoretical Probability, 4(1), 1991, 101-109.