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 -