Estimating time complexity of rumor spreading in ad-hoc networks

Dariusz R. Kowalski; Christopher Thraves Caro

doi:10.1007/978-3-642-39247-4_21

Estimating time complexity of rumor spreading in ad-hoc networks

Dariusz R. Kowalski, Christopher Thraves Caro

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

Rumor spreading is a fundamental communication process: given a network topology modeled by a graph and a source node with a message, the goal is to disseminate the source message to all network nodes. In this work we give a new graph-based formula that is a relatively tight estimate of the time complexity of rumor spreading in ad-hoc networks by popular Push&Pull protocol. We demonstrate its accuracy by comparing it to previously considered characteristics, such as graph conductance or vertex expansion, which in some cases are even exponentially worse than our new characterization.

Original language	English (US)
Title of host publication	Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings
Pages	245-256
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-39247-4_21
State	Published - 2013
Externally published	Yes
Event	12th International Conference on Ad-hoc, Mobile and Wireless Networks, ADHOC-NOW 2013 - Wroclaw, Poland Duration: Jul 8 2013 → Jul 10 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7960 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Ad-hoc, Mobile and Wireless Networks, ADHOC-NOW 2013
Country/Territory	Poland
City	Wroclaw
Period	7/8/13 → 7/10/13

Keywords

Push&Pull protocol
Rumor spreading
asynchronous model
conductance
synchronous model
vertex expansion

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-39247-4_21

Cite this

Kowalski, D. R., & Thraves Caro, C. (2013). Estimating time complexity of rumor spreading in ad-hoc networks. In Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings (pp. 245-256). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7960 LNCS). https://doi.org/10.1007/978-3-642-39247-4_21

Estimating time complexity of rumor spreading in ad-hoc networks. / Kowalski, Dariusz R.; Thraves Caro, Christopher.
Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings. 2013. p. 245-256 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7960 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kowalski, DR & Thraves Caro, C 2013, Estimating time complexity of rumor spreading in ad-hoc networks. in Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7960 LNCS, pp. 245-256, 12th International Conference on Ad-hoc, Mobile and Wireless Networks, ADHOC-NOW 2013, Wroclaw, Poland, 7/8/13. https://doi.org/10.1007/978-3-642-39247-4_21

Kowalski DR, Thraves Caro C. Estimating time complexity of rumor spreading in ad-hoc networks. In Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings. 2013. p. 245-256. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-39247-4_21

Kowalski, Dariusz R. ; Thraves Caro, Christopher. / Estimating time complexity of rumor spreading in ad-hoc networks. Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings. 2013. pp. 245-256 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b57d2706a0254539bb46ba65f8e7552c,

title = "Estimating time complexity of rumor spreading in ad-hoc networks",

abstract = "Rumor spreading is a fundamental communication process: given a network topology modeled by a graph and a source node with a message, the goal is to disseminate the source message to all network nodes. In this work we give a new graph-based formula that is a relatively tight estimate of the time complexity of rumor spreading in ad-hoc networks by popular Push&Pull protocol. We demonstrate its accuracy by comparing it to previously considered characteristics, such as graph conductance or vertex expansion, which in some cases are even exponentially worse than our new characterization.",

keywords = "Push&Pull protocol, Rumor spreading, asynchronous model, conductance, synchronous model, vertex expansion",

author = "Kowalski, {Dariusz R.} and {Thraves Caro}, Christopher",

year = "2013",

doi = "10.1007/978-3-642-39247-4_21",

language = "English (US)",

isbn = "9783642392467",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "245--256",

booktitle = "Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings",

note = "12th International Conference on Ad-hoc, Mobile and Wireless Networks, ADHOC-NOW 2013 ; Conference date: 08-07-2013 Through 10-07-2013",

}

TY - GEN

T1 - Estimating time complexity of rumor spreading in ad-hoc networks

AU - Kowalski, Dariusz R.

AU - Thraves Caro, Christopher

PY - 2013

Y1 - 2013

N2 - Rumor spreading is a fundamental communication process: given a network topology modeled by a graph and a source node with a message, the goal is to disseminate the source message to all network nodes. In this work we give a new graph-based formula that is a relatively tight estimate of the time complexity of rumor spreading in ad-hoc networks by popular Push&Pull protocol. We demonstrate its accuracy by comparing it to previously considered characteristics, such as graph conductance or vertex expansion, which in some cases are even exponentially worse than our new characterization.

AB - Rumor spreading is a fundamental communication process: given a network topology modeled by a graph and a source node with a message, the goal is to disseminate the source message to all network nodes. In this work we give a new graph-based formula that is a relatively tight estimate of the time complexity of rumor spreading in ad-hoc networks by popular Push&Pull protocol. We demonstrate its accuracy by comparing it to previously considered characteristics, such as graph conductance or vertex expansion, which in some cases are even exponentially worse than our new characterization.

KW - Push&Pull protocol

KW - Rumor spreading

KW - asynchronous model

KW - conductance

KW - synchronous model

KW - vertex expansion

UR - http://www.scopus.com/inward/record.url?scp=84884508339&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84884508339&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39247-4_21

DO - 10.1007/978-3-642-39247-4_21

M3 - Conference contribution

AN - SCOPUS:84884508339

SN - 9783642392467

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 245

EP - 256

BT - Ad-hoc, Mobile, and Wireless Network - 12th International Conference, ADHOC-NOW 2013, Proceedings

T2 - 12th International Conference on Ad-hoc, Mobile and Wireless Networks, ADHOC-NOW 2013

Y2 - 8 July 2013 through 10 July 2013

ER -

Estimating time complexity of rumor spreading in ad-hoc networks

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this