TY - GEN

T1 - Brief announcement

T2 - 36th ACM Symposium on Principles of Distributed Computing, PODC 2017

AU - Gilbert, Seth

AU - Robinson, Peter

AU - Sourav, Suman

N1 - Funding Information:
∗A full version of the paper is available in [9]. Authors are listed alphabetically. †This author is the corresponding author. ‡Supported by Singapore MOE grant (MOE2014-T2-1-157).
Publisher Copyright:
© 2017 Association for Computing Machinery.

PY - 2017/7/26

Y1 - 2017/7/26

N2 - Consider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. In this paper, we study the cost of information dissemination in networks where edges have latencies, i.e., sending a message from one node to another takes some amount of time. We first generalize the idea of conductance to weighted graphs, defining φ∗ to be the "weighted conductance" and l∗ to be the "critical latency." One goal of this paper is to argue that φ∗ characterizes the connectivity of a weighted graph with latencies in much the same way that conductance characterizes the connectivity of unweighted graphs. We give near tight lower and upper bounds on the problem of information dissemination. Specifically, we show that in a graph with (weighted) diameter D (with latencies as weights), maximum degree Δ, weighted conductance φ∗ and critical latency l∗, any information dissemination algorithm requires at least Ω(min(D + Δ, l∗/φ∗)) time. We then give nearly matching algorithms, showing that information dissemination can be solved in O(min((D + Δ) log3 n), (l∗/φ∗) log(n)) time.

AB - Consider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. In this paper, we study the cost of information dissemination in networks where edges have latencies, i.e., sending a message from one node to another takes some amount of time. We first generalize the idea of conductance to weighted graphs, defining φ∗ to be the "weighted conductance" and l∗ to be the "critical latency." One goal of this paper is to argue that φ∗ characterizes the connectivity of a weighted graph with latencies in much the same way that conductance characterizes the connectivity of unweighted graphs. We give near tight lower and upper bounds on the problem of information dissemination. Specifically, we show that in a graph with (weighted) diameter D (with latencies as weights), maximum degree Δ, weighted conductance φ∗ and critical latency l∗, any information dissemination algorithm requires at least Ω(min(D + Δ, l∗/φ∗)) time. We then give nearly matching algorithms, showing that information dissemination can be solved in O(min((D + Δ) log3 n), (l∗/φ∗) log(n)) time.

KW - Critical latency

KW - Gossip

KW - Guessing game

KW - Information dissemination

KW - Latencies

KW - Weighted conductance

KW - Weighted spanner

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

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

U2 - 10.1145/3087801.3087846

DO - 10.1145/3087801.3087846

M3 - Conference contribution

AN - SCOPUS:85027854708

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 255

EP - 257

BT - PODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

Y2 - 25 July 2017 through 27 July 2017

ER -