dc.contributor.author | Georgiou, Chryssis | en |
dc.contributor.author | Gilbert, S. | en |
dc.contributor.author | Kowalski, D. R. | en |
dc.creator | Georgiou, Chryssis | en |
dc.creator | Gilbert, S. | en |
dc.creator | Kowalski, D. R. | en |
dc.date.accessioned | 2019-11-13T10:40:09Z | |
dc.date.available | 2019-11-13T10:40:09Z | |
dc.date.issued | 2010 | |
dc.identifier.isbn | 978-1-60558-888-9 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53981 | |
dc.description.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 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 | en |
dc.description.abstract | 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. Copyright 2010 ACM. | en |
dc.source | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing | en |
dc.source | 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010 | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-77956256339&doi=10.1145%2f1835698.1835759&partnerID=40&md5=e76da2a24445a4c82dc57a9cb26a9f67 | |
dc.subject | Lower bounds | en |
dc.subject | Fault-tolerant | en |
dc.subject | Crashes and restarts | en |
dc.subject | Gossip | en |
dc.subject | Dynamic network | en |
dc.subject | Dynamic rumor injection | en |
dc.subject | Expander graphs | en |
dc.subject | Gossip protocols | en |
dc.subject | Message complexity | en |
dc.subject | Trivial solutions | en |
dc.subject | Deterministic protocols | en |
dc.title | Meeting the deadline: On the complexity of fault-tolerant Continuous Gossip | en |
dc.type | info:eu-repo/semantics/conferenceObject | |
dc.identifier.doi | 10.1145/1835698.1835759 | |
dc.description.startingpage | 247 | |
dc.description.endingpage | 256 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Conference Object | en |
dc.description.notes | <p>Sponsors: ACM SIGACT | en |
dc.description.notes | ACM SIGOPS | en |
dc.description.notes | Conference code: 81577 | en |
dc.description.notes | Cited By :5</p> | en |
dc.contributor.orcid | Georgiou, Chryssis [0000-0003-4360-0260] | |
dc.gnosis.orcid | 0000-0003-4360-0260 | |