Change search
ReferencesLink to record
Permanent link

Direct link
Maximizing the number of satisfied subscribers in pub/sub systems under capacity constraints
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
Show others and affiliations
2014 (English)In: Proceedings - IEEE INFOCOM, 2014, 2580-2588 p.Conference paper (Refereed)
Abstract [en]

Publish/subscribe (pub/sub) is a popular communication paradigm in the design of large-scale distributed systems. A provider of a pub/sub service (whether centralized, peer-assisted, or based on a federated organization of cooperatively managed servers) commonly faces a fundamental challenge: given limited resources, how to maximize the satisfaction of subscribers? We provide, to the best of our knowledge, the first formal treatment of this problem by introducing two metrics that capture subscriber satisfaction in the presence of limited resources. This allows us to formulate matters as two new flavors of maximum coverage optimization problems. Unfortunately, both variants of the problem prove to be NP-hard. By subsequently providing formal approximation bounds and heuristics, we show, however, that efficient approximations can be attained. We validate our approach using real-world traces from Spotify and show that our solutions can be executed periodically in real-time in order to adapt to workload variations.

Place, publisher, year, edition, pages
2014. 2580-2588 p.
Keyword [en]
Capacity constraints, Communication paradigm, Formal approximations, Large-scale distributed system, Maximum coverage, Pub/sub systems, Publish/subscribe, Workload variation, Optimization
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-167944DOI: 10.1109/INFOCOM.2014.6848205ISI: 000361544200288ScopusID: 2-s2.0-84904438159ISBN: 9781479933600OAI: diva2:817385
33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014, 27 April 2014 through 2 May 2014, Toronto, ON

QC 20150605

Available from: 2015-06-05 Created: 2015-05-22 Last updated: 2015-10-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Kreitz, Gunnar
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 33 hits
ReferencesLink to record
Permanent link

Direct link