Rumor Spreading with Bounded In-Degree

Sebastian Daum; Fabian Kuhn; Yannic Maus

doi:10.1007/978-3-319-48314-6_21

Rumor Spreading with Bounded In-Degree

Sebastian Daum, Fabian Kuhn, Yannic Maus^*

^*Corresponding author for this work

Research output: Contribution to conference › Paper › peer-review

Abstract

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 language	English
Pages	323-339
DOIs	https://doi.org/10.1007/978-3-319-48314-6_21
Publication status	Published - 2016
Externally published	Yes
Event	23rd International Colloquium on Structural Information and Communication Complexity: SIROCCO 2016 - Helsinki, Finland Duration: 19 Jul 2016 → 21 Jul 2016

Conference

Conference	23rd International Colloquium on Structural Information and Communication Complexity
Abbreviated title	SIROCCO 2016
Country/Territory	Finland
City	Helsinki
Period	19/07/16 → 21/07/16

Access to Document

10.1007/978-3-319-48314-6_21

https://dblp.org/rec/conf/sirocco/DaumKM16

Cite this

@conference{23b7cfe8fefc4a4d9213c0fd251aed71,

title = "Rumor Spreading with Bounded In-Degree",

abstract = "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.",

author = "Sebastian Daum and Fabian Kuhn and Yannic Maus",

year = "2016",

doi = "10.1007/978-3-319-48314-6_21",

language = "English",

pages = "323--339",

note = "23rd International Colloquium on Structural Information and Communication Complexity : SIROCCO 2016, SIROCCO 2016 ; Conference date: 19-07-2016 Through 21-07-2016",

}

TY - CONF

T1 - Rumor Spreading with Bounded In-Degree

AU - Daum, Sebastian

AU - Kuhn, Fabian

AU - Maus, Yannic

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-48314-6_21

DO - 10.1007/978-3-319-48314-6_21

M3 - Paper

SP - 323

EP - 339

T2 - 23rd International Colloquium on Structural Information and Communication Complexity

Y2 - 19 July 2016 through 21 July 2016

ER -

Rumor Spreading with Bounded In-Degree

Abstract

Conference

Access to Document

Fingerprint

Cite this