Brief Announcement: Constructing Fault-Tolerant Overlay Networks for Topic-based Publish/Subscribe
Chen Chen, Roman Vitenberg, and Hans-Arno Jacobsen.
In ACM Symposium on Principles of Distributed Computing (PODC), pages 184 - 186, July 2013.
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 overlay (kTCO) for pub/sub systems, i.e.,
for each topic the sub-overlay induced by nodes interested
in the topic is k-connected.
We prove the NP-completeness of MinAvg-kTCO and show
a lower-bound for the hardness of its approximation. With
regard to MinAvg-2TCO, we present GM2 , the first polynomial
time algorithm with an approximation ratio. With
regards to MinAvg-kTCO, where k >= 2 , we propose a simple
and efficient heuristic algorithm, namely HararyPT, that
aligns nodes across different sub-overlays.
We experimentally demonstrate the scalability of GM2
and HararyPT under representative pub/sub workloads.
Readers who enjoyed the above work, may also like the following:
- OMen: Overlay Mending for Topic-based Publish/Subscribe Systems Under Churn.
Chen Chen, Roman Vitenberg , and Hans-Arno Jacobsen.
In 10th ACM International Conference on Distributed and Event-Based Systems (DEBS), June 2016.
Tags: overlay, pub/sub, churn handling, topic-connected overlay, t-man
- Overlay Design for Topic-based Publish/Subscribe under Node Degree Constraints.
Chen Chen, Yoav Tock, and Hans-Arno Jacobsen.
In 36th IEEE International Conference on Distributed Computing Systems (ICDCS), Nara, Japan, June 2016.
Acceptance rate: 17.6%. 68 papers accepted out of 386 submissions.
Tags: icdcs16, overlay, pub/sub
- Weighted Overlay Design for Topic-based Publish/Subscribe on Geo-Distributed Data Centers.
Chen Chen, Yoav Tock, Hans-Arno Jacobsen, and Roman Vitenberg.
In 35th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 474-485, July 2015.
Acceptance rate: 13%. 70 papers accepted out of 543 submissions..
Tags: icdcs15, overlay, pub/sub