Meeting the deadline: On the complexity of fault-tolerant Continuous Gossip

Chryssis Georgiou, Seth Gilbert, Dariusz R. Kowalski

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

8 Scopus citations


In this paper, we introduce the problem of Continuous Gossip in which rumors are continually and dynamically injected throughout the network. Each rumor has a deadline, and the goal of a continuous gossip protocol is to ensure good "Quality of Delivery," i.e., to deliver every rumor to every process before the deadline expires. Thus, a trivial solution to the problem of Continuous Gossip is simply for every process to broadcast every rumor as soon as it is injected. Unfortunately, this solution has a high per-round message complexity. Complicating matters, we focus our attention on a highly dynamic network in which processes may continually crash and recover. In order to achieve good per-round message complexity in a dynamic network, processes need to continually form and re-form coalitions that cooperate to spread their rumors throughout the network. The key challenge for a Continuous Gossip protocol is the ongoing adaptation to the ever-changing set of active rumors and non-crashed process. In this work we show how to address this challenge; we develop randomized and deterministic protocols for Continuous Gossip and prove lower bounds on the per-round message-complexity, indicating that our protocols are close to optimal.

Original languageEnglish (US)
Title of host publicationPODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing
Number of pages10
StatePublished - 2010
Externally publishedYes
Event29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010 - Zurich, Switzerland
Duration: Jul 25 2010Jul 28 2010

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing


Conference29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010


  • Crashes and restarts
  • Dynamic rumor injection
  • Expander graphs
  • Gossip

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this