• On time analysis of random wal...

Treffer: On time analysis of random walk based token circulation algorithms

Title:
On time analysis of random walk based token circulation algorithms
Authors:
BUI, Alain, SOHIER, Devan
Source:
Advanced distributed systems (5th international school and symposium, ISSADS 2005, Guadalajara, Mexico, January 24-28, 2005, revised selected lectures)Lecture notes in computer science. :63-71
Publisher Information:
New York, NY: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 10 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Algorithme réparti, Distributed algorithm, Algoritmo repartido, Analyse temporelle, Time analysis, Análisis temporal, Approche probabiliste, Probabilistic approach, Enfoque probabilista, Calcul réparti, Distributed computing, Cálculo repartido, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Complexité temps, Time complexity, Complejidad tiempo, Marche aléatoire, Random walk, Marcha aleatoria, Modélisation, Modeling, Modelización, Processus stochastique, Stochastic process, Proceso estocástico, Système réparti, Distributed system, Sistema repartido
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
CReSTIC-LICA, Université de Reims Champagne Ardenne, BP1039, 51687 Reims, France
LRIA - EPHE rue G. Lussac, 75005 Paris, France
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17182602
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17182602
Database:
PASCAL Archive

Weitere Informationen

The problem of evaluating time complexity of random distributed algorithms is considered. A common and natural way to randomize a distributed algorithm is to use random walks i.e. memoryless stochastic processes: a token message circulates in the system and, at each step, the node that owns it sends it to one of its neighbors chosen at random. The token usually contains some pieces of information or part of the result of some distributed computing for instance. In this paper we focus on the cover time, defined by the expected time to visit all nodes in the system. This quantity often appears in the complexity of random walk based distributed algorithms. We provide a general method to compute the cover time on any arbitrary graph modeling a distributed system.