Brief Announcement: Gossiping with Latencies

Seth Gilbert, Peter Robinson, Suman Sourav

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 + Δ)log3n), (l*/φ*)log(n)) time.
Original languageEnglish
Title of host publicationPODC '17
Subtitle of host publicationProceedings of the ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery (ACM)
Number of pages3
ISBN (Electronic)978-1-4503-4992-5
Publication statusPublished - 25 Jul 2017

Cite this