Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 Author, Editor
 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
 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
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