short-paper

Brief announcement: parameterized maximum and average degree approximation in topic-based publish-subscribe overlay network design

Authors:

Melih Onus,

Andréa W. RichaAuthors Info & Claims

SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

Pages 39 - 40

https://doi.org/10.1145/1583991.1584000

Published: 11 August 2009 Publication History

Get Access

Abstract

Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions connect the nodes into a graph which has low average and maximum degree and in such a way that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial time parameterized sublinear approximation algorithm for this problem.

References

[1]

G. Chockler, R. Melamed, Y. Tock, and R. Vitenberg. Constructing scalable overlays for pub-sub with many topics. In PODC, pages 109--118, 2007.

Digital Library

Google Scholar

[2]

M. Onus and A.W. Richa. Parameterized Maximum and Average Degree Approximation in Topic-based Publish-Subscribe Overlay Network Design. In Technical Report, Arizona State University, Department of Computer Science and Engineering, TR-09-006, 2009.

Google Scholar

[3]

M. Onus and A.W. Richa. Minimum maximum Degree Publish-Subscribe Overlay Network Design. In INFOCOM, 2009.

Crossref

Google Scholar

Cited By

View all

Onus MRicha A(2011)Minimum maximum-degree publish-subscribe overlay network designIEEE/ACM Transactions on Networking10.1109/TNET.2011.214499919:5(1331-1343)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1109/TNET.2011.2144999
Onus MRicha A(2010)Parameterized Maximum and Average Degree Approximation in Topic-Based Publish-Subscribe Overlay Network DesignProceedings of the 2010 IEEE 30th International Conference on Distributed Computing Systems10.1109/ICDCS.2010.54(644-652)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.1109/ICDCS.2010.54

Index Terms

Brief announcement: parameterized maximum and average degree approximation in topic-based publish-subscribe overlay network design

Recommendations

Constructing scalable overlays for pub-sub with many topics
PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing

We investigate the problem of designing a scalable overlay network to support decentralized topic-based pub/sub communication. We introduce a new optimization problem, called Minimum Topic-Connected Overlay (Min-TCO), that captures the tradeoff between ...
Brief announcement: constructing fault-tolerant overlay networks for topic-based publish/subscribe
PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing

We incorporate fault tolerance in designing reliable and scalable overlay networks to support topic-based pub/sub communication. We propose the MinAvg- kTCO problem parameterized by k: use the minimum number of edges to create a k-topic-connected ...
SpiderCast: a scalable interest-aware overlay for topic-based pub/sub communication
DEBS '07: Proceedings of the 2007 inaugural international conference on Distributed event-based systems

We introduce SpiderCast, a distributed protocol for constructing scalable churn-resistant overlay topologies for supporting decentralized topic-based pub/sub communication. SpiderCast is designed to effectively tread the balance between average overlay ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

August 2009

370 pages

ISBN:9781605586069

DOI:10.1145/1583991

General Chair:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany)
,
Program Chair:
Michael A. Bender
Stony Brook University and Tokutek, Inc., USA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

SPAA 09

Sponsor:

SPAA 09: 21st ACM Symposium on Parallelism in Algorithms and Architectures

August 11 - 13, 2009

AB, Calgary, Canada

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
124
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Onus MRicha A(2011)Minimum maximum-degree publish-subscribe overlay network designIEEE/ACM Transactions on Networking10.1109/TNET.2011.214499919:5(1331-1343)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1109/TNET.2011.2144999
Onus MRicha A(2010)Parameterized Maximum and Average Degree Approximation in Topic-Based Publish-Subscribe Overlay Network DesignProceedings of the 2010 IEEE 30th International Conference on Distributed Computing Systems10.1109/ICDCS.2010.54(644-652)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.1109/ICDCS.2010.54

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Constructing scalable overlays for pub-sub with many topics

Brief announcement: constructing fault-tolerant overlay networks for topic-based publish/subscribe

SpiderCast: a scalable interest-aware overlay for topic-based pub/sub communication