Implementation of a relay-free PubSub mechanism. I find inspiration in the following works:
- Cyclon (for peer sampling service)
- Vicinity (to obtain peers that are close in their topic interests. T-Man based. Also explore Nearest Neigbour Graph Construction)
- Rings (for maintenance of a ring per topic, but using nodes from vicinity to reuse neighbours in each ring)
- Cyclon for periodic passive view maintenance (regular shuffling with neighbour target selected by cache lifetime)
- Scamp for reactive active view maintenance
- HyParView for membership, with a number of improvements that we may want to incorporate
- Plumtree for epidemic broadcast
Others that we may also want to further investigate
- the works of Jim Dowling (Shuffling with a Croupier and Through the wormhole)
- Legion (implementation of HyParView prioritizing nodes close in network proximity, while maintaining long distance neighbours for small world principle)
Essentially, we want to implement Poldercast, substituting out Cyclon by HyParView for membership / sampling.
HyParView
Messages
- JOIN(newNode: ActorRef): a new node n establishes a TCP connection to the contact node c and sends to c a Join request. A node that receives a join request will start by adding the new node to its active view, even if it has to drop a random node from it. In this case a Disconnect notification is sent to the node that has been dropped from the active view.
- FORWARD_JOIN(newNode: ActorRef, timeToLive: Int, sender: ActorRef): A contact node receiving a join will forward this message, performing a random walk. The message carries a “time to live” field that is initially set to ARWL and decreased at every hop.
- If the TTL is equal to zero or if the number of nodes in p’s active view is equal to one, it will add the new node to its active view. This step is performed even if a random node must be dropped from the active view
- If the time to live is equal to PRWL, p will insert the new node into its passive view
- The time to live field is decremented
- If, at this point, n has not been inserted in p’s active view, p will forward the request to a random node in its active view (different from the one from which the request was received)
- DISCONNECT(peer: ActorRef): Sent to a node p by a node q whenever p is dropped from the active view of q
- SHUFFLE(exchangeSet: Set[ActorRef], timeToLive: Int, origin: ActorRef): Used for Passive-View maintenance. Shuffle requests are propagated using a random walk and have an associated “time to live”, just like the ForwardJoin requests. It contains p’s own identifier, ka nodes from its active view and kp nodes from its passive view (where ka and kp are protocol parameters)
- SHUFFLE_REPLY(exchangeSet: Set[ActorRef]): Sent back from the terminal node q of the random walk to the one initiating the SHUFFLE, p. It includes a number of nodes selected at random from q’s passive view equal to the number of nodes received in the Shuffle request
- NEIGHBOUR(ownId: ActorRef, prio: Boolean)
- NEIGHBOUR_REPLY(ownId: ActorRef, accepted: Boolean)
Configuration Parameters
- Active Random Walk Length (ARWL): specifies the maximum number of hops a ForwardJoin request is propagated
- Passive Random Walk Length (PRWL): specifies at which point in the walk the node is inserted in a passive view
- Ka: Number of nodes to be included of the active view when constructing SHUFFLE requests
- Kp: Number of nodes to be included of the passive view when constructing SHUFFLE requests