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 | 2011 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53979 | |
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 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 | en |
dc.description.abstract | 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. | en |
dc.source | Distributed Computing | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84855594589&doi=10.1007%2fs00446-011-0144-6&partnerID=40&md5=8ddd7522efbafd26b8d75c18b01c516b | |
dc.subject | Distributed computer systems | en |
dc.subject | Hardware | en |
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 | Random and expander graphs | en |
dc.subject | Trivial solutions | en |
dc.title | Meeting the deadline: On the complexity of fault-tolerant continuous gossip | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1007/s00446-011-0144-6 | |
dc.description.volume | 24 | |
dc.description.issue | 5 | |
dc.description.startingpage | 223 | |
dc.description.endingpage | 244 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Cited By :3</p> | en |
dc.source.abbreviation | Distrib Comput | en |
dc.contributor.orcid | Georgiou, Chryssis [0000-0003-4360-0260] | |
dc.gnosis.orcid | 0000-0003-4360-0260 | |