TY - GEN
T1 - Slow links, fast links, and the cost of gossip
AU - Sourav, Suman
AU - Robinson, Peter
AU - Gilbert, Seth
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/7/19
Y1 - 2018/7/19
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 by defining φ∗ to be the 'critical conductance' and ℓ∗ 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, up to polylogarithmic factors. Specifically, we show that in a graph with (weighted) diameter d (with latencies as weights) and maximum degree Δ, any information dissemination algorithm requires at least Δ(min(D+Δ, ℓ∗/φ∗)) time in the worst case. We show several variants of the lower bound (e.g., for graphs with small diameter, graphs with small max-degree, etc.) by reduction to a simple combinatorial game. We then give nearly matching algorithms, showing that information dissemination can be solved in O(min((D+Δ)log^3 n, (ℓ∗/φ;∗)\log n) time. This is achieved by combining two cases. We show that the classical push-pull algorithm is (near) optimal when the diameter or the maximum degree is large. For the case where the diameter and the maximum degree are small, we give an alternative strategy in which we first discover the latencies and then use an algorithm for known latencies based on a weighted spanner construction. (Our algorithms are within polylogarithmic factors of being tight both for known and unknown latencies.) While it is easiest to express our bounds in terms of φ∗ and ℓ∗, in some cases they do not provide the most convenient definition of conductance in weighted graphs. Therefore, we give a second (nearly) equivalent characterization, namely the average conductance φ-avg.
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 by defining φ∗ to be the 'critical conductance' and ℓ∗ 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, up to polylogarithmic factors. Specifically, we show that in a graph with (weighted) diameter d (with latencies as weights) and maximum degree Δ, any information dissemination algorithm requires at least Δ(min(D+Δ, ℓ∗/φ∗)) time in the worst case. We show several variants of the lower bound (e.g., for graphs with small diameter, graphs with small max-degree, etc.) by reduction to a simple combinatorial game. We then give nearly matching algorithms, showing that information dissemination can be solved in O(min((D+Δ)log^3 n, (ℓ∗/φ;∗)\log n) time. This is achieved by combining two cases. We show that the classical push-pull algorithm is (near) optimal when the diameter or the maximum degree is large. For the case where the diameter and the maximum degree are small, we give an alternative strategy in which we first discover the latencies and then use an algorithm for known latencies based on a weighted spanner construction. (Our algorithms are within polylogarithmic factors of being tight both for known and unknown latencies.) While it is easiest to express our bounds in terms of φ∗ and ℓ∗, in some cases they do not provide the most convenient definition of conductance in weighted graphs. Therefore, we give a second (nearly) equivalent characterization, namely the average conductance φ-avg.
KW - Conductance
KW - Gossip
KW - Information Dissemination
KW - Latencies
KW - Weighted Graphs
UR - http://www.scopus.com/inward/record.url?scp=85050962048&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85050962048&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2018.00081
DO - 10.1109/ICDCS.2018.00081
M3 - Conference contribution
AN - SCOPUS:85050962048
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 786
EP - 796
BT - Proceedings - 2018 IEEE 38th International Conference on Distributed Computing Systems, ICDCS 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018
Y2 - 2 July 2018 through 5 July 2018
ER -