Randomized rumor spreading in non-static networks

De Wen Soh, Tony Q.S. Quek, Wee Peng Tay

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


Rumor spreading plays an important role in social communications. Moreover, it forms the basis for an important class of communication protocols called gossip algorithms, which are used for large-scale information dissemination in networks. In this work, we study the dissemination time for randomized broadcast in dynamic environments, like those encountered by wireless networks with mobile nodes. Specifically, we establish order bounds for the dissemination time when the underlying network connectivity matrix changes over time. We state the results for a network that undergoes a single switching time, and then establish bounds for the case where the connectivity matrix undergoes multiple switching times. In the switching time, we include possible additions of nodes. We also investigate an example of randomized gossip in vehicular networks.

Original languageEnglish
Title of host publication2011 International Conference on ICT Convergence, ICTC 2011
Number of pages5
Publication statusPublished - 2011
Event2011 International Conference on ICT Convergence, ICTC 2011 - Seoul, Korea, Republic of
Duration: 2011 Sep 282011 Sep 30

Publication series

Name2011 International Conference on ICT Convergence, ICTC 2011


Conference2011 International Conference on ICT Convergence, ICTC 2011
Country/TerritoryKorea, Republic of

All Science Journal Classification (ASJC) codes

  • Information Systems


Dive into the research topics of 'Randomized rumor spreading in non-static networks'. Together they form a unique fingerprint.

Cite this