Please use this identifier to cite or link to this item:
Title: Meeting the deadline: On the complexity of fault-tolerant continuous gossip
Authors: Georgiou, C.
Gilbert, S. 
Kowalski, D.R.
Keywords: Crashes and restarts
Dynamic rumor injection
Random and expander graphs
Issue Date: 2011
Citation: Georgiou, C., Gilbert, S., Kowalski, D.R. (2011). Meeting the deadline: On the complexity of fault-tolerant continuous gossip. Distributed Computing 24 (5) : 223-244. ScholarBank@NUS Repository.
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. © Springer-Verlag 2011.
Source Title: Distributed Computing
ISSN: 01782770
DOI: 10.1007/s00446-011-0144-6
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jan 22, 2019


checked on Jan 22, 2019

Page view(s)

checked on Dec 22, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.