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:

  1. Keep nodes sorted by a score relevant to the times already advertised,preferably self adjusting sorting on insertion of new nodes
  2. Fast selection of first k elements based on score
  3. Easy update of score and position of nodes in each advertise action
  4. Easy check of duplicate nodes upon insertion, e.g caused by a node failure and reconnect.
  5. Synchronization for concurrent access, modification

The language used for implementation is java.


  1. 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?
  2. 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.

  • What do you mean by "correctly?" – Robert Harvey Jan 27 '18 at 19:27
  • @RobertHarvey do the choice of the score/probability and the requirements satisfy the goal of growing the network graph in the desired way described above? – ichantz Jan 27 '18 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.