Abstract
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 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 perround 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 noncrashed process. In this work we show how to address this challenge; we develop randomized and deterministic proto- cols for Continuous Gossip and prove lower bounds on the per-round message-complexity, indicating that our protocols are close to optimal.
Original language | English (US) |
---|---|
Pages (from-to) | 223-244 |
Number of pages | 22 |
Journal | Distributed Computing |
Volume | 24 |
Issue number | 5 |
DOIs | |
State | Published - Dec 2011 |
Externally published | Yes |
Keywords
- Crashes and restarts
- Dynamic rumor injection
- Gossip
- Random and expander graphs
ASJC Scopus subject areas
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computational Theory and Mathematics