Rumor Spreading with Bounded In-Degree

Sebastian Daum, Fabian Kuhn, Yannic Maus*

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review


In the gossip-based model of communication for disseminating information in a network, in each time unit, every node u can contact a single random neighbor v but can possibly be contacted by many nodes. In the present paper, we consider a restricted model where at each node only one incoming call can be answered in one time unit. We study the implied weaker version of the well-studied pull protocol, which we call restricted pull.

We prove an exponential separation of the rumor spreading time between two variants of the protocol (the answered call among a set of calls is chosen adversarial or uniformly at random). Further, we show that if the answered call is chosen randomly, the slowdown of restricted pull versus the classic pull protocol can w.h.p. be upper bounded by O(Δ/δ⋅logn)
, where Δ and δ are the largest and smallest degree of the network.
Original languageEnglish
Publication statusPublished - 2016
Externally publishedYes
Event23rd International Colloquium on Structural Information and Communication Complexity: SIROCCO 2016 - Helsinki, Finland
Duration: 19 Jul 201621 Jul 2016


Conference23rd International Colloquium on Structural Information and Communication Complexity
Abbreviated titleSIROCCO 2016


Dive into the research topics of 'Rumor Spreading with Bounded In-Degree'. Together they form a unique fingerprint.

Cite this