Biased Selection for Building Small-World Networks

Sevilla de Pablo, Andrés; Mozo Velasco, Alberto; Lorenzo Prieto, Maria Araceli; López Presa, Jose Luis; Manzano García, Pilar y Fernández Anta, Antonio (2010). Biased Selection for Building Small-World Networks. En: "14th international conference on Principles of distributed systems, OPODIS 2010", 14/11/2010 - 17/11/2010, Tozeur, Túnez. ISBN 978-3-642-17652-4.

Descripción

Título: Biased Selection for Building Small-World Networks
Autor/es:
  • Sevilla de Pablo, Andrés
  • Mozo Velasco, Alberto
  • Lorenzo Prieto, Maria Araceli
  • López Presa, Jose Luis
  • Manzano García, Pilar
  • Fernández Anta, Antonio
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 14th international conference on Principles of distributed systems, OPODIS 2010
Fechas del Evento: 14/11/2010 - 17/11/2010
Lugar del Evento: Tozeur, Túnez
Título del Libro: Proceedings of the 14th international conference on Principles of distributed systems, OPODIS 2010
Fecha: 2010
ISBN: 978-3-642-17652-4
Materias:
Escuela: E.U. de Informática (UPM) [antigua denominación]
Departamento: Arquitectura y Tecnología de Computadores [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (394kB) | Vista Previa

Resumen

Small-world networks are currently present in many distributed applications and can be built augmenting a base network with long-range links using a probability distribution. Currently available distributed algorithms to select these long-range neighbors are designed ad hoc for specific probability distributions. In this paper we propose a new algorithm called Biased Selection (BS) that, using a uniform sampling service (that could be implemented with, for instance, a gossip-based protocol), allows to select long-range neighbors with any arbitrary distribution in a distributed way. This algorithm is of iterative nature and has a parameter r that gives its number of iterations. We prove that the obtained sampling distribution converges to the desired distribution as r grows. Additionally, we obtain analytical bounds on the maximum relative error for a given value of this parameter r. Although the BS algorithm is proposed in this paper as a tool to sample nodes in a network, it can be used in any context in which sampling with an arbitrary distribution is required, and only uniform sampling is available. The BS algorithm has been used to choose long-range neighbors in complete and incomplete tori, in order to build Kleinberg’s small-world networks. We observe that using a very small number of iterations (1) BS has similar error as a simulation of the Kleinberg’s harmonic distribution and (2) the average number of hops with greedy routing is no larger with BS than in a Kleinberg network. Furthermore, we have observed that before converging to the performance of a Kleinberg network, the average number of hops with BS is significantly smaller (up to 14 % smaller in a 1000 ×1000 network).

Más información

ID de Registro: 7068
Identificador DC: http://oa.upm.es/7068/
Identificador OAI: oai:oa.upm.es:7068
URL Oficial: http://www.springerlink.com/content/l07q76761211uj53/
Depositado por: Memoria Investigacion
Depositado el: 25 May 2011 15:55
Ultima Modificación: 20 Abr 2016 16:11
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM