MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Fountoulakis, Nikolaos
Huber, Anna
Panagiotou, Konstantinos		dblp
dblp
dblp
Editor(s):
Keidar, Iditdblp
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
Conference URL::
http://disc2009.gsyc.es/
Downloading URL:
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
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 17:25:54
Revision
1.
0.


Editor
Anja Becker
Anna Huber


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