Maximizing the number of satisfied subscribers in pub/sub systems under capacity constraints
2014 (English)In: Proceedings - IEEE INFOCOM, 2014, 2580-2588 p.Conference paper (Refereed)
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.
Capacity constraints, Communication paradigm, Formal approximations, Large-scale distributed system, Maximum coverage, Pub/sub systems, Publish/subscribe, Workload variation, Optimization
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-167944DOI: 10.1109/INFOCOM.2014.6848205ISI: 000361544200288ScopusID: 2-s2.0-84904438159ISBN: 9781479933600OAI: oai:DiVA.org:kth-167944DiVA: diva2:817385
33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014, 27 April 2014 through 2 May 2014, Toronto, ON
QC 201506052015-06-052015-05-222015-10-29Bibliographically approved