Discuss two possible implementations of EN(e) and SN(s). Why must the intersection of EN(e) and SN(s) be non-null for a given e that matches s (the intersection rule)? Does this apply in your possible implementations?

Question

What will be an ideal response?

Answer 1

A common mechanism for implementing the two functions is to map on to an underlying Distributed Hash Table (DHT). For example, consider Scribe, a publish-subscribe system implemented over Pastry. Scribe is a topic-based publish-subscribe system. In Scribe, EN(e) and SN(s) are identical operations and are implemented by the underlying hash function applied to the topic name. This ensures that rendezvous-nodes are chosen at random from the underlying nodes in the associated overlay.
Meghdood [Cao and Singh 2005] offers a second example of how to implement rendezvous-based routing. Meghdood is a content-based publish-subscribe system and, as such, the designers were interested in determining rendezvous nodes not just from the topic or one field but from the entire content. This is a much harder problem. The solution is to map on to a Content Addressable Network (or CAN). A CAN is an overlay network representing an n-dimensional space where each node is responsible for a partition of this space. Meghdood provides a particular subscription language which effectively defines this multi-dimensional space (the space of all possible subscriptions) with the underlying CAN then providing the associated partitioning of this space. The node responsible for each partition is exactly equivalent to the rendezvous node. Please refer to the Meghdood paper for details.
It should be fairly obvious why the intersection rule is required. In all rendezvous-based routing algorithms, subscriptions are sent to one or more rendezvous nodes with the subscriptions stored at these nodes. For a publish event to be routed to all subscriptions, for any event, the calculated set of nodes offered by EN(e) must overlap with the corresponding calculation of SN(s) to find a node that will then match to the subscription and forward it accordingly.
In the first implementation, the intersection rule is trivially met as EN=SN. For the second, the argument the rule is also met. In Megdhood, an event maps to a CAN region which cover all possible subscriptions that can map to that event (known as the event region).