Show simple item record

dc.contributor.authorGeorgiou, Chryssisen
dc.contributor.authorGilbert, S.en
dc.contributor.authorKowalski, D. R.en
dc.creatorGeorgiou, Chryssisen
dc.creatorGilbert, S.en
dc.creatorKowalski, D. R.en
dc.description.abstractIn 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 challengeen
dc.description.abstractwe 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. Copyright 2010 ACM.en
dc.sourceProceedings of the Annual ACM Symposium on Principles of Distributed Computingen
dc.source29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010en
dc.subjectLower boundsen
dc.subjectCrashes and restartsen
dc.subjectDynamic networken
dc.subjectDynamic rumor injectionen
dc.subjectExpander graphsen
dc.subjectGossip protocolsen
dc.subjectMessage complexityen
dc.subjectTrivial solutionsen
dc.subjectDeterministic protocolsen
dc.titleMeeting the deadline: On the complexity of fault-tolerant Continuous Gossipen
dc.description.endingpage256 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeConference Objecten
dc.description.notes<p>Sponsors: ACM SIGACTen
dc.description.notesACM SIGOPSen
dc.description.notesConference code: 81577en
dc.description.notesCited By :5</p>en
dc.contributor.orcidGeorgiou, Chryssis [0000-0003-4360-0260]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record