Brief announcement: Gossiping with latencies

Seth Gilbert, Peter Robinson, Suman Sourav

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

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationPODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Number of pages3
ISBN (Electronic)9781450349925
StatePublished - Jul 26 2017
Externally publishedYes
Event36th ACM Symposium on Principles of Distributed Computing, PODC 2017 - Washington, United States
Duration: Jul 25 2017Jul 27 2017

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing
VolumePart F129314


Other36th ACM Symposium on Principles of Distributed Computing, PODC 2017
Country/TerritoryUnited States


  • Critical latency
  • Gossip
  • Guessing game
  • Information dissemination
  • Latencies
  • Weighted conductance
  • Weighted spanner

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Brief announcement: Gossiping with latencies'. Together they form a unique fingerprint.

Cite this