Memorias de investigación
Ponencias en congresos:
Node Sampling Using Random Centrifugal Walks
Año:2012
Áreas de investigación
  • Tecnología electrónica y de las comunicaciones,
  • Ciencias de la computación y tecnología informática
Datos
Descripción
Sampling a network with a given probability distribution has been identified as a useful operation. In this paper we propose distributed algorithms for sampling networks, so that nodes are selected by a special node, called the source, with a given probability distribution. All these algorithms are based on a new class of random walks, that we call Random Centrifugal Walks (RCW). A RCW is a random walk that starts at the source and always moves away from it. Firstly, an algorithm to sample any connected network using RCW is proposed. The algorithm assumes that each node has a weight, so that the sampling process must select a node with a probability proportional to its weight. This algorithm requires a preprocessing phase before the sampling of nodes. In particular, a minimum diameter spanning tree (MDST) is created in the network, and then nodes? weights are efficiently aggregated using the tree. The good news are that the preprocessing is done only once, regardless of the number of sources and the number of samples taken from the network. After that, every sample is done with a RCW whose length is bounded by the network diameter. Secondly, RCW algorithms that do not require preprocessing are proposed for grids and networks with regular concentric connectivity, for the case when the probability of selecting a node is a function of its distance to the source. The key features of the RCW algorithms (unlike previous Markovian approaches) are that (1) they do not need to warm-up (stabilize), (2) the sampling always finishes in a number of hops bounded by the network diameter, and (3) it selects a node with the exact probability distribution.
Internacional
Si
Nombre congreso
16th International Conference, OPODIS 2012, Principles of Distributed Systems
Tipo de participación
960
Lugar del congreso
Roma, Italia
Revisores
Si
ISBN o ISSN
978-3-642-35475-5
DOI
10.1007/978-3-642-35476-2_21
Fecha inicio congreso
18/12/2012
Fecha fin congreso
20/12/2012
Desde la página
300
Hasta la página
314
Título de las actas
Principles of Distributed Systems Lecture Notes in Computer Science Volume 7702, 2012
Esta actividad pertenece a memorias de investigación
Participantes
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Internet de Nueva Generación
  • Departamento: Informática Aplicada