Biased Selection for Building Small-World Networks

Sevilla de Pablo, Andrés and Mozo Velasco, Alberto and Lorenzo Prieto, Maria Araceli and López Presa, Jose Luis and Manzano García, Pilar and Fernández Anta, Antonio (2010). Biased Selection for Building Small-World Networks. In: "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.

Description

Title: Biased Selection for Building Small-World Networks
Author/s:
  • 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
Item Type: Presentation at Congress or Conference (Article)
Event Title: 14th international conference on Principles of distributed systems, OPODIS 2010
Event Dates: 14/11/2010 - 17/11/2010
Event Location: Tozeur, Túnez
Title of Book: Proceedings of the 14th international conference on Principles of distributed systems, OPODIS 2010
Date: 2010
ISBN: 978-3-642-17652-4
Subjects:
Faculty: E.U. de Informática (UPM)
Department: Arquitectura y Tecnología de Computadores [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (394kB) | Preview

Abstract

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).

More information

Item ID: 7068
DC Identifier: http://oa.upm.es/7068/
OAI Identifier: oai:oa.upm.es:7068
Official URL: http://www.springerlink.com/content/l07q76761211uj53/
Deposited by: Memoria Investigacion
Deposited on: 25 May 2011 15:55
Last Modified: 20 Apr 2016 16:11
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM