Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Fountoulakis, Nikolaos
Huber, Anna
Panagiotou, Konstantinos

dblp
dblp
dblp



Editor(s):

Keidar, Idit

dblp

Not MPII Editor(s):

Keidar, Idit

BibTeX cite key*:

FHP2009

Title, Booktitle

Title*:

Brief Announcement: The Speed of Broadcasting in Random Networks - Density Does Not Matter

Booktitle*:

Distributed Computing : 23rd International Symposium, DISC 2009

Event, URLs

URL of the conference:

http://disc2009.gsyc.es/

URL for downloading the paper:

http://www.springerlink.com/content/8g1q7h5285155063/fulltext.pdf

Event Address*:

Elche/Elx, Spain

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

23 September 2009

Event End Date:

25 September 2009

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

5805

Number:


Month:


Pages:

529-530

Year*:

2009

VG Wort Pages:


ISBN/ISSN:

978-3-642-04354-3

Sequence Number:


DOI:

10.1007/978-3-642-04355-0_53



Note, Abstract, ©

Note:

Full version available from arXiv:0904.4851

(LaTeX) Abstract:

Broadcasting algorithms are of fundamental importance for distributed systems engineering. In this paper we revisit the classical and well-studied \emph{push} protocol for message broadcasting. Assuming that initially only one node has some piece of information, at each stage every one of the informed nodes chooses randomly and independently one of its neighbors and passes the message to it.

The performance of the push protocol on a fully connected network, where each node is joined by a link to every other node, is very well understood. In particular, Frieze and Grimmett proved that with probability $1-o(1)$ the push protocol completes the broadcasting of the message within $(1\pm \eps) (\log_2 n + \ln n)$ stages, where $n$ is the number of nodes of the network. However, there are no tight bounds for the broadcast time on networks that are significantly sparser than the complete graph.

In this work we consider random networks on $n$ nodes, where every edge is present with probability $p$, independently of every other edge. We show that if $p\geq {\alpha (n) \ln n \over n}$, where $\alpha(n)$ is any function that tends to infinity as $n$ grows, then the push protocol broadcasts the message within $(1\pm \eps) (\log_2 n + \ln n)$ stages with probability $1-o(1)$. In other words, in almost every network of density $d$ such that $d \ge \alpha(n) \ln n$, the push protocol broadcasts a message as fast as in a fully connected network. This is quite surprising in the sense that the time needed remains essentially \emph{unaffected} by the fact that most of the links are missing.

HyperLinks / References / URLs:

http://xxx.lanl.gov/pdf/0904.4851v1



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{FHP2009,
AUTHOR = {Fountoulakis, Nikolaos and Huber, Anna and Panagiotou, Konstantinos},
EDITOR = {Keidar, Idit},
TITLE = {Brief Announcement: {The} Speed of Broadcasting in Random Networks - Density Does Not Matter},
BOOKTITLE = {Distributed Computing : 23rd International Symposium, DISC 2009},
PUBLISHER = {Springer},
YEAR = {2009},
VOLUME = {5805},
PAGES = {529--530},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Elche/Elx, Spain},
ISBN = {978-3-642-04354-3},
DOI = {10.1007/978-3-642-04355-0_53},
NOTE = {Full version available from arXiv:0904.4851},
}


Entry last modified by Anja Becker, 03/05/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/14/2010 05:25:54 PM
Revision
1.
0.


Editor
Anja Becker
Anna Huber


Edit Date
05.03.2010 13:59:09
02/14/2010 05:25:54 PM


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section