Underlying problem
In a case of a peer-to-peer discovery protocol,suppose we need to advertise peers in a manner that the network graph will grow such that we avoid cases of both too dense areas (e.g cliques) and too weakly connected areas (e.g bridge nodes).A node can also fail,disconnect, reconnect and update the list of peers it preserves at certain intervals.
An approach to solving this would be to advertise peers with a probability inversely proportional to the times already advertised.
I have obtained the below requirements for the use of a data structure to serve our purpose:
- Keep nodes sorted by a score relevant to the times already advertised,preferably self adjusting sorting on insertion of new nodes
- Fast selection of first k elements based on score
- Easy update of score and position of nodes in each advertise action
- Easy check of duplicate nodes upon insertion, e.g caused by a node failure and reconnect.
- Synchronization for concurrent access, modification
The language used for implementation is java.
Questions
- Am I correctly addressing the problem by the use of such a score and a data structure with the aforementioned requirements, or is there a better approach?
- If answer to 1 is yes, what would be a good choice of a data structure? I think that b-trees seem to fulfil most if not all of them, but i am not quite convinced so i need guidance and justified solutions on the matter.
Thanks in advance.
