TY - GEN
T1 - Meeting the deadline
T2 - 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010
AU - Georgiou, Chryssis
AU - Gilbert, Seth
AU - Kowalski, Dariusz R.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Crashes and restarts
KW - Dynamic rumor injection
KW - Expander graphs
KW - Gossip
UR - http://www.scopus.com/inward/record.url?scp=77956256339&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77956256339&partnerID=8YFLogxK
U2 - 10.1145/1835698.1835759
DO - 10.1145/1835698.1835759
M3 - Conference contribution
AN - SCOPUS:77956256339
SN - 9781605588889
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 247
EP - 256
BT - PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing
Y2 - 25 July 2010 through 28 July 2010
ER -